旅行商查詢

Question

我已經閱讀了近似的TSP之一是做到以下幾點： - 計算的最小生成樹（MST） - 執行的解決的MST

目標一個DFS TSP是每個頂點只被訪問一次。旅行者從'A'點開始，他需要訪問圖表上的所有其他點並回到'A'點（有時候，這個子句不存在），確保每個點只訪問一次。

假設MST圖G是作爲 'T' 如下：

此MST的DFS是A-B-C-E-d。

我的問題是爲了解決TSP，我需要旅行者必須訪問的所有城市（點）的列表。顯然，在MST中不存在從'E'到'D'的路徑。那麼這是如何解決問題的？

Answer 1

只要在原始圖中存在從E到D的路徑，在MST中是否存在從E到D的路徑並不重要。通常TSP包含一個完全連通的圖。本文的更多信息

見第2.1節： http://www.cs.tufts.edu/~cowen/advanced/2002/adv-lect3.pdf