無向グラフでハミルトン閉路を見つけるための動的計画法アルゴリズムとは何ですか？O(n.2^n)時間計算量のあるアルゴリズムが存在することをどこかで見ました。
13964 次
2 に答える
35
ハミルトン閉路を見つけるためのO（n2 n）動的計画法アルゴリズムが実際にあります。O（n 2 2 n）またはO（n2 n ）への多くのO（n！）バックトラッキングアプローチを減らすことができる一般的なアイデアです（より多くのメモリを使用することを犠牲にして）、セットであるサブ問題を検討することです指定された「エンドポイント」を使用します。
ここでは、サイクルが必要なので、任意の頂点から開始できます。修正して、それを呼び出しますx。サブ問題は次のようになります。「の特定のセットSと頂点vに対して、のすべての頂点で始まり、それを通り、？で終わるSパスはありますか？」これを、たとえば、と呼びます。xSvposs[S][v]
ほとんどの動的計画問題と同様に、サブ問題を定義すると、残りは明白です。頂点の2 nセットSをすべて「増加」順にループし、そのような各Sの各vについて、次のように計算できますposs[S][v]。
poss [S] [v] =（
uposs [S− {v}] [u]がTrueであり、エッジu->vが存在するようなものがSに存在します）
v最後に、エッジv->xが存在し、poss[S][v]Trueであるような頂点がある場合、ハミルトン閉路があります。ここSで、はすべての頂点のセットです（x定義方法によって異なります）。
存在するかどうかを判断するだけでなく、実際のハミルトン閉路が必要な場合は、TrueまたはFalseだけでなく、それを可能にしposs[S][v]た実際のサイクルを保存します。uそうすれば、最後のパスをさかのぼることができます。
于 2009-09-07T06:28:14.260 に答える
2
その特定のアルゴリズムを引き出すことはできませんが、ハミルトニアンページにはハミルトニアンサイクルについて、おそらく必要以上に多くのことがあります。:)
このページは、ハミルトン閉路問題とハミルトン閉路問題、およびいくつかの関連する問題についてインターネット上で入手可能な論文、ソースコード、プレプリント、テクニカルレポートなどの包括的なリストとなることを目的としています。
于 2009-09-07T06:12:30.657 に答える