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

Next: Comparison of Search Techniques Previous: Generating Heuristic Functions

Admissible Search Algorithms

An algorithm is admissible if, for any graph, it always terminates in an optimal (least-cost) path from a node s to a goal node whenever a path from s to a goal node exists.

A* is admissible if

  1. All operators costs are $>$ 0
  2. All heuristic estimates are $\geq$ 0, and
  3. The heuristic function never overestimates