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

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

笔记:

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

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

提前致谢.

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

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

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

Answer 1

这是所有边的权重=1 的所有对最短路径问题的一个实例。您将在链接页面上找到常见的解决方案，例如 Dijkstra 算法或 A-star 算法。
一种简单的方法是迭代节点并找到到每个其他节点的最短路径。

$paths = array();
foreach ($nodes as $start) {
    foreach ($nodes as $end) {
        if ($start !== $end) {
            $path[$start][$end] = findShortestPath($graph, $start, $end);
        }
    }
}

在更复杂的方法中findShortestPath，会记住先前运行的子路径（或用于$paths此目的）以获得更好的性能。