You are previewing Algorithms in a Nutshell.

Algorithms in a Nutshell

Cover of Algorithms in a Nutshell by George T. Heineman... Published by O'Reilly Media, Inc.


Breadth-First Search finds 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-First Search tries 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. A*Search adds heuristic intelligence to guide its search rather than blindly following either of these fixed strategies.

A*Search, shown in Figure 7-10, is an iterative, ordered search that maintains a set of open board states to explore in an attempt to reach the goal state. At each search iteration, A*Search uses an evaluation function f*(n) to select a board state n from open whose f*(n) has the smallest value. f*(n) has the distinctive structure f*(n)=g*(n)+h*(n), where:

g*(n) estimates shortest sequence of moves from the initial state to n
h*(n) estimates shortest sequence of moves from n to the goal state
f*(n) estimates shortest sequence of moves from initial state to goal state through n
A*Search fact sheet

Figure 7-10. A*Search fact sheet

The asterisk (*) refers to the use of heuristic information (an historical convention from when the algorithm was first defined in 1968), thus f*(n), g*(n), and h*(n) are estimates of the actual costs f(n), g(n), and h(n), which ...

The best content for your career. Discover unlimited learning on demand for around $1/day.