小编stu*_*der的帖子

我知道这是一个相当频繁的问题(一般来说是tsp),但我已经被它困住了一段时间了.我希望在给定一组x,y坐标的情况下找到最小距离哈密顿路径.起点和终点完全是任意的,但它不能循环,所以标准的tsp出来了(虽然假设在0距离处向所有其他节点添加一个虚拟点,然后在以后删除它有效,我不知道我是怎么做的).

有很多链接到数学论文等讨论算法来解决类似的问题,但我宁愿使用代码而不是复杂的方程式,我真的宁愿不重新发明轮子.

当然,在主要语言java,c#,c ++,ruby,javascript,php等中有一个相当简单的实现,它可以解决我的问题的~20节点版本.

编辑:我也在寻找尽可能准确,显然它不能完全准确为20!有很多排列,但是等于或优于人类在几分钟内可以做的事情将是完美的.

编辑2:另外澄清一下,我正在使用未加权图上的标准二维坐标.距离A-> B == B-> A.

编辑3: 为了消除混淆,这里有一个视觉示例,只有几个点来说明tsp如何不是最理想的(这种情况是一个简单的修复,但有更多的节点,它可能更极端).

TSP减去最长段(红线)

期望的输出