Bidirectional search

Simultaneously searches forward from the initial state and backwards from the goal state(s), hoping that the two searches will meet. The motivation is that $b^{d/2} + b^{d/2}$ is much less than $b^d$.

For this to work, we need to keep track of two frontiers and two tables of reached states, and we need to be able to reason backwards. We have a solution when the two frontiers collide.

There are many different versions of bidirectional search, just as there are many different unidirectional search algorithms.