巡回セールスマン問題ソルバー TSP

すべての都市を一度だけ訪問して出発点に戻る最短ルートを算出します。小規模なケースには厳密な動的計画法 (Held-Karp) を、大規模なケースには最近傍法 + 2-opt ヒューリスティックを使用します。座標入力または距離行列に対応し、アニメーション SVG ルートを表示します。

巡回セールスマン問題ソルバー TSP

クイック例:

5都市正方形+山なりランダムな8都市 EU 8ヶ国の首都 4×4 行列 10都市ベンチマーク三角形（開いた経路）

⌖ 座標 (x, y) ▦ 距離行列

都市または行列

座標行: A, 10, 20 または 10 20。行列行: 0 10 15 20 — 1行に1行ずつ、正方、非負。最大 40 都市。

行列ラベル (任意)

カンマまたはスペース区切りのラベル（行列の各行に1つ）。省略した場合は A, B, C… がデフォルトになります。

アルゴリズム

巡回タイプ

Embed 巡回セールスマン問題ソルバー TSP Widget

巡回セールスマン問題ソルバー TSP

巡回セールスマン問題ソルバー TSPは、古典的な巡回セールスマン問題 (TSP)のための実用的で教育的な電卓です。この問題は、都市の集合とそれらのペア間の距離が与えられたとき、すべての都市をちょうど一度だけ訪問して出発点に戻る最短の経路を見つけるものです。このソルバーは、平面座標またはカスタム距離行列のいずれかを受け入れ、問題の規模に基づいて最適なアルゴリズムを自動的に選択し、結果のルートをアニメーションSVGマップとしてレンダリングします。

巡回セールスマン問題とは？

形式的には、頂点集合 $V = \{1, 2, ..., n\}$ とエッジの重み $d(i, j)$ を持つ完全重み付きグラフ $G = (V, E)$ が与えられたとき、TSP は次を最小化する頂点の置換 $\pi$ を求めます：

最小化： Σ_i=1^n-1 d(π(i), π(i+1)) + d(π(n), π(1))

最後の項がループを閉じます。TSP は組合せ最適化において最も古く、最も研究されている問題の一つです。一般的なケースでは NP 困難であり、すべてのインスタンスを多項式時間で解く既知のアルゴリズムは存在しません。それにもかかわらず、車両のルーティング、プリント基板の穴あけ、DNA シーケンシング、倉庫のピッキングルート、天体観測スケジュール、さらには地方の郵便配達など、数え切れないほどの現実世界のアプリケーションに登場します。

このソルバーの仕組み

Held–Karp 動的計画法 (厳密解)

小規模なインスタンス（12都市まで）の場合、ソルバーは1962年に Richard Bellman と Michael Held & Richard Karp によって独立して発表された Held–Karp アルゴリズムを使用して、証明可能な最適ルートを計算します。キーとなる漸化式（ここで $C(S, j)$ は、頂点 1 から頂点 $j$ まで、部分集合 $S$ を正確に訪問する最短パス）は次の通りです：

C(S, j) = min_{k ∈ S \ {j}} [ C(S \ {j}, k) + d(k, j) ]

最適な巡回コストは、 $min_{j} [C(\{1,...,n\}, j) + d(j, 1)]$ となります。Held–Karp は O(2ⁿ · n²) の時間と O(2ⁿ · n) のメモリで動作します。これは総当たり（$n!$）に比べて大幅な改善ですが、依然として指数関数的です。およそ 20 都市を超えると、メモリ使用量が非現実的になります。

最近傍法 + 2-opt (ヒューリスティック)

より大きなインスタンスの場合、ソルバーは2段階のヒューリスティックを使用します。まず、最近傍法が、各開始頂点から最も近い未訪問の都市へと貪欲に移動することで、素早い巡回ルートを構築します。ソルバーは多くの開始頂点を試し、最良のルートを保持します。次に、2-opt 局所探索が、2つのエッジを繰り返し削除し、結果として得られる2つのパスを他の唯一可能な方法で再接続することでルートを改善します：

適用前： ... a — b ... c — d ... 2-opt 入れ替え後： ... a — c ... b — d ... もし d(a,c) + d(b,d) < d(a,b) + d(c,d) ならば入れ替えを承認し、部分経路 b..c を反転させる

幾何学的には、2-opt はルート内のすべての「交差」を取り除きます。交差している2つのセグメントは、常に交差を解消することで総距離を短縮できます。アルゴリズムは、単一の入れ替えでは改善されない局所最適解で停止し、これを 2-最適 な経路と呼びます。現実的なユークリッド距離のインスタンスでは、2-opt は通常、ミリ秒単位で真の最適解の 2〜5% 以内のルートを見つけます。

入力形式

座標モード (x, y)

1行に1つの都市を入力します。各行は「ラベル, x, y」の形式で、ラベルは任意です。ソルバーはユークリッド距離を自動的に計算し、都市を真の位置に視覚化します。

A, 10, 20 B, 40, 70 C, 75, 30 Paris: 2.35, 48.86 10 20 ← ラベルは自動的に C1 になります

距離行列モード

$n \times n$ の非負の距離の正方行列を、1行に1行ずつ、スペースまたはカンマで値を区切って入力します。行列は対称でも非対称でも構いません。非対称行列は、一方通行、空席状況によって変わる航空券の価格、風に依存する移動などをモデル化できます。必要に応じて「行列ラベル」フィールドにラベルを指定してください。

0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0

アルゴリズムの比較

