4K-7
SIMD 2-opt法のGPGPUへの適応と評価
○坂本 亮，小西克巳（工学院大）
巡回セールスマン問題は，都市の集合とそれらの間の移動コストが与えられたときに，全ての都市をちょうど1巡して出発地に戻る移動距離を求める問題である．
この問題はNP困難として知られている．巡回セールスマン問題は厳密解を多項式時間内で求めることが計算量的に困難であることより，さまざまなアプローチでの問題解決手法が研究されている．
それらは精度保証のついた数学的解法や，アントコロニー最適化などの精度保証のない発見的手法などである．
本研究では，発見的解法の一つである2-opt法にSIMD手法を組み込んだSIMD 2-opt法を提案し，OpenCLを用いてGPU上に実装を行い，その性能を評価する．