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

Next: Example Previous: A*

Power of f

If a heuristic function is wrong (bad estimate), it either overestimates (guesses too high) or underestimates (guesses too low).

For A*, overestimating is much worse than underestimating.

A* returns an optimal answer if h(n) is admissible, or never overestimates the true cost to the nearest goal.