情報処理学会 第76回全国大会講演要旨

組み合わせ最適化問題のひとつである巡回セールスマン問題の
近似解を求める際，都市数が多くなると探索空間も膨大となる
ため，多くの計算時間が必要となる.
また，都市数が数万都市以上の規模になると，高速な近似アル
ゴリズムである2-opt法を用いても計算時間が膨大となる.
一方，近年は高速な画像処理を得意とするGPUに汎用的な数値
計算を行わせるGPGPUが注目されている.
GPGPUを活用することにより，CPUを用いる場合よりも大幅な
速度向上を実現することができる.
本稿では，巡回セールスマン問題の近似アルゴリズムである
2-opt法の計算をGPUを用いて並列処理を行い，性能評価を行う.