Algorithms in a Nutshell

A*Search | 201

Path Finding

in AI

Forces

BREADTH-FIRSTSEARCHand DEPTH-FIRSTSEARCHinspect theclosedset to see

whether it contains a board state, so we used a hash table for efficiency. However,

for A*SEARCHwe may need to reevaluate a board state that had previously been

visited if its evaluated score function is lower. Why would this happen? Recall the

situation in DEPTH-FIRSTSEARCHwhere board states at the depth limit were

found to be (as it turned out) only three moves away from the goal state. These

board states were placed into theclosedset, never to be processed again. In

A*SEARCH, if these same board states are revisited with a lower evaluated score,

they become available again.

A*SEARCHmust be able to rapidly locate the board state in theopenset with the

lowest evaluation score. Note that both BREADTH-FIRSTSEARCHand DEPTH-

FIRSTSEARCHwere able to use a constant time operation to retrieve the next

board state from the open set because they were using a queue and a stack,

respectively. If we stored theopenset as an ordered list, the performance suffers

because inserting a board state into theopenset takes O(n); we can’t use a binary

heap to store theopenset, since we don’t know in advance how many board states

are to be evaluated. Thus we use a balanced binary tree, which offers O(logn)

performance for retrieving the lowest-cost board state and for inserting nodes into

theopen set.

Analysis

The computational behavior of A*SEARCHis entirely dependent upon the

heuristic function. One recent result (Russel and Norvig, 2003) shows that if

|h(x)–h*(x)|≤log h*(x), then the performance is O(d), wheredreflects the distance

to the computed solution, rather than O(bd), wherebrepresents the branching

factor for the search tree. However, this condition is rather hard to satisfy;

GoodEvaluator, which works so well for the 8-puzzle, for example, does not meet

this criteria.

As the board states become more complex, heuristic functions become more

important than ever—and more complicated to design. They must remain effi-

cient to compute, or the entire search process is affected. However, even rough

heuristic functions are capable of pruning the search space dramatically. For

example, the 15-puzzle, the natural extension of the 8-puzzle, includes 15 tiles in

a four-by-four board. It requires but a few minutes of work to create a 15-puzzle

WeakEvaluator Count number of misplaced tiles. 7 13-move solution

closed:145

open:110

BadEvaluator Take differences of opposite cells (across from

the center square) and compare against the

ideal of 16. Ignore blank cell.

(7–0) + (6–8) +

(5–4) + (2–1) = 7

Score is |16–7|=9

421-move solution

closed: 2499

open: 1583

Table 7-3. Comparing three evaluation h*(n) functions (continued)

Measure name Description of h*(n) Evaluation of h*(n) Statistics

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