What is the number of nodes generated by breadth-f

Question

The no. of nodes generated by breadth-first search is, according to my book: N(BFS) = b + b^2 + .... + b^d + ( b^(d+1) - b ) where b is the branching factor and d is the depth of the shallowest node. But should't it just be b + b^2 + .... + b^d ? because that, according to me is the no. of nodes till the depth of the goal. So why's there the + ( b^(d+1) - b )?

Answer 1

I think the case you are referring to is when the test condition is evaluated when a node is generated; then BFS expands all the nodes below the "target" at the smallest depth, except for the children of the target node itself. If the target is at depth d, the worst case is that the last leaf is not expanded (because it's the target):

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

Answer 2

There is a difference in a number of generated nodes by breadth first search depending on the variant of the algorithm you use.

If you apply the goal test to each node when it is selected for expansion (popped out of the open list/queue) then number of generated nodes will be (in the worst case):

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

where d is the solution depth, and b is the branching factor (maximum number of successor of any node).

This is because you will have to generate children of the goal node's siblings before you actually choose the goal node for expansion. And in the worst case, the goal node will be the last in the open list to be chosen for expansion.

But, there is one slight tweak on this general graph-search algorithm, which is that the goal test is applied to each node when it is generated rather than when it is selected for expansion.

So, suppose that the solution is again at the depth d. Again, in the worst case it is the last node generated at that level. Then the total number of nodes generated is:

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

So the space complexity in the first case is: O(b^(d+1)), and in the second case: O(b^d).