1

我正在使用 Dijkstra 算法来求解理想路径。作为程序的一部分，该算法被调用了数千次。

超过一半的路径是不可能的，Dijkstra 需要很长时间才能解决这个问题（在一个小测试中，可能的路径总共需要 2 秒，而不可能的路径总共需要 25 秒。）

因此，我想知道是否有一种方法可以非常有效地检查是否有可能在浪费时间使用算法之前找到 2 个节点之间的路径。有没有非常有效的方法来做到这一点？

谢谢，丹

4

2 回答 2

1

无限制，一次性使用

在没有约束的图表上，程序以前从未见过（甚至以前的一部分），也不会再看到。您唯一能做的就是广度优先搜索或深度优先搜索。

如果内存是一个问题，您可以考虑使用增量深度优先搜索。

您可能会考虑在图表上启动多个线程以查看不同的分支。您需要进行协调，这样他们就不会通过拥有一个他们都可以安全地检查和写入的并发共享数据结构来重复工作。使用并发，您可以让一些线程从头到尾搜索，而另一些线​​程从头到尾搜索。

在带有循环的图上，您可能希望将节点标记为已访问，以免执行无限循环。

约束，一次性使用

想想你的图表和你的目标。

图是密集的还是稀疏的？

有负边权重吗？负和循环？

它遵循梯形规则吗？

是否有一个最大距离，您不在乎是否有路径？

图是非循环的吗？

图表“简单”吗？

通过一些工作，您可能能够找到一种比 dfs 更好的方法来处理您的图表。其他时候，您可能能够以不同的方式构建图表，从而使 dfs 更快。有时，优势可能来自不必在搜索期间存储尽可能多的数据。

约束，多用途

如果值得，您可以运行 Floyd-Warshall 来求解每对节点之间的最短路径。该算法需要一些时间，但是当您可以在关键部分中查找最短路径时，它可能会更有利。

您可以通过在图上执行初始 dfs 来预先求解连接的组件，而不是预先求解最短路径。

如果图表可以更改，但不会剧烈变化，您也许可以简单地修改预先计算的结果，而不是每次都从头开始。

最后的想法

图的大小和复杂性是重要的考虑因素。对于大型稀疏图或树，小型密集连接图的最佳算法将有所不同。

于 2013-04-14T01:13:18.343 回答
0

您是否在同一个图表上运行多个路径查找？如果是这样，您将需要从图表中维护一组不相交的连续空间。这可以通过以下方式实时完成：

  1. 从每个不成功的路径确定中维护连续空间，作为从起始节点开始的完整封闭集；
  2. 构建一个数据结构，一旦计算就可以有效地搜索连续空间；和
  3. 在每个路径确定之前确定起始节点和目标节点是否在相同的已知连续空间中、在两个不同的连续空间中或未知。

(2) 的精确最佳机制密切依赖于图表的性质，所以我把它留给另一个问题。

于 2013-04-13T23:06:45.613 回答