ハミルトンパスチェッカー — 各ノードを正確に一度訪れるパスを見つける
このハミルトンパスチェッカーは、各可能な開始ノードを試し、可能なルートを通じてバックトラックすることで、グラフを通る各ノードを正確に一度訪れるパスを探します。グラフはシンプルなテキストの辺リスト（例：A-B, B-C, C-D）として入力します。
クイック回答
グラフを辺リストとして入力すると（最大10ノード）、バックトラッキングによって各ノードを正確に一度訪れるルートであるハミルトンパスを即座に検索します。
辺をNodeA-NodeBの形式で入力してください（例：A-B, B-C, C-D）。最大10ノード。
ハミルトンパスチェッカー — オンラインで各ノードを一度訪問の使い方
- 1
グラフをカンマ区切りの辺リストとして入力します（例：A-B, B-C, C-D）。
- 2
「計算」をクリックしてハミルトンパスを検索します。
- 3
見つかったパス、または存在しないことの確認を確認します。
なぜハミルトンパスチェッカー — オンラインで各ノードを一度訪問を使うのか？
ハミルトンパスは、グラフ内のすべての頂点を正確に一度訪れます — すべての辺を訪れることに関するオイラーパスとは異なり、これはすべてのノードを訪れることに関するものです。それが存在するかどうかを判定することは一般にNP完全であり、これは可能性を体系的に試すよりも劇的に速い既知のアルゴリズムがないことを意味します。そのため、この計算機はバックトラッキング探索を使用します：一度に1つのノードずつパスを構築し、行き止まりに達するたびにバックトラックし、可能なすべての開始ノードを試します。探索空間はグラフのサイズとともに階乗的に増加するため、この計算機は意図的に最大10ノードに限定されており、そこでは徹底的なバックトラッキング探索でも即座に完了します。
よくある質問
関連ツール
巡回セールスマン問題ソルバー — 正確なHeld-Karp DPをオンラインで
Held-Karp動的計画法アルゴリズムを使用して、各都市を正確に1回訪問する正確な最短往復経路を求めます。無料電卓、最大12都市まで。
トポロジカルソート計算機 — オンラインでカーンのアルゴリズム
カーンのアルゴリズムを使用して有向グラフの有効なトポロジカル順序を見つけるか、サイクルのために順序が存在しないことを検出します。シンプルな辺リスト入力を備えた無料計算機。
最小全域木計算機 — クラスカルのアルゴリズムをオンラインで
クラスカルのアルゴリズムを使用して、重み付きグラフの最小全域木を求めます。シンプルな辺リスト入力とUnion-Findによるサイクル検出を備えた無料計算機。