algorithm - 幅優先探索で生成されるノードの数は?

Question

いいえ。私の本によると、幅優先探索によって生成されたノードの数は次のとおりです。 N(BFS) = b + b^2 + .... + b^d + ( b^(d+1) - b )ここで、bは分岐係数、dは最も浅いノードの深さです。しかし、それだけではいけませんb + b^2 + .... + b^d か？それは、私によれば、いいえです。ゴールの深さまでのノードの。では、なぜそこにあるの+ ( b^(d+1) - b )ですか？

Answer 1

使用するアルゴリズムのバリアントによって、幅優先探索で生成されるノードの数に違いがあります。

各ノードが拡張用に選択された (開いているリスト/キューからポップアウトされた) ときにゴール テストを各ノードに適用すると、生成されるノードの数は次のようになります (最悪の場合):

1 + b + b^2 + b^3 + ... + b^d + (b^(d+1) - b)、

ここdで、 は解の深さ、bは分岐係数 (任意のノードの後継者の最大数) です。

これは、展開するゴール ノードを実際に選択する前に、ゴール ノードの兄弟の子を生成する必要があるためです。最悪の場合、ゴール ノードは、展開のために選択されるオープン リストの最後のノードになります。

ただし、この一般的なグラフ検索アルゴリズムには、わずかな調整が 1 つあります。これは、各ノードが展開のために選択されたときではなく、生成されたときにゴール テストが適用されることです。

したがって、解が再び深さ にあるとしdます。繰り返しますが、最悪の場合、それはそのレベルで生成された最後のノードです。生成されるノードの総数は次のとおりです。

1 + b + b^2 + b^3 + ... + b^d.

したがって、最初のケースのスペースの複雑さは: O(b^(d+1))であり、2 番目のケースでは: O(b^d)です。

Answer 2

あなたが言及しているケースは、ノードが生成されたときにテスト条件が評価される場合だと思います。次に、BFS は、ターゲット ノード自体の子ノードを除き、「ターゲット」の下のすべてのノードを最小の深さで展開します。ターゲットが depthdにある場合、最悪のケースは最後のリーフが展開されないことです (それがターゲットであるため):

1 + b + b^2 + ... + b*(b^d - 1) = 1 + b + b^2 + ... + b^(d+1) - b = (b^(d+2) - 1) / (b - 1)