2

对于一个作业，我被要求找到一种算法，该算法使用 O(n 4 ) 时间计算有向图的传递闭包。我们已经了解了 floyd warshall 算法，它要好得多，所以有人可以帮我创建一个在 O(n4) 时间内运行的算法吗？有这样的算法吗？

我知道这似乎是一个愚蠢的问题。我真的不明白为什么我们被要求找到更慢的方法来做到这一点。

4

2 回答 2

4

Floyd Warshall 是O(n^3)，而且既然O(n^3)是 的一个子集O(n^4)，它也是O(n^4)。
因此，通过设置一个新的图G'=(V,E',w')where E' = V x V(clique, complete graph) 和w'(u,v) = 1 if (u,v) is in E, otherwise INFINITY- 通过使用 Floyd-Warshall 算法，每对(u,v)最终的值小于无穷大都在闭包中。

一个 Theta(n^4) 解决方案：

Q <- E (init) #(Q is a set)
for i from 1 to n:
   for each v in V:
     for each w in V:
        for each u in V:
            if (v,w) is in Q and (w,u) is in E:
               Q <- Q U {(v,u)}  #add (v,u) to Q

复杂性是微不足道Theta(n^4)的，我们只需要证明它确实找到了传递闭包。

通过归纳：

  1. 对于长度为 1 的从 u 到 v 的最短路径，它是基本子句，因为 (u,v) 在 E 中。
  2. 对于每个k： 具有最短路径长度的
    每一对- 存在这样一条路径和一条边。根据归纳假设，在以前的迭代中我们添加到，因此条件将产生真，我们将添加到结果集。(u,v)k>1wu -> ... -> w(w,v)(u,w)Q(u,v)Q

类似地表明，如果将某些对(u,v)添加到 Q 中，则存在路径u->..->w->v，因此它是正确添加的。

第二种Theta(n^4)解决方案：

G'如上所述设置，并为运行 Bellman Fordv中的每个顶点从. BF 的每次运行为1，运行次数为Vv
Theta(n^3)nTheta(n^4)

(1) 技术上它是O(VE)，但没有稀疏图E在Theta(V^2)

于 2012-12-09T09:15:31.213 回答
1

传递闭包的 Floyd-Warshall 算法如下所示：

int dist[N][N];  // For some N
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.
// If the nodes are unconnected, dist[i][j] should be infinity

for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
   if(dist[i][k] && dist[k][j])
      dist[i][j] = 1;

请注意使用的索引的顺序：它们以这种方式排序以保持最佳子结构属性。如果我们改为将它们重新排序如下，则违反了该属性：

  for ( i = 0; i < N; i++ ) 
  for ( j = 0; j < N; j++ )
  for ( k = 0; k < N; k++ )
    if(dist[i][j] && dist[j][k])
      dist[i][k]=1;

违反该属性的结果是传递闭包路径在上面的 O(n^3) 次迭代中（在最坏的情况下）仅增长一个链接。为了确保它们的传递闭包路径一直增长，我们需要不断迭代直到它们停止增长：

do{
  something_done=false;
  for ( i = 0; i < N; i++ ) 
  for ( j = 0; j < N; j++ )
  for ( k = 0; k < N; k++ )
    if(dist[i][j] && dist[j][k]){
      dist[i][k]=1;
      something_done=true;
    }
} while (something_done);

如果外循环在 O(N) 中，则算法本身在 O(N^4) 中。

不幸的是，可能无法（容易地）证明外循环具有该属性，因为它是特定于数据的。

于 2012-12-09T09:52:22.773 回答