使用backtracking解決TSP問題

Question

我一直在試圖找出如何使用回溯解決TSP問題。 你如何計算「成本」？

矩陣：

∞ 20 30 10 11 
15 ∞ 16 4 2 
3 5 ∞ 2 4 
19 6 18 ∞ 3 
16 4 7 16 ∞ 

費用：

3 -> 1 -> 2 -> 4 -> 5 -> 3 cost = 37 
3 -> 1 -> 2 -> 5 -> 4 -> 3 cost = 59 
3 -> 1 -> 5 -> 2 -> 4 -> 3 cost = 50 
3 -> 1 -> 5 -> 4 -> 2 -> 3 cost = 62 
3 -> 1 -> 4 -> 2 -> 5 -> 3 cost = 28 
3 -> 1 -> 4 -> 5 -> 2 -> 3 cost = 36 

我發現它使用貝爾曼方程計算的，我只是不知道 來做到這一點。

任何幫助將不勝感激！

Answer 1

爲了計算成本，你只需要總結所有的邊緣成本。例如，對於路線3 -> 1 -> 2 -> 4 -> 5 -> 3，這會產生

(3,1) => 3 
(1,2) => 20 
(2,4) => 4 
(4,5) => 3 
(5,3) => 7 
------------ 
sum  37 

所以，本質上，你必須產生第一樣本路線並計算其成本。只要你這樣做，你就知道所產生的成本可能是一個最佳的解決方案。

如果您現在進行回溯，並且您遇到了成本較高的情況，那麼您知道這不會導致更好的路線，因此，您可以停止探索路線並向後退一步。

示例：您在第一次運行中發現路線1 2 3 4 5 6 7 8 9 1的成本爲40。現在，在一些回溯步驟中，您有一條路線的開始：1 2 4 5 6 ...並且看到到目前爲止，成本已經是41。這意味着，如果您探索以這些數字開頭的任何路線，則您的路線的費用將超過40，因此不是最優的！現在，你可以簡單地丟棄所有路線開始1 2 4 5 6。

（請注意，上述事項使用非負邊緣成本的工作只有！）