6.034 Artificial Intelligence - Recitations, fall 2004 online slides on search

Next: Informed Searches Previous: Analysis

Bidirectional Search

Search forward from initial state to goal AND backward from goal to initial state

Can prune many options

Must consider:

  • Which goal state to use (set of goal states)?
  • How to determine when two searches overlap
  • Which search to use for each direction (DFS probably not good choice)
  • Figure shows two breadth-first searches

\psfig{figure=figures/bds.ps,width=3.5in,height=2in}

Run time and space of bidirectional search using a uninformed searches is \(O(b^{d/2})\).