algorithm - 旅行商问题中的起点和终点如何确定？

Question

我有一个求解正常对称 TSP 问题的求解器。该解决方案意味着通过所有节点的最短路径，不限制路径中的第一个节点和最后一个节点。

有没有办法转换问题，以确保一个特定的节点作为开始节点，另一个节点作为结束节点？

一种方法是将 I - 一个非常大的距离 - 添加到这些开始/结束节点和所有其他节点之间的所有距离（将 I 两次添加到开始和结束节点之间的距离），因此求解器很想只访问它们一次（从而使它们成为路径的起点和终点）。

这种方法有什么大的缺点，还是有更好的方法来做到这一点？

Answer 1

您可以添加一个虚拟节点，它连接到具有权重0的边的开始和结束节点。由于TSP必须包含虚拟节点，因此最终结果必须包含序列开始 - 虚拟节点 - 结束（没有其他方法可以达到虚拟节点）。因此，您可以获得具有指定起点和终点节点的最短哈密尔顿路径。即使图中的边缘为负，此解决方案也应该有效。

Answer 2

下面是“虚拟节点”概念的可视化。左边是一个正常的 TSP，具有相同的开始和结束节点 A，以及最优解 [A, B, E, D, C, A]。右边是同一个TSP，但是起始节点是A，结束节点是E。它的最优解[A,B,C,D,E]显然与正常情况下的那个没有关系。我们可以找到解决方案的方法是“破解” TSP 图的距离矩阵。在距离矩阵的底部插入虚拟节点，它到节点 A 和 E 的距离设置为 0，它到所有其他节点的距离设置为 inf。当求解器尝试搜索距离矩阵以找到节点 A、DUMMY、E 的最优序列时，将保持在一起，例如 [A, B, C, D, E, DUMMY, A]，然后可以清理给出 [A, B, C, D, E]。

PS。请注意，这种类型的 hack 会对精确求解器的性能产生严重影响。精确的 TSP 求解器设置有各种几何启发式，并且输入零距离和非距离距离显然会与此混淆。例如，我为协和飞机尝试了这个，但它对此并不满意，有时需要更多时间来找到最佳解决方案。没有找到任何文档来处理这种特定情况，但也许还有其他有能力处理这种特定情况的精确求解器。