 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Two
extreme cases
|
|
|
|
|
h=0 A* becomes
UCS : complete&optimal but search
|
|
|
pattern
undirected
|
|
|
|
|
h too large : if
h is large enough to dominate g then
|
|
|
becomes like
Greedy. uses less memory but lose optimality.
|
|
| |
Usually when we say A* we exclude the last case,
|
|
|
and
imply that we have an:
|
|
|
| |
Admissible Heuristic: h(n) ≤ hT(n)
|
|
|
|
|
|
|
we never
over-estimate distance
|
|
|
|
|
h(n) must provide a valid lower bound on cost to the goal
|
|
|
|
|
the g term
does not get swamped and misled, but the
|
|
|
search pattern
improves
|
|
|
|
|
A* is complete
and optimal, and memory usage can be
|
|
|
much lower than
UCS
|
|
