algorithm - グラフでハミルトニアン ウォークを見つけるための多項式時間アルゴリズム

Question

グラフでハミルトニアンウォークを見つけるための多項式時間アルゴリズムはありますか?

私のアルゴリズムは N 階乗であり、非常に遅いです。

Answer 1

一般に、ハミルトニアン パス問題 (の決定バージョン) は NP 完全であるため、ハミルトン パスを見つけるための多項式時間アルゴリズムを取得することは期待できません。通常の N で少し高速化できます。→ N ² 2 ^N動的計画法のトリック (compute hp[v][w][S] = 「終点 v と w を持ち、その頂点がサブセット S であるパスがあるか」を、すべてのサブセット S とすべての 2 つの頂点 v とDP を使用してその中に w) がありますが、それでも指数関数的です。

ただし、ハミルトニアン経路が常に存在する特別な種類のグラフが多くあり、それらは簡単に見つけることができます (Posa、Dirac、Ore などの研究を参照してください)。

たとえば、次のことが当てはまります。グラフのすべての頂点の次数が少なくとも n/2である場合、グラフはハミルトン パスを持ちます。^{実際、O(n 2} )、またはより巧妙に行えば、IIRC で O(n log n) を見つけることができます。
[大まかなスケッチ: 最初に、すべての頂点を何らかの「ハミルトニアン」サイクルで接続するだけです。エッジが実際にグラフ内にあるかどうかは気にしないでください。ここで、実際にはグラフにないサイクルのすべてのエッジ (v,w) について、サイクルの残りの v...w を考慮します。deg(v)+deg(w)>=n として、w が x の隣人で v が y の隣人であるような連続した x、y が (この順序で) リストに存在します。[証明: {w のすべての近傍の集合} と {v の近傍のリスト内のすべての後継者の集合} を考えてみましょう。] ここで、サイクル [v...xy...wv] を [vy...wx...v] に変更します。代わりに、無効なエッジが少なくとも 1 つ少ないため、多くても必要になります。真のハミルトニアン サイクルを取得するための n 回の反復。詳細はこちら】

ところで：あなたが探しているのがすべてのエッジを1回含むウォークである場合、それはオイラーウォークと呼ばれ、それを持つグラフの場合（奇数次数の頂点の数は0または2）、多項式で非常に簡単に見つけることができます時間（速い）。

Answer 2

あなたは百万ドルの質問をしました。ハミルトン経路を見つけることは NP 完全問題です。一部の NP 困難な問題は、動的計画法を使用して多項式時間で解くことができますが、(私の知る限り)これはそれらの 1 つではありません。

Answer 3

NPコンプリートです。でも、何か良い方法を見つけたら教えてください。金持ちになる方法を教えます。

Answer 4

うーん..これはあなたの定義が何であるかに依存します。ハミルトニアン パスは確かに NP 完全です。ただし、エッジと頂点を複数回訪問できるハミルトニアン ウォーク (最後にウォーク ビットを追加する限り、ハミルトニアンと呼ばれます) は、O(p^2logp) または O(max(c^2plogp) で計算できます。 , |E|)) グラフが、ディラックが最初に予想し、高見沢が証明した特定の条件を満たしている限り。高見沢 (1980) 「グラフで短い閉じたスパン ウォークを見つけるためのアルゴリズム」を参照してください。

ポール

Answer 5

NP 困難であるため、最短のより良いアルゴリズムを見つけることはほとんどありません。しかし、あなたが試すことができるヒューリスティックがいくつかあります。おそらく、それらについては講義ノートを参照することをお勧めします ;) .

複雑さを軽減するには、貪欲なアルゴリズムを使用して短い (っぽい) ウォークを見つけることができます。

Answer 6

作業しているグラフがどのように生成されるかに応じて、貪欲なパス拡張を実行し、スタックしたときにランダムなエッジ スワップを実行することで、ランダムなインスタンスに対して予想される多項式時間を取得できる場合があります。

これは、ハミルトニアン ウォークを持つことが保証された、ランダムに生成された比較的まばらなグラフに対してうまく機能します。

Answer 7

My Query: グラフ G でハミルトン閉路を見つけるための検索問題 RHAM が自己可約であることを示す
SR={ x : R(x) ≠ ∅ }