Skip to content
doubtly

1 answer

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

Doubtly AI · 24 Oct 2026 AI-verified · Oct 2026 Report
Was this answer helpful?

Your answer

Log in or create a free account to answer this question.