Algorithms in a Nutshell

A*Search | 195

Path Finding

in AI

Input/Output

Input

The algorithm starts from an initial board state in a search tree and a goal state that

must be reached. It assumes that it can (a) iterate through all valid moves for a given

board state, and (b) compute the evaluation functionf*(n) on a board staten.

Output

Return a sequence of moves that represents the solution that most closely approx-

imates the minimal-cost solution from the initial state to the goal state (or declare

that no such solution was found given existing resources).

Figure 7-10. A*Search fact sheet

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