Skip to content

washington Search: Cost & Heuristics

Search thru a Problem Space / State Space

Input

  • Set of states
  • Operators [and costs]
  • Start state
  • Goal state [test]

Output

  • Path: start ⇒ a state satisfying goal test
  • [May require shortest path]
  • [Sometimes just need state passing test]

Search Methods

Blind search

  • Depth first search (DFS)
  • Breadth first search (BFS)
  • Iterative deepening depth-first search (IDS)

Heuristic search

  • Best first search
  • Uniform cost search (UCS)
  • Greedy search
  • A*
  • Iterative Deepening A* (IDA*)
  • Beam search
  • Hill climbing

Depth First Search