電子情報通信学会総合大会講演要旨
D-1-11
GPUによるナップサック問題に対する高速近似解法の試み
○浦部峻紀・藤本典幸(阪府大)
本質的に逐次性を持つ貪欲法のアルゴリズムに対し、並列性を持つε-貪欲法のアルゴリズムがRaviらによって提案された.本論文では,ナップサック問題に対してRaviらのアルゴリズムをもとに考案したGPUで高速に近似解を求める方法を提案する.同じε-貪欲法に基づいたアルゴリズムで実装したCPU逐次プログラムと今回提案するGPU並列プログラムと実行時間を比較した結果,荷物の個数が2097152(=2^21)個のときに平均で約6.7倍の高速化を達成した.