12

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

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

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

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

4

2 回答 2

19

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

于 2013-01-25T18:40:10.113 回答
3

下面是“虚拟节点”概念的可视化。左边是一个正常的 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 求解器设置有各种几何启发式,并且输入零距离和非距离距离显然会与此混淆。例如,我为协和飞机尝试了这个,但它对此并不满意,有时需要更多时间来找到最佳解决方案。没有找到任何文档来处理这种特定情况,但也许还有其他有能力处理这种特定情况的精确求解器。

于 2019-12-16T09:52:33.460 回答