Bidirectional search runs two searches at the same time, one forward from the start and one backward from the goal, and stops when the two frontiers meet; this cuts the work from about \(b^d\) to about \(2b^{d/2}\).
Idea. Instead of one search tree of depth \(d\), grow two trees of depth about \(d/2\). For \(b = 10, d = 6\): one BFS explores about \(10^6\) nodes, but two BFS searches of depth 3 explore about \(2\times10^3\).
Example. Undirected graph with edges S–A, S–B, A–C, B–C, C–D, D–E, D–F, E–G, F–G. Start S, goal G.
A E
/ \ / \
S C - D G
\ / \ /
B F
- Forward step 1 (from S): frontier {A, B}.
- Backward step 1 (from G): frontier {E, F}.
- Forward step 2: frontier {C}.
- Backward step 2: frontier {D}.
- Forward step 3: C generates D, which is already in the backward search → frontiers meet at D.
Joining the two half-paths: S → A → C → D → E → G (5 edges).
Requirements
- The goal state must be known explicitly (not just a goal test).
- We must be able to generate predecessors (actions must be reversible).
- A check is needed at every step to see whether a node is in both frontiers (usually with a hash table).
Properties (with BFS in both directions):
- Complete: yes (finite \(b\)).
- Optimal: yes, for equal step costs (with the proper meeting check).
- Time and space: \(O(b^{d/2})\).
Drawbacks: large memory (one frontier must be stored), and hard to use when there are many goal states or when predecessors are hard to compute (e.g. chess checkmate positions).