アルゴリズム	時間計算量	メモリ	結果の質	実用的なサイズ
総当たり (Brute force)	O(n!)	O(n)	最適	n ≤ 10
Held–Karp DP	O(2ⁿ · n²)	O(2ⁿ · n)	最適	n ≤ 20
最近傍法 (Nearest-Neighbor)	O(n²)	O(n)	最適解より約25%劣る	n ≤ 数千
NN + 2-opt	O(n² · passes)	O(n)	最適解より約2–5%劣る	n ≤ 数百

このソルバーの使い方

入力モードを選択します。 都市が意味のある (x, y) 位置を持っている場合は「座標」を、コストが非ユークリッドまたは非対称である場合は「距離行列」を選択します。
データを貼り付けるか入力します。 1行に1つの都市または行列の行を入力します。フォームの上にあるクイック例ボタンをクリックすると、有効な例が事前入力されます。
アルゴリズムを選択します。 適切なデフォルト設定のために「自動」のままにしておくと、証明可能な最適性が得られる規模であれば Held–Karp が、そうでなければ NN + 2-opt が選択されます。比較したい場合は、特定のアルゴリズムを強制的に選択することもできます。
閉じた経路か開いた経路かを選択します。 閉じた経路は出発点に戻ります。これは伝統的な TSP です。開いた経路モードは、セールスマンが別の都市で終了する、関連するハミルトンパス問題を解決します。
「解決」をクリックします。 結果ページには、総巡回距離、ルートのアニメーションSVG（「アニメーション再生」で再試行可能）、完全な都市シーケンス、エッジごとの内訳、およびルートで使用されたエッジが強調表示された距離行列が表示されます。

具体例

5つの都市（長方形＋頂点）： A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5) を考えます。ソルバーは以下を返します：

ルート： A → D → E → C → B → A
距離： 3 + √8 + √8 + 3 + 4 ≈ 15.66
最適解か？ はい。Held–Karp により、これより短いルートが存在しないことが証明されています。
なぜこの順序か？ このルートは5つの点の凸包を辿ります（A → D → E → C → B → A）。ユークリッド TSP の古典的な性質として、最適ルートは凸包上の点をその巡回順序で訪問し、内部の点は隣接する凸包の隣人の間に配置されるというものがあります。 A → C → B → D → E → A (距離 ≈ 21.8) のように、自身のパスが交差するルートは、2-opt によって交差を解消し、より短い結果を得ることができます。

現実世界での応用

物流・配送 — ドライバーの1日のルート（15箇所など）を最適化し、燃料と時間を最小限に抑えます。
製造業 — CNC ドリルが PCB 上に開ける穴の順序を決定し、ヘッドの移動距離を最小限にします。
ゲノムアセンブリ — 重なりの類似性（距離行列としてエンコード）によって DNA 断片を順序付けます。
天文学 — 観測時間を最大化するために、標的となる星の間の望遠鏡の旋回をスケジュールします。
倉庫ピッキング — 注文を最小限のステップで処理するために、通路の訪問順序を決めます。
旅行計画 — 移動時間や運賃を最小限に抑える複数都市の旅行を計画します。

よくある質問

巡回セールスマン問題とは何ですか？

巡回セールスマン問題 (TSP) は、すべての都市を一度だけ訪問し、出発都市に戻る最短の経路を求める問題です。これは組合せ最適化における最も有名な問題の一つであり、一般的なケースでは NP 困難です。つまり、すべてのインスタンスを多項式時間で解決する既知のアルゴリズムは存在しません。

Held–Karp アルゴリズムとは何ですか？

Held–Karp は、TSP を厳密に解く動的計画法アルゴリズムで、時間計算量は O(2ⁿ · n²)、空間計算量は O(2ⁿ · n) です。総当たり（$n$ 階乗）よりも劇的に高速ですが、依然として指数関数的であるため、実際には 20 都市程度までのインスタンスに使用されます。このソルバーでは、都市が 12 個以下のときに Held–Karp を使用します。

2-opt とは何ですか？なぜ使用されるのですか？

2-opt は、現在の経路から2つのエッジを繰り返し削除し、結果として生じる2つのパスを別の可能な方法で再接続する局所探索ヒューリスティックです。新しい経路が短い場合、その入れ替えが保持されます。2-opt は 1 回の反復につき多項式時間で動作し、一貫して最適解から数パーセント以内の経路を見つけるため、大規模な TSP インスタンスにおける古典的な手法として使用されます。

座標と距離行列のどちらを使うべきですか？

都市が平面上にあり、直線距離（例：地図上の地点、倉庫の場所、回路基板のドリル穴）である場合は「座標」を使用します。ペアのコストがユークリッド距離ではない場合（例：航空券の価格、渋滞を考慮した移動時間、一方通行の道路距離、非対称コスト）は「距離行列」を使用します。行列モードは、非対称なものも含め、あらゆる非負の距離を受け入れます。

2-opt の解は最適ですか？

いいえ、2-opt は「2-最適」な経路を返します。これは、1組のエッジを入れ替えてもより短いルートが作成できない状態を意味します。これは局所最適解であり、通常は最適解から数パーセント以内ですが、グローバルな最適解である保証はありません。小規模なインスタンスで証明可能な最適解を得るには、Held–Karp を選択してください。

このツールは非対称距離行列をサポートしていますか？

はい。距離行列モードでは、D[i][j] が D[j][i] と異なる非対称な行列を含む、任意の非負の正方行列を入力できます。Held–Karp と 2-opt はどちらも非対称行列を正しく処理します。これは、一方通行、交通状況、または風向きに依存する飛行コストなどの現実世界のルーティング問題に役立ちます。