Hamiltonian path problem

与えられたn-頂点グラフでHamiltonian pathになる可能性のある（完全なグラフではなる）頂点のシーケンスはn！異なるので、可能なシーケンスをすべてテストするブルートフォース探索アルゴリズムは非常に遅くなります。有向グラフ上でHamiltonian cycleを見つけるための初期の厳密なアルゴリズムは、Martelloの列挙アルゴリズムでした。 フランク・ルービンによる探索手順では、グラフの辺を「パスに必ず含まれるもの」「パスに含まれないもの」「未定のもの」の3つのクラスに分けます。 探索を進めていくと、一連の決定規則によって、決定されていない辺が分類され、探索を停止するか継続するかが決定される。 このアルゴリズムは、グラフを別々に解決できる要素に分割します。 また、Bellman, Held, Karpの動的計画法を用いれば、O(n2 2n)の時間で解くことができます。 この方法では、各頂点のセット S と S の各頂点 v に対して、S の頂点を正確にカバーして v で終わるパスがあるかどうかを判断します。S と v の各選択に対して、(S – v,w) にパスが存在するような隣人 w が v に存在する場合に限り、(S,v) にパスが存在することになりますが、これは動的プログラムで既に計算された情報から調べることができます。

Andreas Björklund 氏は、包含排除原理を使用して、ハミルトニアンサイクルの数をカウントする問題を、サイクルカバーをカウントするという、より単純なカウント問題に減らすという別のアプローチを提供しました。

最大次数3のグラフでは、慎重なバックトラック探索により、時間O(1.251n)でハミルトニアンサイクルを見つけることができます。

ハミルトニアンパスとサイクルは、SATソルバーを使って見つけることができます。

ハミルトニアンパスとサイクルの問題は、従来のコンピュータでは解くことが難しいため、型破りなコンピュータモデルでも研究されてきました。

ハミルトニアンパス問題やサイクル問題は、通常のコンピュータでは解くことが難しいため、従来とは異なるモデルでも研究されています。 化学反応に固有の並列性を利用して、グラフの頂点の数に線形な化学反応ステップの数で問題を解くことができますが、反応に参加するためには階乗数のDNA分子が必要になります。 これは、光ケーブルとビームスプリッターでグラフのような構造を作り、その上を光が通過することで、問題の解決策を構築するというものです。 この方法の弱点は、必要なエネルギーがノードの数で指数関数的に増加することです。