5

问题：在未加权的无向图中找到最短路径。

广度优先搜索可以找到两个节点之间的最短路径，但这可能需要 O(|V| + |E|) 时间。预先计算的查找表将允许在 O(1) 时间内回答请求，但代价是 O(|V|^2) 空间。

我想知道的是：是否有一种算法可以提供更细粒度的时空权衡？换句话说，是否有一种算法：

  1. 在比 O(1) 更多的时间内找到最短路径，但比双向广度优先搜索更快
  2. 使用比 O(|V|^2) 占用更少空间的预计算数据？

在实际方面：该图有 800,000 个节点，被认为是一个小世界网络。全对最短路径表的数量级为千兆字节——这在当今并不离谱，但它不符合我们的要求。

但是，出于好奇，我问我的问题。让我彻夜难眠的不是“我怎样才能减少所有对查找表的缓存未命中？”，而是“那里有我从未听说过的完全不同的算法吗？”

答案可能是否定的，没关系。

4

2 回答 2

1

看起来您的输入集必须非常大，如果查找表太大而无法存储在磁盘上。我假设那时数据将不适合 RAM，这意味着您使用的任何算法都应该进行调整以最小化读取和写入的数量。每当涉及磁盘时，空间 == 时间，因为写入磁盘非常慢。

您应该使用的确切算法取决于您拥有的图表类型。您可能会对这篇研究论文感兴趣。完全披露：我自己没有读过它，但它似乎可能是你正在寻找的东西。

编辑：

如果图（几乎）是连通的，即小世界网络，则查找表不能小于 V^2。这意味着所有查找都需要磁盘访问。如果边缘适合主存储器，那么每次只计算路径可能会更快。否则，您可能会从包含所有最短路径长度的表中计算路径。您可以从该表重建路径。

关键是要确保表中在任一方向上彼此靠近的条目在磁盘上也彼此靠近。这种存储模式实现了：

1 2    1   2  5  6
3 4    3   4  7  8
       9  10 13 14
       11 12 15 16

它也适用于缓存层次结构。

为了计算表，您可以使用修改后的Floyd-Warshall，在其中以块的形式处理数据。这将使您能够在合理的时间内执行计算，尤其是在并行化计算的情况下。

于 2010-04-27T20:55:47.070 回答
1

您应该首先查看Dijkstra寻找最短路径的算法。a* 算法是一种变体，它使用启发式算法来减少计算起始节点和目标节点之间的最佳路径（例如欧几里得距离）所花费的时间。您可以修改此启发式以提高性能或准确性。

于 2010-04-27T20:48:22.013 回答