0 から 99 までのラベルが付いた 100 個のノードで構成される折れ線グラフがあります。
これは次のようになります。
0--1--2--3....98--99
そして、BFS、DFS、ダイクストラのアルゴリズムを使用して、最初のケースではノード 0 から他のすべてのノードへの最短パスを見つけます。2 番目のケースではノード 55 (開始ノード)、3 番目のケースではノード 99 に対して同じことを行います。
しかし、BFS では、最後のケースでかかった時間は最初のケースの 2 倍ですが、両方のケースでノードの位置はグラフィカルに同じです。に実行時間を添付しました
。
BFS の for ループと while ループは同じ回数アクセスされます。3 つのケースで異なる時間がかかるのはなぜですか??
ちなみに、C++ で実装されており、グラフの格納にはベクトルのベクトルが使用されます。
事前にどうもありがとうございました。
まず第一に、それを複数回実行しましたか? 結果はかなり異なる場合があります。
とにかく、キャッシュの問題が原因である可能性は十分にあります。コンピュータは、アクセスしているインデックスから配列 (の一部) をすぐにキャッシュするため、0 から配列にアクセスする場合、通常は非常にうまく機能します。ただし、配列の最後から開始すると、高速キャッシュに配列全体が含まれません。(ベクトルは単に動的にサイズ変更可能な配列であるため、これはベクトルの場合も同じです)
また、この方法でアルゴリズムの速度をテストするべきではありません。このように実際に比較することはできません。最初に BFS を実行すると、アレイ全体がまだキャッシュされていないためです。ただし、DFS を実行すると、アレイ全体がプロセッサの高速キャッシュにある可能性があります。より大きなグラフを取得し、疎なグラフと密なグラフの両方を確認することをお勧めします。また、アルゴリズムごとに個別のプログラムを作成して、 のようなユーティリティを使用してチェックするようにしtimeます。