算法在一個連接所有頂點的圖中找到最小權重的線性路徑

給定一個具有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.

貪婪的方法，我將不得不對所有的頂點爲出發點做到這一點。我不確定這個算法是否正確，並且它的複雜度很高。什麼應該是更好的方法來解決這個問題？

來源

2012-02-01 praveen

這個問題被稱爲是NP難從Hamiltonian path problem的減少，因爲如果你給所有的邊權重爲1，問「是有重量的最多n的線性路徑？」那麼如果圖形包含哈密爾頓路徑，那麼答案就是「是」。因此，你不可能找到比純暴力更好的算法，因爲除非P = NP，否則沒有多項式時間解決方案。

對不起，在你的遊行中下雨，並希望這有助於！

來源

2012-02-01 08:24:30 templatetypedef

路徑的權重不一定是1.我必須找到最小權重的線性路徑。需要探索的點數不大，可能不會超過100. – praveen 2012-02-01 08:27:51

@ praveen-爲了減少這個問題，我們只需要證明Hamiltonian Path的任何實例都可以被編碼爲這個問題的一個實例。在這裏，我們不需要使用問題的完整表達性，並且可以使用問題的更弱版本對其進行編碼。 – templatetypedef 2012-02-01 08:30:06

雖然我認爲@templatetypedef是正確的，並且這確實是哈密頓路徑問題的一個實例，但您可能會通過Google搜索旅行推銷員問題獲得更好的結果 - 它足夠接近以至於大多數（所有？）TSP啓發式都會爲你工作（唯一的區別是TSP至少通常被描述爲從頭到尾添加一條路徑，所以它形成一個「環」而不是一條線）。 TSP通常也假設一個完整的圖（即，每個節點彼此連接）;如果圖形不完整，您仍然可以使用常規算法，在任何未連接的節點之間添加無限重量的連接。

你給出的貪婪方法通常被稱爲「最近鄰居」啓發式。這是幾乎所有人都會遇到的第一種方法。它生產的非最佳解決方案在過去的一個世紀中已爲人所知。不幸的是，在合理時間內運行的其他任何東西至少也會產生次優解決方案（至少在對問題沒有限制的情況下）。 A *可能是在合理時間內產生合理（僅稍微不理想）結果的最常見算法。

來源

2012-02-01 09:36:31

_不幸的是，其他任何在合理時間內運行的東西至少也會產生次優解決方案的可能性_在實踐中並非總是如此，有[非常大的]（http://www.tsp.gatech.edu/pla85900/index.html）已知最佳解決方案的TSP實例。 – swen 2012-02-01 16:48:17

算法在一個連接所有頂點的圖中找到最小權重的線性路徑

回答

相關問題