12

Skiena のアルゴリズムの本には、Floyd Warshall アルゴリズムの次の説明が含まれています。

 floyd(adjacency_matrix *g)
 {
   int i,j; /* dimension counters */
   int k; /* intermediate vertex counter */
   int through_k; /* distance through vertex k */
   for (k=1; k<=g->nvertices; k++)
       for (i=1; i<=g->nvertices; i++)
           for (j=1; j<=g->nvertices; j++) {
                through_k = g->weight[i][k]+g->weight[k][j];
                if (through_k < g->weight[i][j])
                      g->weight[i][j] = through_k;
           }
  }

Floyd-Warshall のすべてのペアの最短経路は、O(n 3 ) 時間で実行されます。これは、漸近的に、ダイクストラのアルゴリズムへの n 回の呼び出しよりも優れていません。ただし、ループは非常にタイトで、プログラムは非常に短いため、実際にはより適切に実行されます。これは、隣接リストよりも隣接行列でうまく機能するまれなグラフ アルゴリズムの 1 つとして注目に値します。

太字の部分が真である理由を誰か詳しく説明してもらえますか?

4

4 に答える 4

10

それを分解しましょう：

Floyd-Warshall のすべてのペアの最短経路は、O(n 3 ) 時間で実行されます ...

これは、トリプルforループがあり、それぞれにn回の反復があるためです。

...これは、漸近的にダイクストラのアルゴリズムへのn回の呼び出しよりも優れていません。...

ダイクストラのアルゴリズムを 1 回呼び出すだけで、1 つの特定のノードx1からグラフ内のすべてのノードまでの最短経路がすべてわかることを思い出してください。したがって、グラフ内のすべてのノードに対してダイクストラのアルゴリズムをn回呼び出すことができます: x1、x2、... xnで、 x1からすべてのノードへの最短経路、x2からすべてのノードへの最短経路、 ... xnからすべてのノードへの最短経路を見つけます。言い換えれば、これはすべてのペアに最短経路を与えます - フロイド・ウォーシャルがそうするのと同じように!

Running Dijkstra n times:
time = number of nodes × O((n + e)lgn)      [assuming binary heap used for Dijkstra]
     = n × O((n + e)lgn)                
     = O(n(n + e)lgn)

したがって、Floyd-WarshallのO(n^3)時間は、Dijkstra へのn回の呼び出しのO(n(n + e)lgn)時間よりも優れているわけではありません。

... ただし、ループが非常にタイトで、プログラムが非常に短いため、実際にはより適切に実行されます。

ここでのキーワードは「実践」です。漸近分析は完璧ではないことに注意してください。これは、パフォーマンスの数学的抽象化/近似です。実際にコードを実行すると、考慮されていない多くの実際的な要因があります。プロセッサには、命令をフェッチして実行するための複雑な低レベル アーキテクチャがあります。命令をパイプライン化し、命令をプリフェッチし、命令を予測しようとし、キャッシュします。指示とデータ、...まったく予測不可能です! それでも、これらの低レベルの最適化はすべて、アルゴリズムの全体的なパフォーマンスに大きな影響を与える可能性があります. 理論的に遅いアルゴリズムはブーストを受けることができ、理論的に速いアルゴリズムは同じブーストを受けない可能性があります。これは、big-oh 表記の隠れた定数係数と呼ばれることもあります。

プロセッサは、入れ子になったforループと多次元配列の最適化を好むことがわかりました! これが、Skiena がここでほのめかしていることです。配列のループは、時間的および空間的な局所性forを最大限に活用し、低レベルのプロセッサの最適化でうまく機能します。一方、ダイクストラのアルゴリズムはこれをうまく行わないため、プロセッサの最適化もうまくいきません。その結果、ダイクストラは実際には遅くなる可能性があります。 Floyd-Warshall は、洗練されたデータ構造を使用しておらず、繰り返す命令の数が少ないという意味で「ショート プログラム」です。これらのことは、プロセッサの最適化とともに、Floyd-Warshall が小さな隠れた定数要因を持つことに貢献しています。つまり、
3 )小さい。

于 2018-04-14T20:06:01.717 に答える
3

ただし、ループは非常にタイトで、プログラムは非常に短いため、実際にはより適切に実行されます。

そのアルゴリズムを見ると、3 つのループがあり、その中にネストされているステートメントは 2 つだけです。唯一のロジックは、3 番目のネストされたループ内で実行されます。n Djikstra を実行した場合、ロジックは最初のループと最後のネストされたループ内で実行されますが、これは議論の余地があるほどクリーンではありません。クリーンな 3 つのループにより、コンピューターはメモリの管理も容易になります。

于 2012-05-28T03:57:38.777 に答える
2

一般的なデータ構造を持つダイクストラのアルゴリズムは O(E log v) ですが、フィボナッチ ヒープはこれを O(E+v log v) に改善します。これはより複雑なデータ構造であり、アルゴリズムの定数ファクトリは floyed よりも大きくなります。このリンクの実行時間を見てください。

この質問の違いは、q-sort と heap-sort の違いと同じです

于 2012-05-28T14:58:49.640 に答える