找到'最小生成路徑'的算法？

我知道有很多算法來找到一個加權圖的最小生成樹的啓發，但是我一直在努力尋找任何可以找到的最小生成樹「路徑」。

對於漫畫，如果我們基於每對關係對每個邊進行加權，那麼社會最優排列將是最小跨越「路徑」，即跨越所有頂點的路徑。誰能幫忙？

2012-05-24 user31527

這與尋找最小[哈密頓路徑]（http://en.wikipedia.org/wiki/Hamiltonian_path）有什麼不同？ –

正確的觀察當然。另一個相關問題複雜程度不同的有趣案例：MST = easy，MSP/HP = hard。 –

如果您可以對社會約束做出一些假設，您可以使用修改的huffman算法解決此問題。 –

找到最佳哈密頓路徑（也稱爲最佳路徑覆蓋範圍）是一個難題。（確定是否存在任何哈密頓路徑是NP完全問題。）This scholarly article討論了其中最優路徑覆蓋算法。您可以在網上搜索這些術語來查找其他資源。我不知道任何現成的代碼。

順便說一句，this question（這基本上是你的副本）清楚地解釋了爲什麼旅行推銷員問題不是開始的地方。

2012-05-24 00:27:49

回答