巡回路の長さ
見つかった最短
ステップ数
巡回路の総数
  • 巡回路
  • 見つかった最短
  • 出発点

方法 長さ 最短との差 ステップ数
- - -
- - -
- - -
- - -
- - -

巡回セールスマン問題についてもっと見る

巡回セールスマン問題

セールスマンはすべての都市を一度ずつ訪れて家に帰らなければなりません。どの順番で回れば旅がいちばん短くなるでしょうか。問うのは簡単ですが、都市の数が増えると、すべての順番を試して答えるのは絶望的です。30都市だけでも約 4.4 × 10³⁰ 通りの巡回路があります。地図に都市をばらまくか自分でクリックして置き、手早い経験則、巧みな改良法、そして1つの厳密な方法が巡回路を一歩ずつ作っていく様子を見て、速い方法がどこまで迫れるかを確かめましょう。 都市の配置と数を選び、方法を選んで「解く」を押すと、巡回路が一歩ずつ作られていく様子を見られます。「1ステップ」を押すと1手ずつ進みます。地図をクリックすると都市を追加でき、都市をクリックすると削除できます。「すべて比較」は同じ都市ですべての方法を実行し、それぞれが見つかった最短の巡回路からどれだけ離れているかを示します。赤い都市が旅の出発点です。

使い方

  1. 配置と都市の数を選ぶか、地図をクリックして自分で都市を置きます。都市をクリックすると削除できます。
  2. 方法を選び、「解く」を押して一歩ずつ観察するか、「1ステップ」で1手ずつ進めます。
  3. 「すべて比較」を押すと同じ都市ですべての方法が実行され、各巡回路が見つかった最短のものよりどれだけ長いかがわかります。

なぜ難しいのか

n個の都市には (n − 1)! / 2 通りの異なる巡回路があります。どこから出発しても、どちら回りでも同じだからです。5都市なら12通り、10都市なら181,440通り、20都市なら約 6 × 10¹⁶ 通りになります。どんな地図に対しても、n のべき乗程度にしか増えない時間で最短の巡回路を見つける方法は知られていません。この問題は NP 困難です。このアプリで最良の厳密な方法である1962年の Held–Karp の動的計画法でも約 n² · 2ⁿ ステップが必要なので、ここでは12都市までに制限しています。

よい巡回路を素早く

実際には、ほぼ最短の巡回路はすぐに見つかります。最近傍法はいつも未訪問の最も近い都市へ向かい、たいてい最良の巡回路より25%ほど長くなります。最安挿入法はループを育て、ループの伸びが最も小さくなる都市を加えていきます。2-opt は任意の巡回路から始め、2本の辺をより短い2本に置き換え続けます。これによりすべての交差が取り除かれ、たいてい約5%以内に近づきます。焼きなまし法はランダムな 2-opt の手を打ち、まだ「熱い」うちは巡回路を長くする手もいくつか受け入れるので、落ち着く前に行き詰まりから抜け出せます。

よくある質問

最短ルートを求める公式はありますか?

いいえ。最短の巡回路はすべての都市の正確な位置によって決まり、最悪の場合に指数関数的に増える計算量をかけずに、どんな地図でもそれを見つけられる方法は知られていません。数百から数千の都市なら、Concorde のような専用の厳密ソルバーが線形計画法と巧みな枝刈りを組み合わせて最適な巡回路を証明しています。これまでに厳密に解かれた最大の例は85,900点です。

なぜ 2-opt ではすべての交差がなくなるのですか?

巡回路の2本の辺が交差していると、それらが結ぶ4つの都市は、その2本の辺を対角線とする四角形を作ります。三角不等式により、2本の辺を四角形の向かい合う2辺に取り替えると必ず短くなり、その間の巡回路の区間は逆向きになります。2-opt は改善できなくなるまでこの交換を続けるので、最終的な巡回路が自分自身と交差することはありません。

焼きなまし法の温度とは何ですか?

巡回路を長くする手をどれだけ受け入れやすいかを決める値です。長さを d だけ増やす手は確率 e^(−d/T) で受け入れられます。温度 T が高いとほとんど何でも受け入れられるので、巡回路はまずい配置から抜け出せます。T が下がるにつれて方法は貪欲になり、落ち着いていきます。この名前は、金属をゆっくり冷やして原子をエネルギーの低い配置に落ち着かせる「焼きなまし」に由来します。

なぜ厳密解法は12都市までなのですか?

Held–Karp は、都市のあらゆる部分集合と、最後に訪れる都市のあらゆる候補について最短経路を記録します。これは約 n · 2ⁿ 個の数で、それぞれを n 回の比較で埋めていきます。12都市なら数十万ステップですが、25都市なら数十億ステップになります。それでも (n − 1)! / 2 通りの巡回路をすべて試すよりはるかに高速です。12都市ならその数は2,000万近くになります。

何かがサーバーに送信されますか?

いいえ。都市も5つの方法もすべてブラウザ内で動作します。クリックして置いた都市は、このブラウザのローカルストレージに保存されます。

試してみますか?

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

エディターへ