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

Start Free Trial

No credit card required