Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

A search algorithm explores the state space by generating successors of states already explored, building a search tree from the initial state.

Terms

TermMeaning
Frontiercandidate nodes waiting to be expanded
Explored (closed) setnodes already expanded
Parent / child nodedirect predecessor / direct successor
Root nodetop node, no parent (the initial state)
Leaf nodenode with no children
Branching factor maximum (or average) number of successors of a node
depth of the least cost solution
maximum depth of the state space

A strategy is defined by the order of node expansion, i.e. which frontier node is picked next.

Four Criteria

CriterionQuestion
Completenessdoes it always find a solution if one exists?
Time complexityhow long does it take, measured as number of nodes generated
Space complexitymaximum number of nodes kept in memory
Optimalitydoes it always find the best (least cost) solution?

Uninformed vs Informed

Two families:

  • uninformed (blind) search uses only the problem definition: BFS, UCS, DFS, depth limited, iterative deepening, and it is usually exponential in time and space
  • informed (heuristic) search uses problem specific knowledge to decide the expansion order: greedy search and A*, usually far more efficient

Uninformed Summary

CriterionBFSUCSDFSDepth limitedIterative deepeningBidirectional
Time
Space
OptimalYes*YesNoNoYes*Yes
CompleteYesYesNoYes if YesYes

* when all step costs are equal.

Question to think: is an optimal strategy also complete? Yes, if it always returns the best solution then it must return some solution whenever one exists.

The details of each uninformed method start with Breadth-First and Uniform-Cost Search.