如何确定旅行商问题中的起点和终点？
我有一个求解器，可以解决常规的对称TSP问题。该解决方案意味着通过所有节点的最短路径，而对路径中的第一个和最后一个节点没有限制。
有没有一种方法可以解决此问题，以便可以确保将特定节点作为起始节点，并确保另一个节点作为结束节点？
一种方法是在这些起点/终点之间的所有距离和所有其他节点之间的所有距离上加上一个I（很大的距离）（在起点与终点之间的距离加上I两次），因此求解器很想只访问它们一次（因此将它们作为路径的起点和终点）。
这种方法有什么大的缺点，还是有更好的方法呢？
回答：
您可以添加一个虚拟节点，该虚拟节点连接到权重为0的边的开始和结束节点。由于TSP必须包含该虚拟节点，所以最终结果必须包含序列开始-虚拟节点-
结束（没有其他方法可以达到虚拟节点）。因此，您可以获得具有指定起点和终点的最短汉密尔顿路径。即使图形中的边为负，此解决方案也应起作用。
以上是 如何确定旅行商问题中的起点和终点？ 的全部内容， 来源链接： utcz.com/qa/432734.html
