巡回セールスマン問題ソルバー — すべての都市を巡る最短経路を求める
この巡回セールスマン問題ソルバーは、都市間の距離行列が与えられたとき、各都市を正確に1回訪問して出発都市に戻る正確な最小コスト巡回路を、Held-Karpビットマスク動的計画法アルゴリズムを使用して求めます — この問題は一般にNP困難であるため、意図的に最大12都市までに制限された正確な手法です。
クイック回答
都市間の距離行列を入力すると、Held-Karp動的計画法で正確な最短往復巡回路を即座に求められます。
1都市1行、カンマ区切りの距離を入力してください（例：0,10,15,20 の次に 10,0,35,25）。最大12都市。
巡回セールスマン問題ソルバー — 正確なHeld-Karp DPをオンラインでの使い方
- 1
距離行列を1都市1行、カンマ区切りの距離で入力します。例：0,10,15,20 の次に 10,0,35,25、というように続けます。
- 2
行列は正方形である必要があり、各要素は2つの都市間の距離を示します（対角要素は通常0です）。
- 3
「計算」をクリックして、Held-Karp動的計画法で正確な最適巡回路を求めます。
なぜ巡回セールスマン問題ソルバー — 正確なHeld-Karp DPをオンラインでを使うのか？
巡回セールスマン問題は、各都市を正確に1回訪問して出発点に戻る最短経路を問います — 古典的なNP困難問題であり、可能な(n−1)!/2通りの巡回路すべてを総当たりでチェックすることは、少数の都市を超えると不可能になります。Held-Karpアルゴリズムは、部分集合上の動的計画法を使用して総当たりを劇的に改善します：訪問済み都市の各部分集合と各可能な終了都市について、その状態に到達する最も安価な方法を追跡し、小さな部分集合から完全な集合までO(n!)ではなくO(n² · 2ⁿ)時間で構築します。それでも指数関数的であるため、この電卓は問題を12都市までに制限しており、そこではHeld-Karpは快適に高速なままで、正確で証明可能な最適巡回路（単なる良い近似ではなく）を見つけます。
よくある質問
関連ツール
ハミルトンパスチェッカー — オンラインで各ノードを一度訪問
バックトラッキング探索を通じて、グラフがハミルトンパス（各ノードを正確に一度訪れるパス）を持つかどうかを確認します。最大10ノードのグラフに限定された無料計算機。
最小全域木計算機 — クラスカルのアルゴリズムをオンラインで
クラスカルのアルゴリズムを使用して、重み付きグラフの最小全域木を求めます。シンプルな辺リスト入力とUnion-Findによるサイクル検出を備えた無料計算機。
線形計画法ソルバー — 2変数コーナーポイント法をオンラインで
実行可能領域のすべてのコーナーポイントを求めて評価することで、2変数の線形計画問題を解きます。無料電卓、線形制約付きで最大化または最小化。