Bidirectional search
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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(b d/2 ) (in Big O notation), and the sum of these two search times is much less than the O(b d ) 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.
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. 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.…
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(b d/2 ) (in Big O notation), and the sum of these two search times is much less than the O(b d ) 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.
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. 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. 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 . BHFFA2 has, among others, more careful termination conditions than BHFFA.
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 n is a node with parent p , then k_1(p,n) = k_2(n,p) , defined as being the cost from p to n . d' : the opposite search direction (i.e. d' = 3 - d ) \mathrm{TREE}_d : the search tree in direction d. If d = 1 , the root is s , if d = 2 , the root is t \mathrm{OPEN}_d : the leaves of \mathrm{TREE}_d (sometimes referred to as \mathrm{FRINGE}_d ). It is from this set that a node is chosen for expansion. In bidirectional search, these are sometimes called the search 'frontiers' or 'wavefronts', referring to how they appear when a search is represented graphically.
In this metaphor, a 'collision' occurs when, during the expansion phase, a node from one wavefront is found to have successors in the opposing wavefront. \mathrm{CLOSED}_d : the non-leaf nodes of \mathrm{TREE}_d . This set contains the nodes already visited by the search h_d(n) = \min_i \left \{H(n,o_i) | o_i \in \mathrm{OPEN}_{d'} \right \} where H(n,o) returns an admissible (i.e. not overestimating) heuristic estimate of the distance between nodes and . Front-to-Front suffers from being excessively computationally demanding.
Every time a node is put into the open list, its f = g + h value must be calculated. This involves calculating a heuristic estimate from to every node in the opposing set, as described above. The sets increase in size exponentially for all domains with .
Further reading
.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1294629505 under CC BY-SA 4.0; modifications have been made.