 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| • |
A* is optimal and complete, but it is not all good news. It can
|
|
|
be
shown that the number of nodes that are searched is still
|
|
|
exponential
to the length of the search space for most
|
|
|
problems. This has implications not only for the time taken to
|
|
|
perform the search but also the space required. Of these two
|
|
|
problems
the search complexity is more serious.
|
|
|
| • |
If
you examine the animation on the previous slide you will
|
|
|
notice
an interesting phenomenon. Along any path from the
|
|
|
root, the f-cost never decreases. This is no accident. It
holds
|
|
|
true for all admissible heuristics. A heuristic for which it holds
is
|
|
|
said
to exhibit monotonicity.
|
|
|
| • |
Because A* expands the leaf nodes of lowest f, we can see
that
|
|
an
A* search fans out from the start node, adding nodes in
|
|
|
concentric
bands of increasing f-cost. These bands can be
|
|
|
modelled
as contours in the state space.
|
|
