使用回溯法解决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

我发现它是使用Bellman方程计算的，只是不知道如何操作。

任何帮助都将不胜感激！

- c4rrt3r

---

你的问题是不知道为什么3 -> 1 -> 2 -> 4 -> 5 -> 3这个循环的成本是37吗？还是你不知道如何进行回溯？ - Keegan Carruthers-Smith

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开始的路线。

（请注意，上述考虑仅在使用非负边缘成本时有效！）

- phimuemue