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

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

我已经尝试了一些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
图3是通过一个TSP和IMG＃4解决了上述样品所期望的（X COORDS移回 - 0.5用于可见性）
enter image description here
夫妇更良好的措施＃1 = TSP，＃2 =期望

基本上我想的最短连接n个点，使用无论哪个起点和终点都是最高效的

来源

2011-01-24 stumped_coder

这与PHP有什么关系？您是否有要显示的代码代表节点和图形的结构？ – rik 2011-01-24 08:59:08

嗯，我猜它不直接与PHP相关，除了我更喜欢PHP解决方案，因为它是我希望它结束的语言（假设PHP可以在合理的时间内处理处理），但算法或一些体面的评论使用主要语言（C++，java，ruby等）编写的代码就足够了 – 2011-01-24 09:04:20

图形中的模式表示不需要路径_changing directions_。如何增加与（x2，y2）<（x1，y1）的链接的成本？它会将标准TSP算法偏向左上角附近的解决方案，并在右下角附近完成。 – Apalala 2011-01-25 15:45:04

这是all-pairs shortest path problem的一个实例，所有边的权重= 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为目的），以获得更好的性能。

来源

2011-01-24 09:07:20 rik

既然你不在乎找到一个闭环 - 你需要的只是一条路径 - 你可以对点进行小的修改以避免闭环的成本。要做到这一点，添加一个新的点，称之为v，你定义的点距所有其他点的距离为0。现在，为这个图找到一个TSP解决方案。在某个时候，你会进入然后离开v。如果你进行了这个循环，然后从它上面去掉v和v的边缘，那么你将有一条路径，每个节点只有一次没有任何循环而访问每个节点。

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

来源

2011-01-24 09:10:35 templatetypedef

有许多算法可以搜索图中最短的闭合路径。我认为把解决这个问题的算法之一（也叫做travelling salesman problem）适用于你的需求并不困难（路径应该是哈密尔顿方式而不是哈密尔顿循环）。销售员问题的一些众所周知的解决方案是Dijkstra算法和Prim算法。

来源

2011-01-24 09:11:16

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

回答

相关问题