Algorithms in a Nutshell

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

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