我想知道 TSP 的问题名称是什么，不考虑返回起点的方式，以及解决这个问题的算法是什么。
我研究了最短路径问题，但这不是我想要的，问题只是从 2 个指定点找到最短路径。但我要寻找的是我们给出n个点并且只输入1个起点的问题。然后，找到经过所有点一次的最短路径。 （终点可以是任意点。）
我还研究了哈密顿路径问题，但似乎不是解决我定义的问题，而是查找是否存在哈密顿路径。
我在中找到了我的问题的答案这本书 https://rads.stackoverflow.com/amzn/click/com/0471904139。这与在计算机和其他数字系统的设计中反复出现的计算机布线问题相同。目的是最小化电线总长度。所以，它确实是最小长度哈密顿路径。
书中建议创建一个虚拟点，其与其他点的距离均为 0。因此，问题变成了 (n+1) 个城市对称 TSP。求解后，只需删除虚拟点，然后求解最小长度哈密顿路径，就可以得到TSP路径，而无需返回起点。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
