不考虑回到起点的旅行商问题（TSP）的问题名称是什么？
我想知道 TSP 的问题名称是什么，不考虑返回起点的方式，以及解决这个问题的算法是什么。
我研究了最短路径问题，但这不是我想要的，问题只是从 2 个指定点找到最短路径。但我要寻找的是我们给出n个点并且只输入1个起点的问题。然后，找到经过所有点一次的最短路径。 （终点可以是任何点。）
我还研究了哈密顿路径问题，但似乎不是解决我定义的问题，而是查找是否存在哈密顿路径。
I would like to know what is the problem name for TSP w/o considering the way of going back to starting point and what is the algorithm to solve this.
I looked into Shortest path problem but that is not what I am looking for, the problem only find the shortest path from 2 assigned points. But what I am looking for is the problem which we give n points and inputting only 1 starting point. Then, find the shortest path traveling all points exactly once. (end point can be any point.)
I also looked into Hamiltonian path problem but it seems not to solve my defined problem but rather find whether there is Hamiltonian path or not.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我在本书中找到了问题的答案。这与在计算机和其他数字系统的设计中反复出现的计算机布线问题相同。目的是最小化电线总长度。所以，它确实是最小长度哈密顿路径。
书中建议创建一个虚拟点，其与其他点的距离均为 0。因此，问题变成了 (n+1) 个城市对称 TSP。求解后，只需删除虚拟点，然后求解最小长度哈密顿路径，就可以得到TSP路径，而无需返回起点。
I've found the answer to my question in this book. It is the same with Computer wiring problem which occurs repeatedly in the design of computers and other digital systems. The purpose is to minimize the total wire length. So, it is indeed a minimum length Hamiltonian path.
What the book suggests is to create a dummy point whose distances to every other points is 0. Therefore, the problem becomes an (n+1)-city symmetric TSP. After solving, just delete dummy point and then the minimum length Hamiltonian path is solved and we can get the TSP path without returning back the start point.
如果我理解正确，您想要找到最短路径（从某个顶点开始）并遍历图中的所有节点，而不需要两次访问同一节点。一个更简单的问题是哈密顿路径问题。正如你所说，它询问是否存在这样的路径。由于该问题是 NP 困难的，并且它比您的问题更容易，因此解决您的问题至少是 NP 困难的。嗯，事实并非如此，因为您的问题不是决策问题。但它确实表明我们几乎可以确定没有多项式算法可以解决您的问题。
您可以采用近似法。这里有一个非常酷的 TSP 度量近似值：http://en.wikipedia.org/wiki /Travelling_salesman_problem#Metric_TSP。
If I understand correctly, you want to find the shortest path (that starts from some vertex s) and goes through all the nodes in the graph without visiting the same node twice. A simpler problem, is the hamiltonian path problem. It asks, like you said, weather there exists such a path or not. Since that problem is NP-hard, and it's easier than your problem, solving your problem is at least NP-Hard. Well, that isn't true because your problem is not a decision problem. But what it does say is that we can almost be sure that there is no polynomial algorithm for your problem.
You can resort to approximation. There is a pretty cool approximation for the metric TSP here: http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP.
使用非对称 TSP 求解器（如果有）
如果必须指定起始节点，如 @Vivek Payasi 提到的，
您可以构建一个典型的 TSP 问题，其权重除流入起始节点的弧外均正常。将它们的权重设置为 0。
这将产生不对称旅行商问题（ATSP）。
现在，如果您有一个精确的 ATSP 求解器，它将寻找最短的周期。
完成后，从解决方案中删除权重为 0 的弧。这看起来像是您正在寻找的路径。
*这一切都依赖于高效的 ATSP 求解器。
使用普通的对称 TSP 求解器代替
如果您想避免使用 ATSP 求解器，请参阅此答案：https://stackoverflow.com/a /59354134/7470152
底线是：修复起始节点&一个结束节点，添加一个虚拟节点，其弧连接到权重为0的两个节点，然后将其视为正常的TSP问题。
对所有 (n-1) 个末端节点重复此操作，并选择最短的一个。
Using Asymmetric TSP Solver (if any)
If a start node has to be specified, as mentioned by @Vivek Payasi,
you can build a typical TSP problem with weights otherwise normal except for the arcs that flow into the start node. Set their weights to 0.
This will produce an asymmetric travelling salesman problem(ATSP).
Now if you have an exact ATSP solver, this will look for the shortest cycle.
When it's done, remove the arc with weight 0 from the solution. This will look like a path you're looking for.
*All this relies on an efficient ATSP solver.
Using a plain Symmetric TSP Solver Instead
If you want to avoid using ATSP solver, refer to this answer: https://stackoverflow.com/a/59354134/7470152
The bottom line is: fix start node & an end node, add a dummy node whose arcs are connected to both node with weight 0 and then treat it like a normal TSP problem.
Repeat this for all (n-1) end nodes, and choose the shortest one.
使用具有虚拟点的对称 TSP 求解器
创建一个虚拟点，该点到起点的距离为 0，其他点的距离为大数（该“数字”应大于“图形的直径”），这样它应该始终是最佳的连接到起点的虚拟点。然后使用对称 TSP 求解器求解并从答案中删除虚拟点。
证明：想象一下最佳解决方案的虚拟点未连接到您的起点。然后，让我们构建另一个解决方案：我们采用相同的路径，但删除虚拟点并将其放置在起点与其任何邻居之间。那么路径的长度将被改变，
但
“number”> “图的直径”>=“虚拟点的第一个邻居之间的路径”，这给我们
-“数字”+“虚拟点的第一个邻居之间的路径”-“起始点的邻居和起点”< 0这意味着我们得到了更优化的解决方案。矛盾。这意味着虚拟点始终连接到起点。
Using Symmetric TSP Solver with dummy point
Create a dummy point that has 0 distance to start point and large number for distance for other points (this "number" should be greater than "diameter of graph") that way it should be always optimal for this dummy point to connect to your start point. Then use symmetric TSP solver to get solution and remove the dummy point from the answer.
Proof: Imagine optimal solution has dummy point not connected to your start point. Then let's build another solution: we take the same path but remove dummy point and put it between start point and any of its neighbours. Then length of the path will be changed by
but
"number" > "diameter of graph" >= "path between first neighbours of dummy point"which gives us
-"number" + "path between first neighbours of dummy point" - "path between neighbour of starting point and starting point" < 0that means that we got more optimal solution. Contradiction. That means that dummy point is always connected to the starting point.