一棵樹上的旅行推銷員

所以，我有N個節點和N-1條邊。因此，該圖可以表示爲一棵樹。現在，我需要找到到達每個節點至少一次所需的最小距離。 N的上限爲10^5。一棵樹上的旅行推銷員

有沒有辦法在合理的時間內做到這一點？這個問題可能有一個名稱，但如果是這樣，我找不到它。

我知道TSP是NP完全的。但是，由於這張圖是一棵樹，我想知道是否有解決這個問題的實際解決方案。

謝謝。

來源

2013-06-27 horace he

如果你結束你開始的地方，那麼我認爲你需要穿越每條邊恰好兩次。如果你能以不同的方式結束，那麼它更加有趣和複雜。 – Teepeemm

如果這是一棵樹，那麼深度優先或寬度優先tree traversal是訪問每個節點的簡單方法。這是一個O（N）操作。

如果它對你沒有任何影響，那麼使用深度優先遍歷，因爲它使用更少的內存，IMO更容易實現。

來源

2013-06-27 20:19:36

也許我錯過了一些東西，但是這是否會選擇最小的重量路徑？ –

@Ziyao Wei我可能誤解了這個問題，但如果它是一棵樹，那麼任何兩個節點之間只有一條路徑。我認爲他只是想要遍歷樹，但不知道術語是什麼。 –

我不知道，但我的理解是：考慮一棵樹有根，三個孩子爲根，路徑權重爲1，2，3。最小值應該是2 - > 1 - > 1 - > 3，但遍歷可以給你1 - > 3 - > 3 - > 2。也許我誤解了它的某個地方？ –

你可以做的是隔離圖中的週期，並將它們分組爲一個巨型節點。當你這樣做時，你應該有一個由你的節點組成的循環組的有向非循環圖。在dag中找到達到每條路徑的最短路徑很容易做到，因此此時唯一的辦法就是確保每個組的終點與您想要遍歷的組中的正確節點連接。

來源

2013-06-28 00:11:29

那麼我最終自己解決了這個問題。基本上，訪問節點中每棵樹的最短路徑將遍歷每條邊兩次，除了從原點到距離原點最遠的節點的路徑。所以，你使用一個dfs，並存儲最長的路徑。這是我的代碼。

long long dfs(int a, int b){ //a is the current node, b is the node you reached the current node from. 
ll ans=0; 
for(int i=0;i<elist[a].size();i++){ //elist is just a vector of all the edges. 
    int x=elist[a][i]; 
    if(x==b) continue;   //this checks to make sure you aren't going straight back to the previous node you visited. 
    ans=max(ans,cost[a][i]+dfs(elist[a][i],a)); //ans is the longest distance. Cost is an array of all the edge costs. 
} 
return ans;

}

來源

2013-06-29 23:49:24

一棵樹上的旅行推銷員

回答

相關問題