algorithm - すべてのノードへの非サイクルパス

Question

任意の開始ノードから最短の歩行距離を見つけて、すべてのノードが重みのある無向グラフで訪問されるようにするアルゴリズムまたはアルゴリズムのセットはありますか？ノードが複数回訪問されてもかまわないので、巡回セールスマンではありません。（最初に戻っても問題ありません。すべてのノードを訪問するのに最後に必要なノードである限り、ウォーカーは遠くのノードに到達する可能性があります。）これは最小スパニングツリーではありません。 A-> B-> C-> A-> Dに行くことは、A、B、C、およびDを訪問するための（一意ではない）最短経路である可能性があるためです。私の直感では、これはそうではないと言っています。 NP問題をそれほどトリッキーにする制限がないため、かなりNP問題です。もちろん、私は完全に間違っている可能性があります。

Answer 1

巡回セールスマン問題に関するウィキペディアの記事から：

各都市を「1回だけ」訪問する条件を削除しても、NP困難は削除されません。平面の場合、各都市を1回だけ訪問する最適なツアーがあることが簡単にわかるためです（そうでない場合は、三角不等式によるショートカット）。繰り返しの訪問をスキップしても、ツアーの長さは増えません）。

Answer 2

すでに受け入れられている回答を含む質問に回答を追加するエチケットが何であるかわからない。

別のページにジャンプする必要がなく、平面グラフや三角不等式を処理する必要がなく、これが単純でおそらく理解しやすいという事実のために、この回答を追加しています。

ハミルトン閉路問題は次のように減らすことができます。

すべての頂点を訪問する最小の重みの歩行を見つけるという問題を解決するために、多項式時間アルゴリズムがあるとします。

ハミルトンパスが存在するかどうかを判断する必要があるグラフが与えられた場合、エッジの重みを1に設定して、そのまま問題のアルゴリズムにフィードします。アルゴリズムが値> n-1を返す場合、元のグラフにはハミルトン経路はありません。そうでない場合はあります。

したがって、この問題はNP困難です。