Bidirectional Search

search

Definition

Bidirectional Search

Bidirectional search is a search strategy that searches from the given initial state and backward from a goal state. Thus, it needs “invertible” actions, meaning it can go from state $s$ to predecessor states $s^{\prime }$.

Properties

Completeness

Bidirectional search is complete if $b$, the branching factor, is finite and both directions are implemented using BFS or UCS.

Time Complexity

The search paths meet halfway, so after $\frac{d}{2}$ steps in each direction. Note that $b^{d/2}+b^{d/2}$ is much smaller than $b^d$.

Thus, the time complexity is:

$$O(2\cdot b^{d/2})=O(b^{d/2})$$

Space Complexity

See time complexity.

Optimality

Bidirectional search is optimal if $b$, the branching factor, is finite and both directions are implemented using BFS or UCS.