Bidirectional search

Graph and tree search algorithms
Alpha-beta pruning A* B* Beam Bellman–Ford algorithm Best-first Bidirectional Borůvka's algorithm Breadth-first D* Depth-first Depth-limited Dijkstra's algorithm Floyd–Warshall algorithm Hill climbing Iterative deepening depth-first Kruskal's algorithm Johnson's algorithm Lexicographic breadth-first Uniform-cost more
Related topics
Dynamic programming Search games

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(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.

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). An admissible heuristic will also produce a shortest solution, as was proven originally for A*.

Ira Pohl was the first one to design and implement a bi-directional heuristic search algorithm. Andrew Goldberg and other are explaining how the correct termination for the bidirectional Dijkstra’s Algorithm has to be.

References

• de Champeaux, Dennis; Sint, Lenie (1977), "An improved bidirectional heuristic search algorithm", Journal of the ACM 24 (2): 177–191, doi:10.1145/322003.322004 .
• de Champeaux, Dennis (1983), "Bidirectional heuristic search again", Journal of the ACM 30 (1): 22–32, doi:10.1145/322358.322360 .
• Pohl, Ira (1971), "Bi-directional Search", in Meltzer, Bernard; Michie, Donald, Machine Intelligence, 6, Edinburgh University Press, pp. 127–140 .
• Russell, Stuart J.; Norvig, Peter (2002), "3.4 Uninformed search strategies", Artificial Intelligence: A Modern Approach (2nd ed.), Prentice Hall .