オプティマインドで最適化エンジニアを務める武内です。

巡回セールスマン問題（traveling salesman problem, TSP）とは、ある都市から出発してすべての都市をちょうど1度ずつ訪れたのち、もとの都市に戻るルート（巡回路）のうち、総距離が最小となるものを求める問題です。組合せ最適化という分野で古くから研究されており、かつ同分野の代表的な問題でもあるため、一度はどこかで耳にしたことがあるかもしれません。

一見、コンピュータで簡単に解けそうな問題のように思えますし、実際都市の数が少ないうちは結構いけるのですが、都市の数が増えると解の候補が爆発的に増え、途端に解くのが難しくなることが知られています。

今回はTSPをいろいろな手法を用いて解き、どの程度の時間と精度で解が得られるかをご紹介したいと思います。

詳細はこちらをご覧ください。
▼▼
https://qiita.com/take314/items/dc2e6cf6d97889923c8b