Introduction to Artificial Inteligence - Spring 2001

Informed Search Methods

1. Best-first search
   • Greedy search: minimize estimated cost to reach a goal
   • A* search: minimize total path cost
   • Analysis of A*
2. Heuristic functions
   • Example of heuristic for 8-puzzle
   • Effect of accuracy on performance
   • Inventing heuristic functions
   • Heuristics for constraint satisfaction
3. Resource-bounded search
   • Iterative-deepening A*
   • RTA* (not in the textbook)
4. Iterative-improvement algorithms
   • Hill climbing search
   • Simulated annealing
   • Genetic algorithms (from chapter 20)