2

何百万もの頂点とエッジを持つ有向グラフがあります。頂点のセットが与えられています。それらが「START_POINTS」と呼ばれていると仮定しましょう。「END_POINTS」と呼ばれる別の頂点のセットも示されています。問題は、どのSTART_POINTSからどのEND_POINTSに到達できるかを見つけることです。

次に例を示します。

START_POINTS: S1 S2 S3 S4 S5 S6 S7 ... 
END_POINTS  : E1 E2 E3 E4 E5 E6 E7 ...

アルゴリズムは次のことを伝えることができるはずです。

S1 can reach to E1, E2, E6
S2 can reach to E9, E10
S3 cannot reach any END_POINT
S4 can reach to .....
....

一部のEND_POINTSは、どのSTART_POINTからも到達できない可能性があります。

さて、問題は次のとおりです。それを実装するための最も効率的な方法は何ですか？

各START_POINTから1つずつ開始し、深さ優先探索を使用して到達可能なEND_POINTSを見つけてみました（またはBFS、実行時間を大幅に変更します）。ただし、START_POINTSが非常に多い（END_POINTSも多い）ため、時間がかかります。

START_POINTSのトレースされたパス間には大きな重複があるため、検索を最適化できます。どのパスがどのEND_POINTSに到達できるかを覚えておく必要があります。これを達成するための最も効率的な方法は何ですか？これはよく知られている問題かもしれませんが、私はまだ解決策を見つけることができませんでした。

1月6日に編集：

highBandWidthのアイデアを実装しようとしました（Keith Randallが提案した方法と同様の方法で）：各ノードについて、このノードがSTARTポイントまたはENDポイントでない場合は、すべての入力を出力に接続してから、ノードを削除します。

foreach NODE in NODES
    Skip if NODE is START_POINT or END_POINT
    foreach OUTPUT_NODE of NODE
        Disconnect NODE from INPUT_NODE
    end
    foreach INPUT_NODE of NODE
        Disconnect NODE from INPUT_NODE
        foreach OUTPUT_NODE of NODE
            Connect INPUT_NODE to OUTPUT_NODE
        end
    end
    Remove NODE from NODES
end

これは非常に速く始まり、すぐに非常に遅くなります。これは主に、残りのノードの入出力カウントが非常に大きくなり、forループがネストされてパフォーマンスが低下するためです。それをより効率的にする方法はありますか？

4

3 に答える 3

1

これはやり過ぎかもしれませんが、Dijkstraをチェックしてみてください。以前、仮想ノードの独自のルーティング テーブルを作成するときに使用しました。この場合、すべてのノードの値が 1 になり、各ノードの移動コストが同じになることを意味します。

于 2011-01-04T04:33:54.620 に答える
1

グラフを剪定して、開始ノードまたは終了ノードに表示されないすべてのノードを取り除き、インバウンド ノードからアウトバウンド ターゲットへのエッジに置き換えます。それが完了したら、他のすべてのノード (開始ノードまたは終了ノード) を調べて、これらのノードを削除せずに、インバウンド ノードからアウトバウンド ノードにエッジを追加します。Djikstra のような反復を数回行うと、Start から End のエッジが残るはずです。

于 2011-01-04T05:02:26.403 に答える
0

まず、強連結成分アルゴリズムを実行します。次に、すべての接続されたコンポーネントを 1 つのノードに縮小します。次に、グラフのトポロジカル ソートを実行します。次に、1 回のパスで、どの開始ノードがグラフ内の各ノードに到達できるかを計算できます (各開始ノード s をセット {s} に初期化してから、トポロジー順に各ノードで着信エッジの結合を実行します)。

答えが # start nodes * # # end nodes と同じくらい大きくなる可能性があるという潜在的な問題があります。うまくいけば、単一のノードに収縮する大きな SCC がいくつかあることを願っています。これにより、答えがより簡潔になる可能性があります (同じ SCC 内のすべての開始ノードが同じ場所に到達できるため、セット内で 1 つの代表のみを使用する必要があります)。

于 2011-01-04T05:08:33.613 に答える