3

これは、おそらく最適な解決策がない問題です。有向グラフがあり、サイクルがあるかどうかわからないとします (サイクル検出は、この問題の側面の 1 つになります)。一連の頂点 (おそらく数百万の頂点) が与えられた場合、特定のグラフのすべての一意のペア間のすべての個別のパス (重複する頂点のないパス) をカウントする必要があります。この状況にどう立ち向かうか。

これを行うための強引な方法を見てみましょう。

  • グラフからすべての可能なペアを計算します。

  • グラフのペアごとに、DFS を使用してソースから宛先へのすべてのパスを取得します。

  • ペアがハッシュ テーブルで表されていると仮定すると、このペアに対する値としてパス カウントを入れます。
  • 残りのペアについて繰り返します。

これで問題が発生する可能性があることを指摘できますか? この問題をこのように考えてみましょう。地球上のすべての都市間のすべての個別の経路を見つける計算上の課題は何ですか?また、この問題を解決しようとする場合、どこから始めればよいでしょうか?

編集:提示されたアルゴリズムの一部は、O(n!) 階乗時間で結果を生成します。これは、処理するリソースが限られている単一のマシンにとっては、やや困難な計算です。グラフ トラバーサルの問題を小さなチャンクに分割するための map-reduce テクニックを知っている人はいますか?

4

3 に答える 3

3

そのようなパスがいくつ存在できるか考えたことがありますか?

このような V 個の頂点を持つグラフでは、約 V^2 個の異なるペアがあります。完全なグラフ (すべてのペアの間にエッジが存在するもの) を持つ最悪のシナリオを想像してみましょう。パス内で重複する頂点を許可しないため、パスは 1 エッジから V-1 エッジまでの任意の場所に配置できます。

頂点の各ペア間:

  1. 1 つのエッジを持つパスは 1 つだけです。
  2. 2 つのエッジを持つ V-2 パスがあります。始点でも終点でもない中間頂点を使用します。
  3. 3 つのエッジを持つ (V-2)(V-3) パスがあります。任意の 2 つの異なる中間頂点を使用します。
  4. 4 つのエッジを持つ (V-2)(V-3)(V-4) パスがあります。
  5. n 個のエッジを持つ prod{k=1 -> n-1}(Vk-1) パスがあります。

それを考えると、V を持つグラフの合計パスは最大で V^2*sum{i=1 -> V-1}(prod{k=1 -> i-1}(Vk-1)) であることがわかります。頂点。

したがって、パスの総数は P(V) = V^2*sum{i=1 -> V-1}(prod{k=1 -> i-1}(Vk-1)) = V^2* sum{i=1 -> V-1}(O(V^V)) = O(V^3*V^V) = O(V!)。

ここで、各パスを一定時間で計算できる理想的な世界を想像してください。アルゴリズムの実行には O(1*V!) = O(V!) 時間がかかりますが、これは非現実的です。

パスを列挙せずにカウントできるアルゴリズムが存在する可能性があるため、より効率的なアルゴリズムが得られます。

于 2011-03-09T18:31:23.253 に答える
3

パスの大まかな近似を取得するフロイド-ウォーシャルの一般化は次のとおりです。

 procedure FloydWarshall ()
    for k := 1 to n
       for i := 1 to n
          for j := 1 to n
             path[i][j] = path[i][j] + path[i][k]*path[k][j]

これをどのようにスケーリングするかについての非常に大まかなアイデアを次に示します。免責事項 - これは具体的なものではありません。非常に手の込んだものですが、混乱を招く以上の助けになることを願っています。アルゴリズムがどのように機能するかを理解するのに役立ちます。グラフの隣接行列から開始します。各反復 k では、i から j へのパスの数は、i から j への前の反復のパスの数に、k を介した i から j へのパスの数を加えたものに等しいと言っています。

したがって、グラフをサイズ kxk の n 個の任意の下位隣接行列に分割し、それぞれについて上記の計算を行います。これでパスの数がわかり、結合された行列で上記の一部を再計算することにより、部分行列の結合を開始します。つまり、再結合時に k の n/2 値を再計算するだけで済みます。これは、 http://theory.stanford.edu/~oldham/publications/generalized/asgsp.pdfと同様の方向に見えます。

于 2011-03-10T21:23:43.763 に答える
0

この SO ページでは、任意の 2 つの頂点間のすべての非循環パスを出力するための DFS メソッドについて説明します。Java コードも含まれています。これを変更して、頂点のすべてのペアのすべてのパスを見つけることができますが、すべての頂点間のすべてのパスをカウントする最も効率的な方法ではありません。

于 2011-03-09T21:31:10.990 に答える