3

ビッグデータ分析で問題に直面しています。そこでは、175Kを超えるノードを持つグラフのダイクストラアルゴリズムを使用してパスを見つけています。しかし、問題は、パスが存在するかどうかを特定の送信元と宛先について知らないことです。私はこれを約1000のソースと宛先に対して行う必要があります。しかし、それらの間にパスが存在するかどうかわからないため、ランダムに選択することはできません。これをどう処理するかわかりません。MapReduce環境でのアルゴリズムの1回の実行には、ローカルで約15分の時間がかかります。したがって、試行錯誤は選択肢ではありません。少なくとも1000のソースと宛先を見つけることができるのは私たちだけです。サイクル（？）または強く接続されたコンポーネントを見つけることですか？これは正しいです ？私の問題が明確に理解できることを願っています。

私は基本的に、そのサイズのグラフにパスが存在するソースと宛先の1000ペアを見つけることを探しています

4

3 に答える 3

4

1000個のソースノードをランダムに選択し、ノードにアクセスするまで、ノードごとに幅優先探索kを実行することをお勧めします。次に、アクセスする次のノードを選択し、それをそのソースの宛先として設定します。

この方法を使用すると、各宛先がそのソースから到達可能であることが保証されます。

于 2012-12-04T03:10:59.320 に答える
3

disjoint-union-set（DUS）のようなデータ構造を使用できます。グラフ全体の接続性を取得するために初期化を行います。aがbに到達できる場合、それらはDUSの同じセットに配置されます。初期化の複雑さはすべて、グラフのエッジの数に依存します。そして、クエリはO（1）に関するものです。

于 2012-12-04T04:14:23.633 に答える
0

これが私が提案するアルゴリズムです：

findPairsPath ()
{
    define 2D Array SD //holds source-destination nodes
    SD = {}
    pick any node u randomly
    k=0

    while (k<1000)
    {
       DFS (u, k)
       pick any node u randomly not stored in SD 
    }
}

DFS (u, k)
{

    for all nodes v adjacent to u and not stored in SD
     {
       store (u,v) in SD //storing a source and a destination
       k++
       DFS (v,k)

     }

}
于 2012-12-25T22:18:36.443 に答える