Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet in the middle. The reason for this approach is that in many cases it is faster: for instance, in a simplified model of search problem complexity in which both searches expand a tree with branching factor b, and the distance from start to goal is d, each of the two searches has complexity O(bd/2) (in Big O notation), and the sum of these two search times is much less than the O(bd) complexity that would result from a single search from the beginning to the goal.
Contents
- Description
- Terminology and notation
- Approaches for Bidirectional Heuristic Search
- Front to Back
- Front to Front
- References
As in A* search, bi-directional search can be guided by a heuristic estimate of the remaining distance to the goal (in the forward tree) or from the start (in the backward tree).
Ira Pohl (1971) was the first one to design and implement a bi-directional heuristic search algorithm. Andrew Goldberg and others explained the correct termination conditions for the bidirectional version of Dijkstra’s Algorithm.
Description
A Bidirectional Heuristic Search is a state space search from some state
While it may seem as though the operators have to be invertible for the reverse search, it is only necessary to be able to find, given any node
Similarly, for those edges that have inverse arcs (i.e. arcs going in both directions) it is not necessary that each direction be of equal cost. The reverse search will always use the inverse cost (i.e. the cost of the arc in the forward direction). More formally, if
Terminology and notation
Approaches for Bidirectional Heuristic Search
Bidirectional algorithms can be broadly split into three categories: Front-to-Front, Front-to-Back (or Front-to-End), and Perimeter Search (Kaindl Kainz 1997). These differ by the function used to calculate the heuristic.
Front-to-Back
Front-to-Back algorithms calculate the
Front-to-Back is the most actively researched of the three categories. The current best algorithm (at least in the Fifteen puzzle domain) is the BiMAX-BS*F algorithm, created by Auer and Kaindl (Auer, Kaindl 2004).
Front-to-Front
Front-to-Front algorithms calculate the h value of a node n by using the heuristic estimate between n and some subset of
where
Front-to-Front suffers from being excessively computationally demanding. Every time a node n is put into the open list, its