A-l*_*bby 32 algorithm traveling-salesman np-hard graph-algorithm
我想知道TSP没有问题的名称是什么,考虑回到起点的方式以及解决这个问题的算法是什么.
我查看了最短路径问题,但这不是我想要的,问题只能找到2个指定点的最短路径.但我正在寻找的是我们给出n分并仅输入1个起点的问题.然后,找到所有点正好行进一次的最短路径.(终点可以是任何一点.)
我也研究了汉密尔顿路径问题,但似乎没有解决我定义的问题,而是找出是否存在汉密尔顿路径.
请指教我,谢谢!
A-l*_*bby 34
我在本书中找到了问题的答案.在计算机和其他数字系统的设计中反复出现的计算机接线问题也是如此.目的是最小化总线长度.因此,它确实是哈密尔顿路径的最小长度.
本书建议的是创建一个虚拟点,其与其他点的距离为0.因此,问题变为(n + 1) - 城市对称TSP.解决之后,只需删除虚拟点,然后求解最小长度哈密顿路径,我们就可以得到TSP路径而不返回起点.