巡回セールスマン問題を解説

セールスマンに都市のリストを渡し、それぞれを一度ずつ訪れて家に帰る最短の旅を求めてみましょう。提案されたルートは誰でも確かめられますし、まずいルートなら目で見て改善することもできます。それなのに、いつも最良のものを見つける速い方法は誰も知りません。巡回セールスマン問題は難しい問題の代表例となり、それに挑むために考え出された方法は、今では配送の計画、回路基板の穴あけ、ゲノムの組み立てに使われています。

閉じた巡回路で結ばれた都市の地図。出発点の都市に印が付き、その下にもっと短い巡回路がうっすらと見える
閉じた巡回路で結ばれた都市の地図。出発点の都市に印が付き、その下にもっと短い巡回路がうっすらと見える

問題

巡回路はすべての都市をちょうど一度ずつ訪れ、出発した場所で終わります。その長さは途中の距離の合計です。課題は最短の巡回路を見つけることです。ここで扱う版では距離は地図上の直線距離なので、A から C へ行くのが B を経由するより長くなることはありません。これが計量的巡回セールスマン問題です。このパズルは1930年ごろに数学者カール・メンガー(Karl Menger)によって論じられ、その名前は続く数十年のあいだ、ランド研究所(RAND Corporation)の数学者たちが取り上げたころに広まりました。

1970年のカール・メンガー。巡回セールスマン問題を1930年ごろ論じた。
1970年のカール・メンガー。巡回セールスマン問題を1930年ごろ論じた。

ルートの爆発

出発する都市を固定します。次の都市の選び方は n − 1 通り、その次は n − 2 通り、というように続き、どの巡回路も2つの向きにたどれるので、巡回路は (n − 1)! / 2 通りあります。10都市なら181,440通りで、コンピュータには簡単です。20都市では約 6 × 10¹⁶ 通り、70都市では観測可能な宇宙にある原子の数を超えます。コンピュータが速くなってもあまり役に立ちません。都市が1つ増えるごとに、計算量はおよそ n 倍になるからです。

NP 困難

1972年、リチャード・カープ(Richard Karp)は、グラフにすべての頂点を通る巡回路、つまりハミルトン閉路があるかどうかという問題が、どれも同じくらい難しい NP 完全問題の一族に属することを示しました。巡回セールスマン問題はこれを含むので、NP 困難です。この問題を速く解く方法があれば、スケジューリング、物流、暗号の分野にある何千もの他の問題も速く解けることになります。そのような方法が存在するかどうかが P 対 NP 問題であり、ミレニアム懸賞問題の1つです。

厳密な方法:Held–Karp

1962年、マイケル・ヘルド(Michael Held)とリチャード・カープ、そしてそれとは独立にリチャード・ベルマン(Richard Bellman)が動的計画法を用いました。都市のあらゆる集合 S と、S に含まれるあらゆる都市 j について、出発地の都市から始まり、S の都市をちょうど訪れて j で終わる最短経路を計算します。それぞれの値は S から j を除いた集合の値から求まるので、表は小さな集合から大きな集合へと埋められ、最後に最短の巡回路が得られます。必要なのは n! ではなく約 n² · 2ⁿ ステップで、30都市では数分と宇宙の年齢ほどの差になりますが、それでも指数関数的に増えます。

1962年のリチャード・ベルマン、アルフレッド・アイゼンスタット撮影。1950年代初め、ランド研究所に勤めていた彼が動的計画法と名づけた。
1962年のリチャード・ベルマン、アルフレッド・アイゼンスタット撮影。1950年代初め、ランド研究所に勤めていた彼が動的計画法と名づけた。

手早い構成法

