Bidirectional Search

search

Definition

Bidirectional Search

Bidirectional search is a search strategy that searches from the given initial state and backward from a goal state. Thus, it needs “invertible” actions, meaning it can go from state to predecessor states .

Properties

Completeness

Bidirectional search is complete if , the branching factor, is finite and both directions are implemented using BFS or UCS.

Time Complexity

The search paths meet halfway, so after steps in each direction. Note that is much smaller than .

Thus, the time complexity is:

Space Complexity

See time complexity.

Optimality

Bidirectional search is optimal if , the branching factor, is finite and both directions are implemented using BFS or UCS.