5

問題: 重み付けされていない無向グラフで最短経路を見つける。

幅優先探索は 2 つのノード間の最短経路を見つけることができますが、これには最大で O(|V| + |E|) の時間がかかる場合があります。事前に計算されたルックアップ テーブルを使用すると、O(1) 時間でリクエストに応答できますが、O(|V|^2) スペースが犠牲になります。

私が疑問に思っていること:よりきめの細かい時空トレードオフを提供するアルゴリズムはありますか? 言い換えれば、次のようなアルゴリズムはありますか?

  1. O(1) よりも長い時間で最短経路を見つけますが、双方向の幅優先検索よりも高速です
  2. O(|V|^2) より少ないスペースを占有する事前計算されたデータを使用しますか?

実用面:グラフは 800,000 ノードであり、スモールワールド ネットワークであると考えられています。すべてのペアの最短パス テーブルはギガバイトのオーダーになります。これは最近では法外なことではありませんが、私たちの要件には合いません。

しかし、私は好奇心から質問しています。夜、私を悩ませているのは、「どうすれば全ペア ルックアップ テーブルのキャッシュ ミスを減らすことができるか?」ではなく、「聞いたことのないまったく異なるアルゴリズムが世の中にあるのだろうか?」ということです。

答えはノーかもしれませんが、それは問題ありません。

4

2 に答える 2

1

ルックアップテーブルが大きすぎてディスクに保存できない場合は、入力セットを非常に大きくする必要があるようです。その場合、データはRAMに収まらないと思います。つまり、使用するアルゴリズムを調整して、読み取りと書き込みの量を最小限に抑える必要があります。ディスクへの書き込みが非常に遅いため、ディスクが関係する場合は常にスペース==時間。

使用する必要のある正確なアルゴリズムは、使用しているグラフの種類によって異なります。この研究論文はあなたにとって興味深いかもしれません。完全開示：私自身は読んでいませんが、あなたが探しているもののようです。

編集：

スモールワールドネットワークのように、グラフが（ほぼ）接続されている場合、ルックアップテーブルをV^2より小さくすることはできません。これは、すべてのルックアップにディスクアクセスが必要になることを意味します。エッジがメインメモリに収まる場合は、毎回パスを計算する方が速い場合があります。それ以外の場合は、すべての最短パスの長さを含むテーブルからパスを計算する可能性があります。そのテーブルからパスを再構築できます。

重要なのは、どちらの方向でも互いに近いテーブルのエントリが、ディスク上でも互いに近いことを確認することです。このストレージパターンは、次のことを実現します。

1 2    1   2  5  6
3 4    3   4  7  8
       9  10 13 14
       11 12 15 16

また、キャッシュ階層でもうまく機能します。

テーブルを計算するために、データをブロック単位で処理する修正されたFloyd-Warshallを使用する場合があります。これにより、特に並列化する場合に、妥当な時間で計算を実行できます。

于 2010-04-27T20:55:47.070 に答える
1

最短経路を見つけるためのダイクストラのアルゴリズムを見ることから始めるべきです。a* アルゴリズムは、ヒューリスティックを使用して、開始ノードとゴール ノードの間の最適なルート (ユークリッド距離など) を計算するのにかかる時間を短縮するバリアントです。このヒューリスティックは、パフォーマンスまたは精度のために変更できます。

于 2010-04-27T20:48:22.013 に答える