用回溯算法求解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开头的路由。

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