graph - 「最小スパンパス」を見つけるアルゴリズム?

Question

このコミックにインスパイアされたhttp://xkcd.com/173/

加重グラフの最小スパニング ツリーを見つけるためのアルゴリズムがたくさんあることは知っていますが、最小スパニング 'パス' を見つけることができるアルゴリズムを見つけるのに苦労しています。

コミックの場合、各ペアの関係に基づいてすべてのエッジに重みを付けると、社会的に最適な配置は最小スパン 'パス'、つまりすべての頂点にまたがるパスになります。誰でも助けることができますか？

Answer 1

最適なハミルトンパス（最適なパスカバーとも呼ばれます）を見つけることは難しい問題です。（ハミルトンパスが存在するかどうかを判断することは、NP完全問題です。）この学術論文では、とりわけ、最適なパスカバーアルゴリズムについて説明しています。これらの用語をWebで検索して、他のリソースを見つけることができます。すぐに利用できるコードはわかりません。

ちなみに、この質問（基本的にはあなたの質問の複製です）は、巡回セールスマン問題が出発点ではない理由を明確に説明しています。