旅行推銷員 - 近似在線軟件？

Question

你們誰都知道解決方案能夠爲旅行商問題產生一個平庸的解決方案。我有3人打算訪問31個目的地......我不知道如何解決這個問題？

感謝所有 -

馬克西姆

Answer 1

我想你可以通過挑選任意點開始（如果未指定起點）嘗試貪婪的方法，然後在每一步你旅行到最接近你當前的點。假設點之間的距離可以在恆定的時間內計算出來，那麼你可以在O（n^2）時間內找到一條路徑。

爲了澄清，下面的僞代碼應該幫助（我沒有寫這種東西在一段時間，所以我希望這是不夠清楚）

Name: GreedyPath(C, p) 
Input: C - a non-empty collection of points to visit 
     p - a starting point in C 
Output: S - a sequence of points covering C 
Algorithm: 
    Remove p from C 
    If C is empty 
    Return the sequence containing only p 
    Else 
    Let p1 be the closest point to p in C 
    Let S = GreedyPath(C, p1) 
    Append p to the start of S 
    Return S 

顯然消耗部件的時間被找到每次最近點p，但對於n點，這應該只需要n(n-1)/2距離計算（除非我錯了）。

Answer 2

有幾個選項，包括：Nearest Neighbor,Christofides和Lin–Kernighan。

如果這些失敗，您可以隨時使用專家的code（免費給學術研究人員）。