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.

An example: Order in which the nodes are expanded

Properties:

  • Completeness: yes, if best-first search used
  • Optimality (Admissibility): yes, if best-first search used
  • Time Complexity: O(bd/2), if best-first search used 
  • Space Complexity: O(bd/2), if best-first search used (b – branching factor, d – depth in the tree)