 |
|
|
|
|
|
|
|
|
|
|
|
|
| • |
Two
possible heuristic functions that never
|
|
|
overestimate
the number of steps to the goal are:
|
|
|
|
1.
h1 = the number of tiles that are in the
wrong
|
|
|
position.
In figure 5.7, none of the 8 tiles is in the goal
|
|
|
position, so that start state would have h1 = 8. h1
is admissible
|
|
|
heuristic, because it is clear that any tile that is out of the
place
|
|
|
must
be moved at least once.
|
|
|
|
2.
h2 = the sum of distance of the tiles
from their goal
|
|
|
positions. Since no diagonal moves is allow, we use Manhattan
|
|
distance
or city block distance. h2 is also admissible, because
|
|
|
any move can only move 1 tile 1 step closer to the goal. The 8
|
|
|
tiles
in the start state give a Manhattan distance of h2 =
|
|
|
2+3+3+2+4+2+0+2
= 18
|
|
