解決旅行推銷員一旦你知道最短路線的距離

我想解決TSP (Travelling Salesman Problem)，但不是以傳統的方式。我正在執行這些步驟。解決旅行推銷員一旦你知道最短路線的距離

1）首先，我改變TSP到真/假問題。

現在這個問題的定義是：「所有城市的總路程是否小於或等於k？假設我有一個算法TSP_tf(k)來解決它。

2）然後我查詢的最小ķ。

這是，我搜索「哪個是最短路線的距離」。

一個有效的算法來解決它將與二分搜索。我從k=1開始，我打電話TSP_tf(k)。如果它返回false，我將k乘以2，並且一直呼叫TSP_tf，直到返回true。發生這種情況時，搜索最小k，在區間(k/2 - k]中返回true，並使用二分搜索進行搜索。

我會得到那麼最小距離min_k。

3）返回TSP的最短路線知道其距離爲min_k。

這裏是我的問題來了。如何解決這個問題是一個有效的算法？通過高效率我的意思是一個好方法:)很明顯，TSP將仍然是NP。

來源

2016-09-27 Santiago Gil

我認爲這對我們來說有點過於寬泛。也許[cs.se]會願意接受這一點，但即使他們可能想要一些更具體的開始。我不確定你的目標實際上是什麼，因爲所有三個步驟都是（我認爲）NP。 – Teepeemm

將'min_k'提供給ILP模型將允許您修剪很多，但詳細解釋該方法需要整本書。 – harold

我投票結束這個問題作爲題外話，因爲它是關於計算機科學，不適用於編程。 [已轉載到計算機科學]（http://cs.stackexchange.com/q/64037）。（將來，[請不要這樣做]（http://meta.stackexchange.com/q/64068），[flag]（http://stackoverflow.com/help/privileges/flag-posts）您的問題請求遷移。） – Gilles

我終於設法解決它。

假設我們有一個圖表g，它代表了城市及其TSP的連線。一個節點代表一個城市，一個加權邊緣表示兩個城市之間存在一個連接，並與其相應的距離有關。

爲了在給定距離的情況下獲得最短路線，我們刪除一對一的邊，並查看它們是否是最短路線的一部分。我們怎麼能知道它？如果我們刪除圖中的邊e我們稱之爲TSP_tf與已知的最短距離min_k，有兩種情況：

TSP_tf(min_k) == false。這是，刪除e使得無法獲得與min_k距離的路線。 e是最短路線的一部分。
TSP_tf(min_k) == true。如果沒有連接e，仍然可以獲得具有相同最小距離的路線。 e不參與最短路線。

如果我們逐步將其應用到圖形的所有邊，我們可以得到精確的最短路徑（或更好說，最短的路線之一，因爲可能有不止一個解決方案）。

// min_k is the distance of the shortest path of the TSP represented by the graph g. 
Graph TSP(Graph g, int min_k) 
    Graph shortestPath = g; 
    For (Edge e in g) 
     // Delete the edge e. 
     shortestPath -= e; 
     // e is part of the shortest path. 
     If (TSP_tf(shortestPath, min_k) == false) 
      shortestPath += e; 
     EndIf 
    EndFor 
    Return shortestPath; 
EndTSP

我們知道，圖的節點的最大數目爲1/2 * |V| * |V-1|，是|V|節點的數量。對每個節點完成呼叫，所以對TSP_tf的呼叫的數量具有峯值O(|V|^2)，這是高效的算法。

來源

2016-10-14 18:05:36

您的TSP_tf是通常所說的決策問題版本。該問題是NP完整的，請參閱https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computational_complexity進行驗證。所以你不應該希望它會很容易處理。

也就是說，同樣的維基百科文章有大量關於在實踐中解決TSP問題的驚人有效方法的信息。

來源

2016-09-27 21:13:41 btilly

是的我知道這個術語，但用我的語言，而不是英文。感謝您的鏈接，聽起來很有趣，但是現在我想用這種方式解決問題，只是爲了好奇。 –

解決旅行推銷員一旦你知道最短路線的距離

回答

相關問題