graph-algorithm - 完全なグラフでの最も安いコスト トラバーサル

Question

nノード（重みが異なる）の完全に接続されたグラフが与えられた場合...ノードA（開始ノード）から他のすべてのノードに移動して戻るための最も安価なサイクルを提供するアルゴリズムがあるかどうか疑問に思っていましたノードAへ？これを達成するためにプリムのようなアルゴリズムを変更する方法はありますか?

ご協力いただきありがとうございます

編集：私は無向グラフを扱っていることを忘れていたので、各頂点のイン度=アウト度です。

Answer 1

ダイクストラを変更して、他のすべてのノードへの最短経路を見つけ、それを見つけたら、Aに戻る最短経路を見つけることはできませんか？

Answer 2

そのようなパスが存在する必要はありません。すべてのノードのイン次数がそのアウト次数と等しい場合にのみ存在します。

必要なのは、最も安価なオイラー パスです。それを見つける問題は、巡回セールスマン問題と呼ばれます。それを解決するための高速なアルゴリズムはありません。

編集：再考：巡回セールスマン問題は、すべてのノードを1回だけ訪問するツアーを検索します。すべてのノードを少なくとも 1 回訪問するツアーを求めています。したがって、あなたの問題は単に P にあるのかもしれません。

Answer 3

反復深化 A スター検索アルゴリズムを試すことができます。常に最適です。ただし、ヒューリスティックを定義する必要があります。これは、解決しようとしている問題によって異なります。