帶有最大費用的加權無向圖中的頂點遊覽？

Question

如果我們需要從一個特定的頂點開始，那麼在帶有最大代價的帶權無向圖中尋找頂點遊程的有效算法是什麼？

Answer 1

它是NPC，因爲如果你設置所有邊的權重爲1，如果HC存在，它將成爲你的答案，所以你可以通過解決這個問題來解決這個問題，從單一來源找到HC存在。 NPC，但有一些多項式近似算法。

Answer 2

由於問題是NP難題，因此很難找到一種有效的算法來準確解決所有可能的加權輸入圖形問題。

然而，可能存在有效的算法，其可以保證找到最多可以離開最佳可能答案的恆定時間的答案，例如，可能會有一種有效的算法，可以保證找到一條重量至少爲最大重量路徑的1/2的路徑。

如果你有興趣尋找這樣的算法，你可以嘗試谷歌搜索「加權哈密頓路徑近似算法」，這是接近，但不是相同，你的問題。它不一樣，因爲哈密爾頓路徑需要包含所有的頂點。這是一個研究報告，可能要麼含有，或者導致的想法，你的問題的一個近似算法：由Michel X. Goemans和大衛

http://portal.acm.org/citation.cfm?id=139404.139468

「的約束森林問題的通用逼近技術」 P. Williams。當然，如果你的圖表足夠小以至於你可以枚舉所有可能的包含你想要的頂點的路徑，「足夠快爲你的目的」，那麼你可以準確地解決它。