Algorithms in a Nutshell

A*Search | 203

Path Finding

in AI

A common powerful alternative to A*SEARCHis known as ITERATIVEDEEPENINGA*

(or IDA*), developed by Korf (1985). It relies on a series of expanding depth-first

searches with a fixed cost-bound. For each successive iteration, the bound is

increased based upon the results of the prior iteration. IDA* is more efficient than

BREADTH-FIRSTSEARCHor DEPTH-FIRSTSEARCHalone since each computed

cost value is based on actual move sequences rather than a heuristic estimate. Korf

(2000) has described how powerful heuristics, coupled with IDA*, have been used

to solve random instances of the 15-puzzle, evaluating more than 400 million

board states during the search process.

Barr and Feigenbaum (1981) present several alternatives to consider when one

cannot efficiently compute an admissibleh*(n) function.

Figure 7-13. Sample A*Search tree for 15-puzzle

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