Is the space complexity of the bidirectional search, where the breadth-first search is used for both the forward and backward search, $O(b^{d/2})$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Norvig & Russell's book (section 3.5) states that the space complexity of the bidirectional search (which corresponds to the largest possible number of nodes that you save in the frontier)
$$O(2b^{d/2}) = O(b^{d/2}).$$
The intuition behind this result is that (as opposed to e.g. uniform-cost search or breadth-first search, which have space (and time) complexity of $O(b^{d})$) is that the forward and backward searches only have to go half way, so you will not eventually need to expand all $b^{d}$ leaves, but only half of them.
However, this space complexity is correct if you use a breadth-first search for the forward and backward searches (which is your scenario!), given that breadth-first search, assuming a finite branching factor, expands one level at a time, so it's guaranteed that both the forward and backward searches meet in the middle. This can be seen in figure 3.17 of the same book, where you can see that both searches have the same "radius". Moreover, the only nodes that you need to store in the frontier are the ones on the circumference (not all nodes that you see in the image)
However, if you used another search algorithm to perform the forward and backward searches, the space complexity may be different. This is true if e.g. the searches do not meet and then they end up exploring all the state space.