2

割り当ての場合、O（n 4）時間を使用して有向グラフの推移閉包を計算するアルゴリズムを見つけるように求められます。フロイドウォーシャルアルゴリズムについてはすでに学びましたが、これははるかに優れているので、誰かがO（n4）時間で実行されるアルゴリズムを作成するのを手伝ってもらえますか？そのようなアルゴリズムはありますか？

私はそれが質問のばかげているように見えることを知っています。なぜ私たちがそれを行うのに遅い方法を見つけるように求められているのか、私は本当に理解していません。

4

2 に答える 2

4

Floyd WarshallはO(n^3)であり、はのO(n^3)サブセットであるO(n^4)ため、もO(n^4)です。
したがって、新しいグラフを設定することによりG'=(V,E',w')（E' = V x Vクリーク、完全グラフ）、およびw'(u,v) = 1 if (u,v) is in E, otherwise INFINITY-Floyd-Warshallアルゴリズムを使用(u,v)することにより、無限大未満の値で終わる各ペアがクロージャーに含まれます。

シータ（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. （u、v）はEにあるため、uからvまでの長さ1の最短経路の場合は基本節です。
  2. それぞれについてk： 長さの最短経路を持つ
    各ペア-経路とエッジがあるようなものがあります。誘導仮説から、前の反復でにを追加したため、条件はtrueになり、結果のセットに追加します。(u,v)k>1wu -> ... -> w(w,v)(u,w)Q(u,v)Q

同様に、Qにペア(u,v)が追加された場合、パスが存在するu->..->w->vため、正しく追加されたことを示します。

2番目のTheta(n^4)解決策：

G'上記のように設定しv、実行中の各頂点に対して、Vからベルマンフォード法を実行しvます。
BFの各実行はTheta(n^3)1であり、実行n回数はTheta(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）反復で1つのリンクのみを成長させます。推移閉包パスが完全に成長することを保証するために、それらが成長を停止するまで反復を続ける必要があります。

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 に答える