Algorithms in a Nutshell

(^200) | Chapter 7: Path Finding in AI
As with BREADTH-FIRSTSEARCHand DEPTH-FIRSTSEARCH, board states are
entered into theclosedset when processed. Because ASEARCHincorporates
heuristic information that includes ag(n) computational component, there is one
situation when ASEARCHmay review a past decision on boards already visited. A
board state to be inserted into theopenset may have a lower evaluation score than
an identical state that has already been visited. If so, ASEARCHremoves the past
board state inclosedso it can locate a minimum-cost solution.
Each board state stores a back link, called aDepthTransition, to record (a) the
move that generated it, (b) a reference to the previous board state, and (c) the
depth from the initial position. In ASEARCH, the depth value is frequently used
as theg(n) component within the evaluation function. The algorithm generates
copies of each board state, since the moves are applied directly to the boards and
not undone.
Consequences
The success of ASEARCHis directly dependent upon its heuristic function. If
h(n) is always zero, ASEARCHis nothing more than BREADTH-FIRSTSEARCH.
However, ifh(n)>h(n), ASEARCHmay not be able to find the optimal solution,
although it may be possible to return some solution, assuming thath(n) is not
wildly off the mark.
One should use ASEARCHonly if a heuristic functionh(n) is found that isadmis-
sible. A heuristic function is admissible if 0≤h(n)≤h(n). There are two sides to this
constraint. Ifh(n) ever returns a negative number (stating, somehow, that the
board statenis “past” the goal state), then the contribution ofg(n) is negated
when computingf(n). Ifh(n)>h(n), the estimate is too high and ASEARCHmay
not find the optimal solution. However, it is difficult to determine an effective
h(n) that is admissible and that can be computed effectively. There are numerous
examples of inadmissibleh(n) that still lead to solutions that are practical
without necessarily being optimal.
ASEARCHwill find an optimal solution if its heuristic functionh(n) is admis-
sible. For the 8-puzzle, Table 7-3 shows the evaluation of three heuristic functions
over the sample board state:
148
73
652
Table 7-3. Comparing three evaluation h(n) functions
Measure name Description of h(n) Evaluation of h(n) Statistics
GoodEvaluator P(n) + 3S(n), where P(n) is the sum of the
Manhattan distances that each tile is from “home.”
S(n) is a sequence score that checks the non-
central squares in turn, allotting 2 for every tile not
followed by its proper successor and 0 for every
other tile, except that a piece in the center scores 1.
13+3*11=46 13-move solution
closed:14
open: 12
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use