我有一系列图形坐标，我需要找到穿过它们的最短单向路径。我没有预定的开始/结束，但每个点只能被触摸一次，并且不需要返回到最佳原点。
我已经尝试了几种 TSP 方法，但它们似乎都基于最后返回原点，这在这种情况下给出了非常低效的结果。
Example
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
Notes:
是的，我尝试了搜索功能，有一个基本相同的问题算法：所有点之间的最短路径 https://stackoverflow.com/questions/2501732/algorithm-shortest-path-between-all-points然而，唯一真正的答案是 TSP，而闭路循环对此又是低效的。
它不需要 100% 准确，我已经有了一个排列方法，但它太慢了，我需要处理至少 ~25-30 个点，用一个好的近似值解决对我来说很有效
提前致谢。
Edit to clarify, TSP tends to solve as in img #1, my desired result is img #2
img 3 is the above sample solved via a TSP and img #4 is the desired (x coords shifted back -.5 for visibility)
Couple more for good measure #1 = TSP, #2 = desired
Basically i want the shortest chain connecting n points, using whichever start and end point is most efficient
由于您不关心寻找闭环 - 您所需要的只是一条路径 - 您可以对必须的点进行小的修改，以避免闭环的成本。为此，请添加一个新点，将其命名为 v，您将其定义为与所有其他点的距离为 0。现在，找到该图的 TSP 解。在某个时刻，您将进入然后离开 v。如果您采用循环，然后从中删除进出 v 的边，那么您将拥有一条仅访问每个节点一次的路径，而没有任何循环。
这仍然需要您求解或近似 TSP，但它消除了返回起点的巨大开销。
