algorithm - 不考虑返回起点的旅行商问题(TSP)的问题名称是什么？

Question

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

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

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

Answer 1

我在 this book 中找到了问题的答案.在计算机和其他数字系统的设计中反复出现的计算机布线问题也是如此。目的是尽量减少总线长。因此，它确实是一条最小长度的哈密顿路径。

书上建议创建一个虚拟点，其与其他点的距离为 0。因此，问题变成了 (n+1)-城市对称 TSP。求解后，只需删除虚拟点，即可求解最小长度哈密顿路径，无需返回起点即可得到TSP路径。