5

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

我尝试了几种 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 坐标向后移动 -.5 以提高可见性
在此处输入图像描述 在此处输入图像描述 在此处输入图像描述 在此处输入图像描述
） more for good measure #1 = TSP, #2 = desired
在此处输入图像描述 在此处输入图像描述
基本上我想要连接 n 点的最短链，使用最有效的起点和终点

4

3 回答 3

3

这是所有边的权重 = 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-24T09:07:20.227 回答
3

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

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

于 2011-01-24T09:10:35.453 回答
0

有许多算法可以搜索图中的最短闭合路径。我认为根据您的需求调整解决该问题的算法之一（也称为旅行商问题）并不难（路径应该是汉密尔顿方式而不是汉密尔顿循环）。一些著名的推销员问题解决方案是 Dijkstra 算法和 Prim 算法。

于 2011-01-24T09:11:16.820 回答