如何從一個預先確定的頂點開始，至少從一個無向加權圖中找出訪問每個頂點的最低成本？

Question

所採用的路徑不必結束於預定的頂點。 基本上，旅行商問題除了一個頂點可以被訪問多次。

編輯：將有最多10000個頂點和邊

Answer 1

不知道這件事，但我認爲這是最佳的（也許不是最有效的思想）：計算每對點之間的最小路徑，然後在此圖上應用旅行推銷員。

Answer 2

由於在標準TSP定義中解決方案是哈密爾頓循環（或巡迴），因此它不一定是最優的。在實踐中，TSP是尋找最短旅程的優化問題，就像你描述的那樣。

問題仍然是NP-hard，並且它找到near-optimal解決方案的算法解決。這是您搜索「旅行推銷員問題的啓發式」（pdf）的結果之一。