可以通过查找图的最小生成树来解决TSP问题

Question

我们可以通过查找有节点是要访问的城市的有向图的最小生成树来解决旅行商问题,权重是城市之间的距离吗？定向图只是为了考虑距离(城市-A,城市-B)!=距离(城市-B,城市-A)的情景.

Answer 1

最小生成树问题要求您构建连接所有城市并且总重量最小的树,而旅行商问题要求您查找以最小总重量访问所有城市的旅行(并且可能返回到您的起点) .

如果您在查看差异时遇到困难,在MST中,您需要在加权图中找到最小权重树,而在TSP中,您需要找到最小权重路径(或周期/电路).这有帮助吗？

Answer 2

这是之间的区别

找到G 的非循环连通子图T，其中 V(T) = V(G) 且权重(T) 最小

和

在 G 中找到一个循环C，使得 V(C) = V(G) 且权重 (C) 最小

其中 Weight(X) = X 的边之和。正如您所看到的，这两个问题非常不同。

然而，两者之间存在着某种关系。如果图权重满足三角形不等式，则可以使用 MST 在 x2 的范围内近似 TSP：计算 MST，然后（从任意根）遍历它并按前序返回顶点。您可以在 G Laporte 的《旅行商问题：精确算法和近似算法概述》中找到该近似值（以及其他近似值）的详细分析- 欧洲运筹学杂志，1992 年 - 爱思唯尔。