7

次のような単純な無向グラフがあるとします。

ここに画像の説明を入力

D、A、B、または C ( ) から開始する - ステップの開始点 ( )から開始点 ( ) までのV_start可能なパスがいくつあるかを計算する必要があります。ここで、各エッジと頂点を無制限に訪れることができます。 .V_startV_startn

深さ優先探索を考えていたのsteps > n || (steps == n && vertex != V_start)ですが、例えばn = 1000000. 次に考えたのは、DFS と動的プログラミングを組み合わせることでした。しかし、ここで行き詰まりました。

(これは宿題ではありません。学習のためにグラフとアルゴリズムをいじり回しているだけです。)

大規模な で合理的な時間内にこれを解決するにはどうすればよいnですか?

4

2 に答える 2

20

このタスクは、行列の乗算によって解決されます。

0 と 1 を含む行列nxを作成します ( からへのパスがある場合、セルに対して 1 )。この行列をそれ自体で乗算します(高速行列累乗の使用を検討してください)。次に、マトリックスのセルには、から始まり、で終わる長さのパスの数があります。nmat[i][j]ijkmat[i][j]kij

注: 高速行列累乗は基本的に高速累乗と同じですが、代わりに数値を乗算して行列を乗算します。

注 2:nはグラフ内の頂点の数であると仮定します。次に、ここで提案するアルゴリズムは、時間の複雑さ O(log k * n 3 ) で実行され、メモリの複雑さは O(n 2 ) です。ここで説明されているように、最適化された行列乗算を使用すると、もう少し改善できます。その場合、時間計算量は O(log k * n log 2 7 ) になります。

編集Antoine の要求に応じて、このアルゴリズムが実際に機能する理由を説明します。

アルゴリズムを帰納法で証明します。帰納法の基礎は明らかです。最初に、行列に長さ 1 のパスの数があります。

k行列を の累乗にすると、 の累乗kまで、との間のmat[i][j]長さのパスの数があると仮定しましょう。kij

次のステップを考えてみましょうk + 1。k + 1長さのすべてのパスは、長さのプレフィックスkともう 1 つのエッジで構成されることは明らかです。これは基本的に、長さのパスが次の式k + 1で計算できることを意味します (ここではmat_pow_k、行列を 1 乗したものを示しますk)

num_paths(x, y, k + 1) = sum i=0 i<n mat_pow_k[x][i] * mat[i][y]

繰り返しますnが、グラフ内の頂点の数です。これを理解するには少し時間がかかるかもしれませんが、基本的に、初期行列のmat[i][y]セルには と の間に直接エッジがある場合にのみ1 がxありyます。そして、長さ のパスを形成するために、そのようなエッジのすべての可能な接頭辞を数えますk + 1。

しかし、私が最後に書いたのは、実際には のk + 1st 乗を計算することですmat。これは、帰納法と私のステートメントのステップを証明します。

于 2012-04-27T06:59:20.723 に答える
2

これは、動的計画法の問題に非常に似ています。

  1. af[n][m] を始点から点 n までの m ステップの経路の数と定義する
  2. すべての点 n から隣接する k まで、次の式があります: f[k][m+1] = f[k][m+1] + f[n][m]
  3. 初期化では、すべての f[n][m] は 0 になりますが、f[starting_point][0] = 1
  4. 最終結果を計算できるように

擬似コード:

memset(f, 0, sizeof(f));
f[starting_point][0] = 1;
for (int step = 0; step < n; ++step) {
    for (int point = 0; point < point_num; ++point) {
        for (int next_point = 0; next_point < point_num; ++ next_point) {
            if (adjacent[point][next_point]) {
                f[next_point][step+1] += f[point][step];
            }
        }
    }
}
return f[starting_point][n]
于 2012-04-27T11:22:39.357 に答える