algorithm - 使用回溯法解决 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 开头的路由。

(请注意，上述注意事项仅在使用非负边成本时才有效!)