次のような単純な無向グラフがあるとします。
D、A、B、または C ( ) から開始する - ステップの開始点 ( )から開始点 ( ) までのV_start可能なパスがいくつあるかを計算する必要があります。ここで、各エッジと頂点を無制限に訪れることができます。 .V_startV_startn
深さ優先探索を考えていたのsteps > n || (steps == n && vertex != V_start)ですが、例えばn = 1000000. 次に考えたのは、DFS と動的プログラミングを組み合わせることでした。しかし、ここで行き詰まりました。
(これは宿題ではありません。学習のためにグラフとアルゴリズムをいじり回しているだけです。)
大規模な で合理的な時間内にこれを解決するにはどうすればよいnですか?
このタスクは、行列の乗算によって解決されます。
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。これは、帰納法と私のステートメントのステップを証明します。
これは、動的計画法の問題に非常に似ています。
擬似コード:
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]