巡回セールスマン問題

巡回セールスマン問題を総当たりで解く場合のイメージ。左側で一つずつ探していき、より効率のいいルートが見つかった場合、右側のグラフが更新される。

巡回セールスマン問題︵じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP︶は、都市の集合と各2都市間の移動コスト︵たとえば距離︶が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める︵セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める︶組合せ最適化問題である。

詳細

問題例の大きさは、都市の数で表される。この問題は、計算複雑性理論においてNP困難と呼ばれる問題のクラスに属する。すなわち、問題例の大きさに関する決定性の多項式時間アルゴリズムが見つかりそうにない、計算量的に困難な問題である。なお、この問題の特殊ケースとして考えられるハミルトン閉路問題は、NP困難であると共にNP完全と呼ばれるクラスにも属するので、扱いが異なる。

都市間の移動コストが三角不等式を満たす、すなわち移動コストを距離と呼べる部分問題︵あるいは制約つき問題︶も、NP困難である。都市を平面上の点、都市間の距離を平面上のユークリッド距離とする部分問題は最も直感的で理解しやすいが、これもNP困難である。この部分問題は平面TSPなどと呼ばれ、実用上の応用も多く、またベンチマークの問題例としても距離関数の定義が自明なため頻繁に現れる。 都市の間の移動コストを1または2に制限しても、この問題はNP困難である。ハミルトン閉路問題は、移動コストを1または無限大に制限した TSP とみなすことができる。

一方で制約のない巡回セールスマン問題の直接の応用事例は無いと言ってもよい。逆に実際の応用事例では、より複雑な定義で配送計画や表面実装ロボットの動作計画などに適用される。

解法

全ての経路を計算することで最適解を得る手法は時間計算量は$O(n!)$$O(n!)$であり、都市数の増加に対して時間計算量が急速に増加するため、都市数が20以上になると現実的でない。 比較的効率的なアルゴリズムとしては時間計算量と空間計算量が共に$O(n^{2}2^{n})$$O(n^{2}2^{n})$である動的計画法を用いたヘルドカープのアルゴリズムが存在する。

NP困難な問題は、任意の大きさの任意の問題例に対しての多項式時間アルゴリズムが存在しないと考えられているが、巡回セールスマン問題の場合、約2000都市以内の比較的小さい問題例に対して、あるいは問題例によっては解が得られないことがあってもよいのであれば、線形計画法と論理木を組み合わせた分枝限定法や、線形計画法と巡回群を組み合わせた切除平面法により、パーソナルコンピュータでおよそ1日以内で厳密解を得られることが多い。

厳密に最適解を求めることを放棄して計算時間を短くする方法は、2-optやリン・カーニハン・アルゴリズムなどの局所探索アルゴリズム、焼きなまし法、ホップフィールドネットワークあるいはボルツマン機械などのヒューリスティックアルゴリズムと、出力される解のコストと最適解のコストとの差をなんらかの形で保証する多項式時間近似アルゴリズムの二つに大別できる。

より複雑な定義の問題をあつかう解法としては、欧州では前述した分枝限定法、切除平面法、︵前者2つをミックスした︶分枝カット法といった厳密解法を用いることが多く、アメリカ合衆国では遺伝的アルゴリズム、タブー探索といった厳密に最適な解を保証しないヒューリスティックアルゴリズムを用いることが多い。

三角不等式が成り立つ TSP については多項式時間近似アルゴリズムが数多く存在する。 たとえば近似アルゴリズムが2︵最悪でも出力が最適解の長さの2倍以内である︶のアルゴリズム︵最近追加法他︶や近似度 1.5 のアルゴリズム︵クリストフィードのアルゴリズム︶が知られている。 近年、平面TSP には、近似率を任意に1に近づけることができるアルゴリズム、多項式時間近似戦略 PTAS が Arora によって与えられた。 ハミルトン閉路問題の多項式時間の厳密解が多項式時間で求められない︵ハミルトン閉路問題はNP完全なのでP≠NPと同じ︶なら三角不等式を満たさないTSPは近似率を保証する多項式時間のアルゴリズムはない。

関連項目

• ハミルトン閉路問題
• 中国人郵便配達問題 - すべての辺（頂点ではなく）を少なくとも1回ずつ通る巡回路でコスト最小のものを求める。こちらは多項式時間で解けることが知られている。
• DNAコンピュータ
• 粘菌コンピュータ
• 最近傍法
• P≠NP予想
• 配車配送計画ソフト

外部リンク

• 『巡回セールスマン問題の意味と2近似アルゴリズム』 - 高校数学の美しい物語
• TSPLIB - TSPのベンチマーク問題集その1
• Traveling Salesman Problem - TSPのベンチマーク問題集その2 (World TSP，National TSPs, VLSI)
• TSPのソースコードへのリンク集