巡回セールスマン問題における2-opt法のGPGPUによる高速化

• 福田悠太

• 大川猛

• 大津金光

• 横田隆史

Abstract

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

Journal

• 第76回全国大会講演論文集

  第76回全国大会講演論文集 2014 (1), 197-198, 2014-03-11

Keywords

• アーキテクチャ

Details

• CRID: 1050855522055629824
• NII Article ID: 170000085434
• NII Book ID: AN00349328
• Web Site: http://id.nii.ac.jp/1001/00104315/
• Text Lang: ja
• Article Type: conference paper
• Data Source:
  • IRDB
  • CiNii Articles
  • KAKEN