訪問所有節點而不返回開始的最短路徑

Question

假設我們有一組任意節點，並且我們希望節點之間的最短路徑與我們必須訪問圖中的所有節點。這是一種旅遊推銷員問題，但不會再回到起始節點。假設我們可以從任意節點開始，並在任意節點（除了起始節點）結束，但我們必須訪問圖中的所有節點。複雜性與旅行推銷員問題一樣，即NP難度？有沒有已知的算法來解決這個問題？

Answer 1

這仍然是TSP，並且是NP-Hard。在TSP上運行的算法也適用於此。請注意，「不關心」起始節點的事實並不重要，因爲通過嘗試所有可能性，您將複雜度乘以n。

從Hamiltonian Path Problem這個問題的減少是相當瑣碎：

給定圖G=(V,E)，創建一個新的加權圖與G'=(V,E',w)，其中：

E' = V x V (all edges are there) 
w(u,v) = 1 if (u,v) is in E 
w(u,v) = 2 else 

現在，原圖G有哈密頓當且僅當穿過所有頂點的最短路徑的長度爲|V|。