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)