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

Question

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

有没有办法转化问题，保证特定节点为起始节点，另一个节点为结束节点？

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

这种方法有什么大的缺点吗，或者有更好的方法吗？

Answer 1

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