14

最小スパニング ツリー (重み付きグラフの場合) を見つけ、グラフにハミルトニアン パスがあるかどうか (ハミルトニアン サイクルの存在に依存する) を見つけるためのアルゴリズムを調べていました。私はすべてを台無しにしました。では、ハミルトニアン パスとスパニング ツリーの違いは何でしょうか? どちらもグラフのすべての頂点をカバーしています。スパニング ツリー (おそらく最小スパニング ツリー) を見つけるための効率的なアルゴリズムを使用できますが、ハミルトニアン サーキットを見つけるためのアルゴリズムを使用できないのはなぜですか?? サイクルに到達するまで、一度に 1 つのエッジを追加および削除し続けることができます。おそらく、ハミルトニアン サイクルを見つけることができますか??

4

4 に答える 4

10

2つの問題はかなり異なります。最小全域木は、道路を建設するのに 1 回の支払いで済み、何度でも使用できる場所を接続する問題と考えてください。任意の場所から任意の場所に移動できる最も安価な道路構成 (たとえば、クルスカルのアルゴリズムによる) を考え出すのは簡単です。

一方、ハミルトニアン サイクルでは、実際の移動距離を最小化する必要があります。つまり、ある場所から別の場所へのすべての移動がカウントされます。(同じ場所を 2 回訪れてはいけないとも言われていますが、それは些細なことです。) この問題は基本的に非局所的なものです。次のステップ。比較すると、貪欲な MST アルゴリズムは、すべてのステップでツリーに追加する正しい次のエッジを選択することが保証されています。

ところで、「HP の効率的なアルゴリズムはあり得ない」と言う人は誰もいません。まだ見つかっていないだけかもしれません:-)

于 2011-07-23T13:53:05.067 に答える
3

ハミルトニアン パスでは、ソースとシンクを除くすべての頂点の次数は 2 です。必ずしも MST (または必要に応じて ST) の場合はそうではありません。

于 2014-09-17T05:46:16.340 に答える
2

ハミルトニアン パス、特に最小ハミルトニアン サイクルは、旅行セールスマンの問題、つまり最短旅行を解決するのに役立ちます。高速なソリューションは、空間の複雑さを軽減し、効率的なアドレッシングのために使用する特別な種類の空間充填曲線も使用するヒルベルト曲線のように見えます。mst は、順序や交差に関係なく、すべての頂点を接続 (つまり、移動) するためのコストが最も低い方法で接続するようなものです。道路の検索、水路の検索、インターネット ケーブルの検索などの問題を解決するのに役立ちます。

于 2011-07-23T15:08:32.380 に答える