ハミルトン経路問題

ハミルトン経路とハミルトン閉路を見つける問題は、以下のように関連付けることができます。

• ある意味では、グラフGのハミルトン経路問題は、Gから新しい普遍頂点xを追加して得られるグラフHにおけるハミルトン閉路問題と関連付けることができる。この普遍頂点xは、Gのすべての頂点に接続されている。したがって、ハミルトン経路を見つけるのにかかる時間は、ハミルトン閉路を見つけるのにかかる時間よりも著しく遅くなることはない（最悪の場合でも、頂点の数の関数として）。
• 反対方向には、グラフGのハミルトン閉路問題は、G の頂点 v と v の分割コピー v' にそれぞれ終端(次数 1) 頂点 s と t を追加して得られるグラフHのハミルトン路問題と同等である。v 'はvと同じ近傍を持つ。H のハミルトン路は頂点 ⁠ を通る。${\displaystyle svx-\cdots -yv'-t}$⁠ は、 Gにおけるハミルトンサイクルがを通り抜けることに対応します。${\displaystyle vx-\cdots -y(-v)}$⁠ . ^{[ 4 ]}

グラフにハミルトン路が存在するかどうかを判断するには、入力グラフ G 内の考えられるすべての経路をチェックする必要があります。与えられたn頂点のグラフでは、ハミルトン路になり得る頂点の異なるシーケンスがn ! 通りあります(完全グラフでは、実際にハミルトン路になります)。そのため、考えられるすべてのシーケンスをテストする総当たり探索アルゴリズムは非常に遅くなります。

有向グラフ上のハミルトン閉路を見つけるための初期の正確なアルゴリズムは、マルテロの列挙アルゴリズムでした。^{[ 3 ]}フランク・ルービンによる探索手順^{[ 5 ]}は、グラフのエッジを、パスに必ず含まれるエッジ、パスに含まれないエッジ、および未決定のエッジの3つのクラスに分けます。探索が進むにつれて、一連の決定ルールが未決定のエッジを分類し、探索を停止するか続行するかを決定します。パスに含まれないエッジは削除できるため、探索は継続的に小さくなります。このアルゴリズムはまた、グラフを個別に解決できるコンポーネントに分割し、探索サイズを大幅に削減します。実際には、このアルゴリズムは今でも最速です。

また、ベルマン、ヘルド、カープによる動的計画法アルゴリズムを用いて、この問題を O( n ² 2 ⁿ ) の時間で解くことができます。この方法では、頂点の集合SとS内の各頂点vについて、 S内の頂点をすべて網羅し、 vで終わるパスが存在するかどうかを判定します。Sとvの任意の選択について、( S , v ) のパスが存在するのは、 vに隣接頂点wが存在し、 ( S − v , w )のパスが存在する場合のみです。このパスは、動的計画法で既に計算された情報から調べることができます。^{[ 6 ] [ 7 ]}

アンドレアス・ビョルクルンドは、包含排除原理を用いて、ハミルトン閉路の数を数える問題を、より単純な閉路被覆の数を数える問題に還元する代替アプローチを提供しました。この問題は、特定の行列式を計算することで解決できます。この方法を用いて、彼は任意のn頂点グラフにおけるハミルトン閉路問題をモンテカルロアルゴリズムによってO(1.657 ⁿ ) の時間で解決する方法を示しました。二部グラフの場合、このアルゴリズムはさらに時間O (1.415 ⁿ )に改善できます。^{[ 8 ]}

最大次数が３のグラフの場合、慎重なバックトラッキング探索により、ハミルトン閉路（存在する場合）をO(1.251 ⁿ )の時間で見つけることができます。^{[ 9 ]}

ハミルトン経路はSATソルバーを用いて求めることができます。ハミルトン経路はNP完全問題であり、3-SAT問題にマッピング還元することができます。したがって、ハミルトン経路問題の解を求めることは、3-SAT問題の解を求めることと同等です。

ハミルトン経路問題とハミルトンサイクル問題を従来のコンピュータで解くのは困難であるため、非従来型の計算モデルでも研究されてきた。例えば、レナード・アドレマンは、ハミルトン経路問題はDNAコンピュータで解ける可能性があることを示した。化学反応に内在する並列性を利用することで、この問題はグラフの頂点の数に比例する数の化学反応ステップで解ける可能性があるが、反応には階乗数のDNA分子が必要となる。^{[ 10 ]}

ハミルトニアン問題に対する光学的解決策も提案されている。^{[ 11 ]}このアイデアは、光ケーブルとビームスプリッターで構成されたグラフのような構造を作り、そこに光を通して問題の解決策を構築するというものである。このアプローチの弱点は、ノードの数に対して指数関数的に増加するエネルギー量が必要となることである。

オンチップネットワーク(NoC) は、オンチップコンポーネント間の通信として機能するコンピュータシステムやプロセッサで使用されます。 ^{[ 24 ]} NoC のパフォーマンスは、ネットワークを介してデータパケットを転送する方法によって決まります。^{[ 25 ]}ハミルトンパス問題は、マルチキャストルーティングのパスベースの方法として実装できます。パスベースのマルチキャストアルゴリズムは、開始ノードから各終了ノードへのハミルトンパスが存在するかどうかを判断し、対応するパスを介してパケットを送信します。この戦略を利用することで、デッドロックやライブロックのないルーティングが保証され、NoC の効率が向上します。^{[ 26 ]}

レンダリングエンジンは、コンピュータ グラフィックスで使用されるソフトウェアの一種で、入力データから画像やモデルを生成します。^{[ 27 ]} 3 次元グラフィックス レンダリング では、エンジンへの一般的な入力はポリゴン メッシュです。オブジェクトのレンダリングにかかる​​時間は、入力の受信速度に依存し、入力が大きいほどレンダリング時間が長くなります。ただし、三角形メッシュの場合、レンダリング時間を最大 3 分の 1 に短縮できます。これは、「連続する三角形が面を共有するように三角形を順序付ける」ことによって行われます。^{[ 28 ]}このようにすると、連続する各三角形の間で 1 つの頂点だけが変わります。この順序は、三角形メッシュの双対グラフにハミルトン パスが含まれている場合に存在します。