我有一系列图形坐标，我需要找到一条通过它们的最短单向路径。我没有预定的起点/终点，但是每个点仅需触摸一次，并且不需要返回到最佳原点。
我已经尝试了几种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
笔记:
是的，我尝试了搜索功能，有一个基本相同的问题
Algorithm: shortest path between all points
然而，唯一真正的答案是TSP，这再次使闭合电路效率低下。
它不需要是100％准确的，我已经有了排列方法，但是它太慢了，我需要处理至少〜25-30点，并为我找到一个很好的近似值
提前致谢。
编辑澄清，TSP倾向于像img＃1中那样解决，我想要的结果是img＃2
img 3是通过TSP解决的上述示例，而img＃4是所需的(x坐标向后移-.5以提高可见性)
更好地结合，以更好地衡量＃1 = TSP，＃2 =理想
基本上我想用最短的链条连接n个点，无论使用哪个起点和终点都是最有效的
最佳答案
由于您不必在意找到一个闭环-您只需要一条路径即可-您可以对要点进行一些小的修改，以免产生闭环的成本。为此，添加一个新点，将其命名为v，您将其定义为与所有其他点的距离为0。现在，为该图找到一个TSP解决方案。在某个时候，您将输入v，然后离开v。如果您进行了循环，然后将边缘移入v或从v中移出，那么您将获得一条路径，该路径恰好一次访问每个节点而没有任何循环。
这仍然需要您解决或近似TSP，但是它消除了返回起点的巨大开销。
关于php - 通过多个节点的最短单向路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4780110/