如何确定旅行商问题中的起点和终点？ [英] How to fix the start and end points in Travelling Salesmen Problem?

问题描述

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

I have a solver that solves normal symmetric TSP problems. The solution means the shortest path via all the nodes with no restriction on which nodes are the first and the last ones in the path.

有没有办法解决问题

一种方法是添加一个I-距离很大-到这些起点/终点节点与所有其他起点/终点之间的所有距离（起点和终点节点之间的距离加I两次），因此求解器倾向于仅访问它们一次（因此使它们成为路径的起点和终点） ）。

One way would be to add an I - a very large distance - to all distances between these start/end nodes and all the others (adding I twice to the distance between start and end node), so the solver is tempted to visit them only once (thus making them as the start and the end of the path).

此方法是否有任何重大缺点，或者有更好的方法？

Are there any big disadvantages of this approach, or is there a better way to do this?

推荐答案

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

You can add a dummy node, which connects to start and end node with edges with weight 0. Since the TSP must contain the dummy node, the final result must contain the sequence start - dummy node - end (there is no other way to reach the dummy node). Therefore, you can get the shortest Hamilton path with specified start and end node. This solution should work even if the edges in the graph are negative.

这篇关于如何确定旅行商问题中的起点和终点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！