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.
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.
Andrew Goldberg and others explained the correct termination conditions for the bidirectional version of Dijkstra’s Algorithm.
[1] 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 was the first one to design and implement a bi-directional heuristic search algorithm.
[2] Search trees emanating from the start and goal nodes failed to meet in the middle of the solution space.
The BHFFA algorithm of de Champeaux fixed this defect.
[3] A solution found by the uni-directional A* algorithm using an admissible heuristic has a shortest path length; the same property holds for the BHFFA2 bidirectional heuristic version described by de Champeaux .
It returns a valid list of operators that if applied to
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
such that there exists some valid operator from each of the parent nodes to
[5] Bidirectional algorithms can be broadly split into three categories: Front-to-Front, Front-to-Back (or Front-to-End), and Perimeter Search.
and the root of the opposite search tree,
Front-to-Back is the most actively researched of the three categories.
[5] Front-to-Front algorithms calculate the h value of a node n by using the heuristic estimate between n and some subset of
The canonical example is that of the BHFFA (bidirectional heuristic front-to-front algorithm),[3][4] where the h function is defined as the minimum of all heuristic estimates between the current node and the nodes on the opposing front.
returns an admissible (i.e. not overestimating) heuristic estimate of the distance between nodes n and o. Front-to-Front suffers from being excessively computationally demanding.
Every time a node n is put into the open list, its
This involves calculating a heuristic estimate from n to every node in the opposing OPEN set, as described above.
The OPEN sets increase in size exponentially for all domains with b > 1.