algorithm - 不考虑回到起点的旅行商问题（TSP）的问题名称是什么？

Question

我想知道 TSP 的问题名称是什么，不考虑返回起点的方式以及解决此问题的算法是什么。

我研究了最短路径问题，但这不是我要找的，这个问题只能从 2 个指定点找到最短路径。但我正在寻找的是我们给出 n 分并且只输入 1 个起点的问题。然后，找到通过所有点的最短路径恰好一次。（终点可以是任何点。）

我还研究了哈密顿路径问题，但它似乎没有解决我定义的问题，而是找出是否存在哈密顿路径。

Answer 1

我在这本书中找到了我的问题的答案。在计算机和其他数字系统的设计中反复出现的计算机布线问题也是如此。目的是最小化总导线长度。所以，它确实是一条最小长度的哈密顿路径。

这本书的建议是创建一个与其他点的距离为 0 的虚拟点。因此，问题变成了 (n+1)-city 对称 TSP。求解后，只需删除虚拟点，然后求解最小长度哈密顿路径，就可以在不返回起点的情况下得到TSP路径。

Answer 2

如果我理解正确，您想找到最短路径（从某个顶点 s 开始）并遍历图中的所有节点，而无需两次访问同一节点。一个更简单的问题，是哈密顿路径问题。就像你说的，它问天气是否存在这样的路径。由于该问题是 NP-hard，而且比您的问题更容易，因此解决您的问题至少是 NP-Hard。好吧，这不是真的，因为您的问题不是决策问题。但它确实说的是，我们几乎可以确定您的问题没有多项式算法。

您可以使用近似值。这里有一个非常酷的度量 TSP 近似值：http ://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP 。