最小生成树和旅行商问题有什么区别？

Question

我们能否通过寻找最小生成树来解决旅行商问题？

- Ouais

---

它们之间存在联系：它们都在寻找一种使用最小边权连接图中所有顶点的方法。不同之处在于，最小生成树(MST)寻找一棵树，而旅行商问题(TSP)寻找一条路径。 - Peter Alexander

康拉德·鲁道夫，那是错误的 - 存在联系，并且问题是有意义的： https://www.ics.uci.edu/~eppstein/161/960206.html “最小生成树可以用于近似解决旅行商问题”，这是一个不那么明显的应用。 - volzotan

所以，对于这个问题的答案是： 不完全是，但你可以使用MSP近似地解决TSP问题: https://www.ics.uci.edu/~eppstein/161/960206.html "[...] 如果您绘制沿着最小生成树的路径，您会重复访问每条边并访问所有点，因此TSP权重小于两倍的MST权重。 因此，此旅行路线在优化方面的表现比最优解至少好一倍" - volzotan

MST是TSP问题的一种简化形式，因此您可以将MST解决方案用作TSP的启发式函数，因为它总是估计比实际解决方案更少成本的解决方案。你问题的答案是“不”。你不能使用MST解决方案来解决TSP问题。 - Sadiq

不，在TSP中，每个顶点只被访问一次，而在MST中，每个节点可能被访问多次。换句话说，在TSP中，节点的度数为2，但在MST中，节点的度数可能大于2。 - hojjat.mi

Answer 1

最小生成树问题要求你构建一棵连接所有城市且总权值最小的树，而旅行商问题则要求你找到一条访问所有城市且总权值最小（可能会回到出发点）的路径。

如果你很难看出区别，在最小生成树中，你需要在带权图中找到一个最小权重的树，而在旅行商问题中，你需要找到一条最小权重的路径（或者环路/回路）。这有所帮助吗？

- Anthony Labarre

---

如果顶点之间只有一条路径，那么它是否会变成TSP问题？ - Sumit Gupta

Answer 2

这是两个问题之间的区别：

找到图G的一个无环连通子图T，使得V(T) = V(G)，且权值Weight(T)最小

与

找到图G中的一个循环C，使得V(C) = V(G)，且权值Weight(C)最小

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

然而，它们之间有一个关系。如果图的权重满足三角不等式，可以使用MST近似TSP的解决方案，近似因子为x2：计算MST，然后从任意根开始遍历它，并以预序方式返回顶点。您可以在旅行推销员问题：G Laporte撰写的精确和近似算法概述 - 欧洲运营研究杂志，1992年 - Elsevier中找到此近似（以及其他近似）的详细分析。

- Yakov Galka