すべての頂点を一度正確に結ぶグラフの最小重みの直線パスを求めるアルゴリズム

Question

n個の頂点を持つ重み付け無向グラフを考えると、 の各頂点を結ぶ最小ウェイトのパスを見つける問題に直面するライン。 最初は、これが最小スパニングツリーを見つける問題だと思った しかし、これは当てはまりません。スパニングツリーの場合には、頂点に枝番号 があるか、次数が2より大きくなることがあります。私が見つけ出す必要があるのは、 線形パスです。つまり、終点の頂点を除くすべての頂点は、度数がちょうど2です。 開始点と終了点はn個の頂点のいずれかになります。

鉱山は、私が出発点として、すべての頂点のためにこれを行う必要があります

first chose any vertex, maintain a sum 
    check all its neighbors such that the cost of reaching it is 
    least among all the neighbors 
    mark this neighbor as visited 
    add the cost to sum 
repeat the procedure above until all the points have been visited. 

すなわち貪欲なアプローチでした。 このアルゴリズムが正解で、複雑さが高いかどうかはわかりません。 この問題を解決するにはどうすればよいでしょうか？

Answer 1

この問題は、すべてのエッジの重みを1にして「最大でnの線形パスがあるのですか」と質問すると、Hamiltonian path problemからのNP-グラフにハミルトニアンパスが含まれている場合、答えは「はい」になります。その結果、P = NPが多項式時間解を持たない限り、純粋なブルートフォースよりも優れたアルゴリズムを見つけることはまずありません。

あなたのパレードに雨が降って申し訳ありませんが、これが役立つことを願っています！

Answer 2

@templatetypedefは正しいと思いますが、これは実際にハミルトニアンパスの問題のインスタンスです。セールスマンの問題を解決するためのグーグルでは、おそらくより良い結果になるでしょう。ほとんどの（すべて？）TSPヒューリスティックは、 TSPは少なくとも通常は最初から最後までのパスを追加するものとして記述されているため、単なる行ではなく「リング」を形成します。 TSPは、通常、完全なグラフを仮定する（すなわち、すべてのノードがお互いに接続する）。グラフが完成していない場合は、接続されていないノード間に無限大の重み付けの接続を追加して、通常のアルゴリズムを使用することができます。

あなたが与えた貪欲なアプローチは、一般に「最近隣」発見的手法として知られています。ほぼすべての人に起こる最初のアプローチです。その最適ではない解決策は、1世紀以上にわたって知られています。残念なことに、妥当な時間に実行されるものは、少なくとも少なくとも最適解を生成する可能性もあります（少なくとも問題の制限がない場合）。 A *はおそらく合理的な時間内に妥当な（ほんのわずかしか最適でない）結果を生成するための最も一般的なアルゴリズムです。