最近傍法は、まだ訪れていない最も近い都市へ常に移動します。単純で速いのですが、いくつかの都市を取り残しがちで、それらを最後に長い回り道で回収しなければならないため、巡回路はたいてい最良のものより25%ほど長くなります。一方、挿入法は閉じたループを保ち、残りの都市を1つずつ、コストが最も小さくなる位置に加えていきます。1976年にはニコス・クリストフィデス(Nicos Christofides)が、どんな計量的な地図でも最適値の1.5倍以下になることが保証された構成法を見つけました。この上限は40年以上、ほとんど破られませんでした。

巡回路の改善:2-opt

局所探索は任意の巡回路から始め、それを短くする小さな変更を繰り返します。古典的な手である 2-opt は、2本の辺を取り除き、2つの断片を逆の向きにつなぎ直します。これにより、その間の区間が反転します。2本の辺が交差していれば、この手で交差がほどけて長さが短くなるので、2-opt でこれ以上改善できない巡回路は自分自身と交差しません。ランダムな地図では、2-opt の巡回路はたいてい最適値より5%ほど長くなります。3本の辺を入れ替えるより強力な手や、1973年のリンとカーニハンによる可変深度法を使えば、さらに近づけます。

焼きなまし法

局所探索は、ずっとよい巡回路が存在するにもかかわらず、どの1手を打っても悪くなる巡回路で行き詰まることがあります。1983年にスコット・カークパトリック(Scott Kirkpatrick)、ダニエル・ジェラット(Daniel Gelatt)、マリオ・ベッキ(Mario Vecchi)がこの問題に応用した焼きなまし法は、冶金学から着想を得ています。悪化する手を、温度に応じた確率で受け入れるのです。温度は最初は高く、ゆっくりと下げられます。序盤は巡回路が自由にさまよい、終盤には改善だけが受け入れられます。冷却が十分にゆっくりであれば、とてもよい巡回路を確実に見つけられます。

実際に試す

巡回セールスマンのデモを開くと、最大200の都市を、ランダムに、円周上に、クラスター状に、格子状に、あるいはクリックした好きな場所に置けます。最近傍法が最後の都市を取り残す様子や、2-opt がすべての交差をほどく様子を見て、焼きなまし法の温度が下がっていくのを追い、Held–Karp に12都市までの最短巡回路を証明させてみましょう。「すべて比較」は同じ地図ですべての方法を実行し、各巡回路が見つかった最短のものよりどれだけ長いかを示します。

よくある質問

巡回セールスマン問題はどこで使われていますか?

多くの場所を効率のよい順番で訪れる必要があるところなら、どこでも使われます。配達や集荷のルート、回路基板上のドリルやレーザーの経路、望遠鏡が星を観測する順番、倉庫でのピッキングの順番、そして距離の意味は異なりますが、DNA 配列を組み立てるときの断片の並び順などです。

これまでに厳密に解かれた最大の問題は何ですか?

1954年、ジョージ・ダンツィーク(George Dantzig)、レイ・フルカーソン(Ray Fulkerson)、セルマー・ジョンソン(Selmer Johnson)は、アメリカ合衆国の49都市を回る最短の巡回路を証明しました。2006年には、デビッド・アップルゲート(David Applegate)、ロバート・ビクスビー(Robert Bixby)、ヴァシェク・フヴァータル(Vašek Chvátal)、ウィリアム・クック(William Cook)による Concorde ソルバーが、何年分ものコンピュータ時間をかけて、チップ設計に由来する85,900点を回る最適な巡回路を証明しました。

最短の巡回路にはいつも交差がないのですか?

はい、直線距離を使う平らな地図の上ではそうです。2本の辺が交差していれば、それらを、それらが作る四角形の2辺に取り替えると巡回路が短くなるので、交差のある巡回路は最短にはなりえません。

ヒューリスティックは毎回同じ巡回路を返しますか?

ここで使っている最近傍法、最安挿入法、2-opt は決定的で、同じ都市に対しては同じ巡回路を返します。焼きなまし法はランダムな巡回路から始めてランダムな手を打つので、2回の実行で異なる巡回路になることがあります。ただし、長さはたいていほぼ同じです。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

巡回セールスマンのデモを開く