9

約70kのノードと250kのエッジがあり、グラフは必ずしも接続されていません。明らかに、効率的なアルゴリズムを使用することが重要です。おすすめは何ですか？

ちなみに、タスクを複数のマシンに分割する方法についてアドバイスをいただければ幸いです。この種の問題でも可能ですか？

ありがとう

4

4 に答える 4

4

MapReduceは、このための優れた分散アルゴリズムですが、少し強力すぎる可能性があります。それに興味がある場合は、この講義またはおそらくこのブログ投稿を見て、インスピレーションを得てください。（実際、私がMapReduceを教えられたとき、これは最初の例の1つでした。）

250kのエッジと70kの場合、グラフは比較的まばらであるように見えます。ダイクストラのアルゴリズムO( E + V log V )は、の完全な実行時間（すべてのソース）で、各ノードに対して実行されますO( VE + V^2 log V )。これは十分に高速であるはずですが、通常の警告がダイクストラに適用されます。（ネガティブエッジ。）

問題が負の重みを扱っているが、負のサイクルを扱っていない場合は、ジョンソンのアルゴリズムを調べることもできます。具体的には、再重み付けされたグラフを取得し、各ノードからダイクストラのアルゴリズムを実行するため、分散することもできます。

于 2010-03-10T23:59:53.823 に答える
4

Floyd-Warshallアルゴリズムを使用できます。それはまさにこの問題を解決します。

複雑さはO（V ^ 3）です。

O（V ^ 2 * log V + VE）の複雑さを持つジョンソンのアルゴリズムもあります。後者は、ダイクストラのアルゴリズムをV回実行するため、配布も簡単です。これは、並行して実行できます。

于 2010-03-11T00:01:16.347 に答える
1

この問題を並列化するには、2つの単純な方法があります
。1）サブコンポーネントを識別し、それらを異なるコンピューターに分散します。2つの異なるコンポーネントからの2つのノード間のパスの長さは未定義です。

2）グラフをさまざまなコンピューターにロードし、すべてのコンピューターにノードのリストを提供して、すべての最短経路を計算します。あるノードの結果は別のノードの結果に依存しないため、この問題を並列化できます。

利点：実装するのはそれほど難しくありませんが、これを一度解決する必要がある場合にのみ、このようにします。これが繰り返し発生する問題である場合は、分散アルゴリズムを確認することをお勧めします。

igraphを使用してください。これはCで記述されており、非常に高速で、Pythonをラッパー言語として使用できます。

于 2010-03-11T00:03:42.663 に答える
0

次のキーワードを持つ論文/出版物を見てください：分散グラフ検索アルゴリズム。これが役立つかもしれないものです。

このACMアカウントのみの紙もあります：グラフ上の分散計算：最短経路アルゴリズム

于 2010-03-11T00:03:54.110 に答える