(^194) | Chapter 7: Path Finding in AI
SEARCHmust store on the order ofbdboard states inopen, wherebis the
branching factor for the board states anddis the depth of the solution found. This
is much higher than DEPTH-FIRSTSEARCH, which only needs to store aboutbd
board states inopenat any one time, based upon the actively pursued board state
at depthd.BREADTH-FIRSTSEARCHis guaranteed to find the solution with the
least number of moves that transform the initial board state to the goal board
state.
ASearch
BREADTH-FIRSTSEARCHfinds an optimal solution (if one exists), but it may
explore a tremendous number of nodes since it makes no attempt to intelligently
select the order of moves to investigate. In contrast, DEPTH-FIRSTSEARCHtries to
rapidly find a path by making as much progress as possible when investigating
moves; however, it must be bounded because otherwise it may fruitlessly search
unproductive areas of the search tree. ASEARCHadds heuristic intelligence to
guide its search rather than blindly following either of these fixed strategies.
ASEARCH, shown in Figure 7-10, is an iterative, ordered search that maintains a
set ofopenboard states to explore in an attempt to reach the goal state. At each
search iteration, ASEARCHuses an evaluation functionf(n) to select a board
statenfromopenwhosef(n) has the smallest value.f(n) has the distinctive struc-
turef(n)=g(n)+h(n), where:
g(n) estimates shortest sequence of moves from the initial state ton
h(n) estimates shortest sequence of moves fromn to the goal state
f(n) estimates shortest sequence of moves from initial state to goal state
throughn
The asterisk () refers to the use of heuristic information (an historical convention
from when the algorithm was first defined in 1968), thusf(n),g(n), andh(n) are
estimates of the actual costsf(n),g(n), andh(n), which are unknown until a solu-
tion is found. In short, having a lowf(n) score suggests that the board statenis
close to the final goal state.
The most critical component off(n) is the heuristic evaluation that computes
h(n), sinceg(n) can be computed on the fly by recording with each board state
its depth from the initial state.Ifh(n) is unable to accurately separate promising
board states from unpromising board states, ASEARCHwill perform no better
than the blind searches already described. If, however,h(n) can provide an accu-
rate estimate such that 0 ≤h(n)≤h(n), thenf(n) can be used to locate a minimal-
cost solution.
- Note thatg*(n)≥g(n) because there may, in fact, be a shorter move sequence that achieves the same
board state.
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
Licensed by
Ming Yi