Bidirectional Search

As outlined in Russell Norvig Chapter 03: Solving Problems by Searching

Definition

A Search Algorithm that adopts an Uninformed Search Strategy:

The algorithms we have covered so far start from an initial state and can reach any one of multiple possible goal states. An alternative approach called 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\). (p. 100)

Implementation

For the algorithm to work, we need to keep track of two frontiers and two tables of reached states. We also need to be able to reason backwards. If state s’ is a successor of s in one direction, we need to know that s is a successor of s’ in the other. When the two frontiers collide, we have a solution.

There are many different variants of bidirectional search, as with unidirectional search. RN’s implementation describes a bidirectional best-first search. This could be used with, for example, path cost as the evaluation function to give a bi-directional version of uniform-cost search.

Pseudocode

Properties and Performance

The properties and performance depend on the algorithms used to search in the two directions. For example, if the evaluation function is path cost and the optimal path is \(C^*\), no node with cost \(> \frac{C^*}{2}\) will be expanded, which be a considerable speedup.