Summary

Heuristic functions estimate costs of shortest paths Good heuristics can dramatically reduce search cost Greedy best-first search expands lowest h Incomplete and not always optimal A*search expands lowest g + h Complete and optimal Admissible heuristics can be derived from exact solution of relaxed problems Local search algorithms can be used to find a reasonably good local optimum after a small number of restarts