通過所有在同一點處結束的垂直遍歷加權圖

Question

是否有一種算法可以讓我按照以下方式遍歷加權圖？

• 開始在特定的節點
• 經過圖中的所有vertecies
• 在最短的時間內量做到這一點（權重是次）
• 在起始節點

補完

Answer 1

聽起來像Travelling Salesman Problem給我。一個NP難題。沒有多項式時間算法可以爲您提供最佳解決方案。儘管如此，您可以使用搜索啓發式來獲得接近最佳解決方案。

Answer 2

我不確定，如果有任何有效的算法存在，但蠻力方法肯定會給你答案。

在任何情況下，你可以給頂點/邊的數量的約束。

Answer 3

正如Greg Sexton在我之前所說的那樣，這是旅行推銷員問題的一個典型例子。關於處理這種風格的問題，有許多先進的算法，這對您的特定情況而言是最好的，而取決於圖表。如果頂點的數量很高，則需要大量的計算能力才能在實際的時間範圍內完成。