すべてのノードを訪問する最短経路

Question

私は非常に典型的なアルゴリズムを探していますが、共通の解決策はすべて少し違います。

無向グラフでは、すべてのノードを訪問する最短経路が必要です。ノードは再訪することができ、開始ノードに戻る必要はありません。

トラベリングセールスマン問題には、各ノードが一度しか訪問できず、パスが開始された場所に戻る必要があるという制限が追加されているようです。

最小限のスパニングツリーはソリューションの一部である可能性がありますが、そのようなアルゴリズムは最小限のパスではなく、ツリーを提供します。さらに、それらはツリーであり、したがってループを持たないので、ループがより効率的である可能性があるバックトラックを強制する。

Answer 1

グラフを変形することで、通常のトラベリングセールスマン問題に減らすことができます。

まず、すべてのノードのペアの最小距離を計算します。そのためにFloyd-Warshallアルゴリズムを使用することができます。あなたはそれを持っていたら、ちょうどエッジのuとVノード間の完全グラフを構築することはからUにV最小のコストです。

次に、ノードをもう一度見直す必要がないので、通常のTSPアルゴリズムを適用することができます。これはすでにエッジのコストに隠れています。