 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
• |
The restriction we mentioned on the previous slide
|
|
|
for the h function
is simply this:
|
|
|
The h function must never
overestimate the cost
|
|
to reach the goal.
|
|
|
|
• |
Such an h is called an admissible heuristic. Another
|
|
|
way of describing admissible functions is to say they
|
|
|
are optimistic, as they always think the cost to the
|
|
|
goal is less than it actually is.
|
|
|
|
• |
If we have an admissible h function, this naturally
|
|
|
transfers to the f function as f
never overestimates
|
|
|
the actual cost to the best solution through n.
|
|
