Bidirectional search

Template:Graph search algorithm Bidirectional search is a graph search algorithm that runs two simultaneous searches: one forward from the initial state, and one backward from the goal, and stopping when the two meet in the middle. The reason for this approach is that each of the two searches has complexity $O(b^{d/2})$ (in Big O notation), and $O(b^{d/2}+b^{d/2})$ is much less than the running time of one search from the beginning to the goal, which would be $O(b^{d})$.

This does not come without a price: Aside from the complexity of searching two times in parallel, we have to decide which search tree to extend at each step; we have to be able to travel backwards from goal to initial state - which may not be possible without extra work; and we need an efficient way to find the intersection of the two search trees. This additional complexity means that the A* search algorithm is often a better choice if we have a reasonable heuristic.

Bi-directional search can use a heuristic as well. An admissible heuristic will also produce a shortest solution as was proven originally for the uni-directional A* algorithm.

References

• Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach, 2nd ed., Prentice Hall, 2002 (§3.4).

• Dennis de Champeaux & Lenie Sint, An Improved Bi-directional Heuristic Search Algorithm, Journal ACM, vol 24, no 2, 1977 May, pp 177-191.

• Dennis de Champeaux, Bi-Directional Heuristic Search Again, Journal ACM, vol 30, no 1, 1983 January, pp 22-32.

Ddccc (talk) 22:42, 13 December 2007 (UTC)