php - 通过多个节点的最短单向路径

Question

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

我尝试了几种 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 个点的最短链，使用最有效的起点和终点

Answer 1

由于您不关心找到闭环 - 您只需要一条路径 - 您可以对必须的点进行小的修改以避免闭环的成本。为此，添加一个新点，将其称为 v，您将其定义为与所有其他点的距离为 0。现在，为这个图找到一个 TSP 解决方案。在某个时候，您将进入然后离开 v。如果您进行循环，然后从中删除进出 v 的边，那么您将拥有一条路径，该路径仅访问每个节点一次而没有任何循环。

这仍然需要您解决或近似 TSP，但它消除了返回起点的巨大开销。