BFSの実行時間はO（b ^ d）です。
bは分岐係数、dは開始ノードからのグラフの深さ（レベルの数）です。
私はしばらくグーグルで検索しましたが、この「b」をどのように理解するかについて誰も言及していません。
つまり、分岐係数は「各ノードが持つ子の数」を意味することを私は知っています
たとえば、二分木の分岐係数は2です。
したがって、BFSグラフの場合、b=グラフ内の各ノードのすべての分岐係数を平均します。
またはb=MAX（各ノードのすべての分岐因子の中で）？
また、どちらの方法でbを選択しても、実行時間に近づくにはあいまいに見えます。たとえば、グラフに30000ノードがある場合、5ノードのみに10000分岐があり、残りのすべての29955ノードには10分岐しかありません。深度は100に設定されています。
この場合、O（b ^ d）は意味をなさないようです。
誰かが少し説明できますか？ありがとうございました！
より頻繁に引用されるランタイムは、BFS が O(m + n) であるというものです。ここで、m はエッジの数、n はノードの数です。これは、各頂点が 1 回処理され、各エッジが最大 2 回処理されるためです。
O(b^d) は、BFS をチェスのゲームでブルート フォーシングする場合などに使用されると思います。この場合、各ポジションには比較的一定の分岐係数があり、エンジンは一定数のポジションを深く検索する必要があります。たとえば、チェスの b は約 35 で、Deep Blue の検索深度は 6 ～ 8 (最大 20) でした。
このような場合、グラフは比較的非循環的であるため、b^d は m + n とほぼ同じです (ツリーでは同じです)。O(b^d) は、b が固定され、d が制御されるため、より便利です。
グラフO(b^d)では、b = MAXです。最悪の場合ですので。プリンストンhttp://www.princeton.edu/~achaney/tmve/wiki100k/docs/Breadth-first_search.htmlからのこのリンクを確認してください- 時間の複雑さの部分に移動します
人工知能から引用するには- Stuart Russel と Peter Norvig による最新のアプローチ:
時間と空間の複雑さは、問題の難しさの尺度に関して常に考慮されます。理論的なコンピューター サイエンスでは、典型的な尺度は状態空間グラフのサイズ |V | です。+ |E|、ここで、V はグラフの頂点 (ノード) のセット、E はエッジ (リンク) のセットです。これは、グラフが検索プログラムに入力される明示的なデータ構造である場合に適しています。(ルーマニアの地図はその一例です。) AI では、グラフは多くの場合、初期状態、アクション、および遷移モデルによって暗黙的に表現され、無限であることがよくあります。これらの理由から、複雑さは次の 3 つの量で表現されます。d、最も浅いゴール ノードの深さ (つまり、ルートからパスに沿ったステップ数)。そしてM、状態空間内の任意のパスの最大長。多くの場合、時間は検索中に生成されたノードの数で測定され、スペースはメモリに格納されるノードの最大数で測定されます。ほとんどの場合、ツリーでの検索の時間と空間の複雑さについて説明します。グラフの場合、答えは状態空間内のパスがどの程度「冗長」であるかによって異なります。
これにより、O(|V|+|E|) と b^d の違いについて明確な洞察が得られるはずです。