O'Reilly logo

Algorithms in a Nutshell by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

A*Search

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required