現在、深さ優先検索 (最大 10 レベル) を実行して、2 部グラフで長さ $n$ のパスの数を数えています。ただし、これを実装すると、3000 個以上の要素を持つ 2 部グラフから長さ 5 の 700 万個のパスをカウントするのに 5 分以上かかります。このカウントの問題をより効率的に行う方法を探しています。文献にそのようなアルゴリズムがあるかどうか疑問に思っています。
これらは無向 2 部グラフであるため、パスにサイクルが存在する可能性があります。
ここでの私の目標は、1 分以内に 100 万要素の 2 部グラフで長さ $n$ のパスの数を数えることです。
提案された回答を事前にありがとうございます。
最初のアイデアには同意しますが、BFS とは言えません。BFS では各ノードを 1 回通過しますが、ここでは何度でも通過できます。
2 つの配列を保持する必要があります (Cnt1 と Cnt2 と呼びましょう。Cnt1 は要素に到達した回数であり、長さ i のパスがあり、Cnt2 は同じですが長さは i + 1 です)。最初はすべての要素が Cnt2 で 0 で、Cnt1 で 1 です (各ノードから始まる長さゼロのパスが 1 つあるため)。
N 回繰り返す:
すべてのノードを通過
する 現在のノードについて、接続されているすべてのノードを通過し、それぞれについて、Cnt2 のその位置に、Cnt1 の現在のノードに到達した回数を追加します。
すべてのノードを終了したら、Cnt1 に Cnt2 をコピーし、Cnt2 をゼロにします。
最後に、Cnt1 のすべての数値を追加するだけで、それが答えになります。
幅優先探索に変換し、同じノードに同じ長さでつながる 2 つのパスがある場合は、そこにたどり着いた方法ではなく、そのようなウェイがいくつあるかを追跡します。
これにより、多くの繰り返し作業が回避され、大幅なスピードアップが実現します。(nが小さくない場合は、より優れた高速化があります。読み進めてください。)
nここでの私の目標は、1 分未満で 100 万要素の 2 部グラフの長さのパスの数を数えることです。
ええと、幸運ですか？
別の調査方法として、グラフの隣接行列を n 乗すると、得られる行列のすべてのエントリは、1 つの場所から始まり、終了する長さの終わりのパスの数になります。別の。そのため、二乗を繰り返すなどの近道をすることができます。便利ですね。
残念ながら、100 万要素のグラフでは、10^12 エントリの隣接行列が発生します。このような 2 つの行列を単純なアルゴリズムで乗算するには、10^18 の演算が必要です。もちろん、より優れた行列乗算アルゴリズムがありますが、それでも、たとえば 10^15 演算を下回ることはありません。これは 1 分では完了しません。(行列が十分にまばらである場合、可能性はあるかもしれませんが、このトピックについて調査を行う必要があります。)