Simple Search

The algorithm makes use of two procedures specific to the problem

1. A predicate goal?, which takes a state and returns #t if the state is a goal state
2. A procedure extend, which takes a state and returns all of the successor states to the state

• Form a one-element queue consisting of a zero-length path that contains only the root node.
• Until the first path in the queue terminates at a goal node (satisfies goal?) or the queue is empty,
  • Remove the first path from the queue; create new paths by extending the first path to all the neighbors of the terminal node.
  • Reject all new paths with loops.
  • ...
  • Add the new paths, if any, to the queue.
  • ...
• If the goal node is found, announce success; otherwise, announce failure.

• Depth-first search
  Add the new paths to the front of the queue.
  • Backtracks when a dead-end or "futility" limit is reached
  • Appropriate when there is a high branching factor
  • May be advantageous when many solutions exist but only one needs to be found
  • May fail to find a solution
• Breadth-first search
  Add the new paths to the back of the queue.
  • Appropriate when there are long useless branches but not when there is a high branching factor
  • Guaranteed to find a solution (if there is one) and to find the one with the least steps first
• Nondeterministic search
  Add the new paths at random places in the queue.
  • When unable to choose between depth-first and breadth-first