Space complexity of breadth-first search

Question

I read that breadth-first search has to store (at most) $1+b+b^2+···+b^d$ nodes in memory ---more than depth-first search---, where $d$ is the depth of a solution, and $b$ is the branching factor.

Why isn't it $b^d$?

Why are $1+b+b^2+···+b^{d-1}$ (the previously searched depths) maintained in memory?

If it's a matter of completeness, then (a complete implementation of) DFS would suffer from the same problem.

Answer 1

That's not entirely correct Tobi. Breadth-First search requires to store in memory only those nodes awaiting for expansion. Thus, it only requires to store in memory $b^d$ nodes in the worst case, i.e., if the solution is found at the rightmost child at depth $d$. That is the number of nodes required to be stored in memory because when the solution is found at depth $d$, that is precisely the number of nodes awaiting for expansion.

Indeed! You could actually remove any node after expanding it. So far, you are correct when you are guessing that you could actually remove all nodes expanded in the previous depths whose sum gets so far as $b^0+b^1+b^2+b^3+...+b^{d-1}$. Now, here comes the question:

1. Why would you do it? Why would you actually remove those nodes? If you do not remove them, you could easily implement a duplicate detection mechanism: if a node $n$ is found at depth $d_1$ it is stored in memory. If it is found again at depth $d_2$, $d_2>d_1$ then its expansion can be skipped because a shortest path to it was already found ---given that the edge costs are all the same.
2. Oh yeah! you might be thinking that this idea is not worthy as it requires to store in memory a rather large number of nodes: $b^0+b^1+b^2+...b^{d-1}$, isn't it? So that while duplicate detection seems desirable it might be too costly.

Note however that the sum of the terms of the geometric progression $b^0+b^1+b^2+...+b^{d-1}$ equals $\frac{b^d-1}{b-1}$ so that adding duplicate detection requires only a small fraction ($b-1$) of the nodes actually required to be stored in memory ($b^d$).

In other words, we say that the memory requirements of Breadth-First Search are dominated by the number of nodes awaiting to be expanded, $b^d$. Additional memory can be used as the total number of nodes in memory, $b^d+\frac{b^d-1}{b-1}=\frac{b^{d+1}-1}{b-1}$ (in case that duplicate detection is implemented), is much smaller than the number of nodes required to store the nodes in the subsequent level, $b^{d+1}$.

Test these numbers, even if $b=2$, note that with duplicate detection, the number of nodes in memory is $2^{d+1}-1$ which is smaller than $2^{d+1}$, the number of nodes required to store in memory for exploring an additional level without duplicate detection. The situation worsens significantly if you consider larger branching factors. For example, with $b=10$, the number of nodes required with duplicate detection is $\frac{10^{d+1}-1}{9}$, which is only 11% of the nodes required to be stored in memory for exploring the subsequent depth without duplicate detection, $10^{d+1}$ ...

Hope this helps,