3

这可能是一个可能没有最佳解决方案的问题。假设我有一个有向图，不知道它是否有任何循环（循环检测将是这个问题的一个方面）。给定一组顶点（可能是数百万个顶点），我需要计算给定图的所有唯一对之间的所有不同路径（没有重复顶点的路径）。我将如何处理这种情况？

让我们看一个蛮力的方法来做到这一点：

  • 从图中计算所有可能的对。

  • 对于每对图，使用 DFS 获取从 Source 到 Destination 的所有路径。

  • 假设这些对在哈希表中表示，将路径计数作为该对的值。
  • 对其余的对重复此操作。

人们能指出哪些事情可能会出错吗？让我们以这种方式思考这个问题，找到地球上所有城市之间的所有不同路径的计算挑战是什么？如果甚至尝试解决这个问题，应该从哪里开始？

编辑：提出的一些算法在 O(n!) 阶乘时间内产生结果。对于资源有限的单台机器来说，这是一个令人生畏的计算。有谁知道 map-reduce 技术可以将图遍历的问题分解成更小的块？

4

3 回答 3

3

你有没有想过这样的路径可以存在多少？

在具有 V 个顶点的此类图中，您有大约 V^2 对不同的对。让我们想象一个最坏的情况，你有一个完整的图（每对之间都存在边）。路径可以有 1 条边和 V-1 条边之间的任何位置，因为您不允许路径中有重复的顶点。

每对顶点之间：

  1. 只有一条路径有 1 条边；
  2. 有 2 条边的 V-2 路径：使用任何不是起点或终点的中间顶点；
  3. 有 (V-2)(V-3) 条具有 3 条边的路径：使用任意两个不同的中间顶点；
  4. 有 (V-2)(V-3)(V-4) 条路径，有 4 条边；
  5. 有 prod{k=1 -> n-1}(Vk-1) 条具有 n 条边的路径。

鉴于此，我们知道有 V 的图最多有 V^2*sum{i=1 -> V-1}(prod{k=1 -> i-1}(Vk-1)) 个总路径顶点。

因此路径总数为 P(V) = V^2*sum{i=1 -> V-1}(prod{k=1 -> i-1}(Vk-1)) = V^2*总和{i=1 -> V-1}(O(V^V)) = O(V^3*V^V) = O(V!)。

现在想象一个理想的世界，您可以在恒定时间内计算每条路径。您的算法需要 O(1*V!) = O(V!) 时间来运行，这是不切实际的。

可能有一种算法可以在不枚举路径的情况下计算路径，从而获得更有效的算法。

于 2011-03-09T18:31:23.253 回答
3

粗略近似路径的 Floyd-Warshall 概括如下：

 procedure FloydWarshall ()
    for k := 1 to n
       for i := 1 to n
          for j := 1 to n
             path[i][j] = path[i][j] + path[i][k]*path[k][j]

这是关于如何扩展它的一个非常粗略的想法。免责声明 - 这不是具体的 - 它非常随意，但希望它的帮助不仅仅是混淆。它有助于理解算法是如何工作的。它从图的邻接矩阵开始。在每次迭代 k 中，我们说从 i 到 j 的路径数等于先前迭代中从 i 到 j的路径数加上从 i 到 j 通过 k 的路径数。

因此，将图分解为 n 个大小为 kxk 的任意子邻接矩阵，在上面对它们中的每一个进行计算。现在您有了路径的数量，并通过在组合矩阵上重新计算上述部分来开始组合子矩阵。即，我们只需要在重新组合时重新计算 k 的 n/2 个值。我发现了这个，它看起来像一个类似的方向http://theory.stanford.edu/~oldham/publications/generalized/asgsp.pdf。

于 2011-03-10T21:23:43.763 回答
0

这个 SO 页面描述了一种用于打印任意两个顶点之间的所有非循环路径的 DFS 方法——它还包括 java 代码。您可以对其进行修改以查找所有顶点对的所有此类路径，但这不是计算所有顶点之间的所有路径的最有效方法。

于 2011-03-09T21:31:10.990 回答