小编stu*_*der的帖子

我有一系列图形坐标,我需要找到最短的单向路径.我没有预定的开始/结束但是每个点只能触摸一次并且不需要返回到最佳原点.

我尝试了几种TSP方法,但它们似乎都是基于最终返回到原点,在这种情况下会产生非常低效的结果.

例

1,13
3,0
3,7
2,21
2,11
3,12
1,19
3,6

会解决

3,0
3,6
3,7
3,12
2,11
1,13
1,19
2,21

笔记:

是的我尝试了搜索功能,有一个基本相同的问题 算法:所有点之间的最短路径 然而唯一真正的答案是TSP,再一次,闭合电路效率低下.

它不需要100%准确,我已经有一个排列方法,但它太慢了,我需要处理至少~25-30点,安顿好的近似对我有用

提前致谢.

编辑澄清,TSP倾向于解决,如img#1,我想要的结果是img#2
img 3是通过TSP解决的上述样本,img#4是所需的(x coords向后移动-.5为可见性)

多做好措施#1 = TSP,#2 =期望

基本上我想要连接n个点的最短链,使用最有效的起点和终点