旅行推销员和寻找最短路径有什么区别？

Question

我能想到的唯一区别是,在旅行商问题(TSP)中,我需要找到图中所有顶点的最小排列,并且在最短路径问题中,我们不需要考虑所有顶点.搜索州空间的最小路径长度路线可以任何人建议更多的差异.

Answer 1

您已经提出了本质区别:TSP是找到一个包含图中每个节点的排列的路径,而在最短路径问题中,任何给定的最短路径可能并且通常确实包含一个适当的子集图中的节点.

其他差异包括:

• TSP解决方案要求其答案为循环.
• TSP解决方案必然会在其路径中重复一个节点,而最短路径则不会(除非一个人正在寻找从节点到自身的最短路径).
• TSP是NP完全问题,最短路径是已知的多项式时间.

如果你正在寻找一个关于差异的精确陈述,我会说你只需要用更技术性和更精确的术语"简单循环访问图中的每个节点"来替换你对"permuation"的想法,或者更好,"Hamilton循环":

TSP要求人们找到覆盖图中具有最小权重的每个节点的简单循环(或者,具有最小权重的Hamilton循环).最短路径问题需要找到具有最小权重的两个给定节点之间的路径.最短路径不一定是哈密顿量,也不需要是循环.

Answer 2

使用最短路径问题,您可以考虑两个节点之间的路径.使用TSP,您可以考虑所有节点之间的路径.这使得后者更加困难.

考虑节点A和B之间的两条路径.一条在D上,另一条在C上.让C上的一条路径变长.在最短路径问题中,此路径可立即被丢弃.在TSP中,完全有可能这条路径是整个解决方案的一部分,因为您必须访问C并且以后访问它可能会更加昂贵.

因此,您无法在类似但较小的子问题中分解TSP.