Algorithms in a Nutshell

(^196) | Chapter 7: Path Finding in AI
Assumptions
If 0≤h(n)≤h(n) andg(n)≥g(n), then ASEARCHwill find the minimal-cost solu-
tion, if it exists.
Context
Using the example from the 8-puzzle starting at:
two computed search trees are shown in Figures 7-11 and 7-12. Figure 7-11 uses
theGoodEvaluatorf(n) function proposed by Nilsson (1971). Figure 7-12 uses the
WeakEvaluatorf(n) function also proposed by Nilsson. The light-gray board states
depict theopenset when the goal is found. BothGoodEvaluatorandWeakEvaluator
locate the same eight-move solution to the goal node (labeled “GOAL”) but
GoodEvaluatoris more efficient in its search. Let’s review thef(n) values associ-
ated with the nodes in both search trees to see why theWeakEvaluatorsearch tree
explores more nodes. Observe that just two moves away from the initial state in
theGoodEvaluatorsearch tree, there is a clear path of nodes with ever-decreasing
f(n) values that lead to the goal node. In contrast, theWeakEvaluatorsearch tree
explores four moves away from the initial state before narrowing its search direc-
tion.WeakEvaluatorfails to differentiate board states; indeed, note how thef(n)
value of the goal node is actually higher than thef(n) values of the initial node
and all three of its children nodes.
Theh(n) component off(n) must be carefully designed, and this effort is more of
a craft than a science.h(n) must be efficient to compute; otherwise, the search
time becomes onerous. Much of the available ASEARCHliterature describes
highly specializedh(n) functions for different domains, such as route finding on
digital terrains (Wichmann and Wuensche, 2004) or project scheduling under
limited resources (Hartmann, 1999). Pearl (1984) has written an extensive (and
unfortunately out-of-print) reference for designing effective heuristics. Korf (2000)
discusses further strategies for designing admissibleh(n) functions. Michalewicz
and Fogel (2004) provide a recent perspective on the use of heuristics in problem
solving, not just for ASEARCH.
Solution
ASEARCHstores theopenboard states so it can efficiently remove the board state
whose evaluation function is smallest. When compared with BREADTH-FIRST
SEARCHand DEPTH-FIRSTSEARCH, there is a subtle difference in when ASEARCH
determines that it reaches the goal. Recall that BREADTH-FIRSTSEARCHand
DEPTH-FIRSTSEARCHcheck when the successor board states are generated.
813
45
276
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