### 3.6.1 *A*^{*} Search

^{*}

** A^{*} search** is a combination of lowest-cost-first and best-first searches
that considers both path cost and heuristic
information in its selection of which path to expand. For each path on
the frontier,

*A*uses an estimate of the total path cost from a start node to a goal node constrained to start along that path. It uses

^{*}*cost(p)*, the cost of the path found, as well as the heuristic function

*h(p)*, the estimated path cost from the end of

*p*to the goal.

For any path *p* on the frontier, define
*f(p)=cost(p)+h(p)*. This is an
estimate of the total path cost to follow path *p* then go to a goal
node.

If *n* is the node at the end of path *p*, this can be depicted as follows:

actual estimate start ---------> n -----------> goal cost(p) h(p) -------------------------> f(p)

If *h(n)* is an underestimate of the path costs from node *n* to a goal node,
then *f(p)* is an underestimate of a path cost of going from a start
node to a goal node via *p*.

*A ^{*}* is implemented by treating the frontier as
a priority queue ordered by

*f(p)*.

**Example 3.15:**Consider using

*A*search in Example 3.4 using the heuristic function of Figure 3.12. In this example, the paths on the frontier are shown using the final node of the path, subscripted with the

^{*}*f*-value of the path. The frontier is initially

*[o103*, because

_{21}]*h(o103)=21*and the cost of the path is zero. It is replaced by its neighbors, forming the frontier

[b3_{21}, ts_{31},o109_{36}].

The first element represents the path *⟨o103,b3⟩*; its *f*-value
is *f(⟨o103,b3⟩)=cost(⟨o103,b3⟩)+h(b3)=4+17=21*.
Next *b3* is
selected and replaced by its neighbors, forming the frontier

[b1_{21}, b4_{29}, ts_{31}, o109_{36}].

Then the path to *b1* is selected
and replaced by its neighbors, forming the frontier

[c2_{21}, b4_{29}, b2_{29}, ts_{31}, o109_{36}].

Then the path to *c2* is selected
and replaced by its neighbors, forming

[c1_{21}, b4_{29}, b2_{29}, c3_{29}, ts_{31}, o109_{36}].

Up to this stage, the search has been continually exploring what seems to be
the direct path to the goal. Next the path to *c1* is selected and
is replaced by its neighbors, forming the frontier

[b4_{29}, b2_{29}, c3_{29}, ts_{31}, c3_{35}, o109_{36}].

At this stage, there are two
different paths to the node *c3* on the queue. The path to *c3* that does not
go through *c1* has a lower *f*-value than the one that
does. Later, we consider the situation when
one of these paths can be pruned.

There are two paths with the same *f*-value. The algorithm does not
specify which is selected. Suppose the path to *b4* is selected next
and is replaced by its neighbors, forming

[b2_{29}, c3_{29}, ts_{31}, c3_{35}, o109_{36}, o109_{42}].

Then the path to *b2* is selected and replaced by its
neighbors, which is the empty set, forming

[c3_{29}, ts_{31}, c3_{35}, b4_{35}, o109_{36}, o109_{42}].

Then the path to *c3* is removed and has no neighbors; thus, the new
frontier is

[ts_{31}, c3_{35}, b4_{35}, o109_{36}, o109_{42}].

Note how *A ^{*}* pursues many different paths from the start.

A lowest-cost path is eventually found. The algorithm is forced to try many different paths, because several of them temporarily seemed to have the lowest cost. It still does better than either lowest-cost-first search or best-first search.

**Example 3.16:**Consider Figure 3.8, which was a problematic graph for the other heuristic methods. Although it initially searches down from

*s*because of the heuristic function, eventually the cost of the path becomes so large that it picks the node on an actual optimal path.

The property that *A ^{*}* always finds an optimal path, if one exists,
and that the first path found to a goal is optimal is called the

**admissibility**of

*A*. Admissibility means that, even when the search space is infinite, if solutions exist, a solution will be found and the first path found will be an optimal solution - a lowest-cost path from a start node to a goal node.

^{*}**Proposition.**

*(*

*A*admissibility): If there is a solution,^{*}*A*always finds a solution, and the first solution found is an optimal solution, if^{*}- the branching factor is finite (each node has only a finite number of neighbors),
- arc costs are greater than some
*ε>0*, and *h(n)*is a lower bound on the actual minimum cost of the lowest-cost path from*n*to a goal node.

**Proof.**

**Part A:**A solution will be found. If the arc costs are all greater than some*ε> 0*, eventually, for all paths*p*in the frontier,*cost(p)*will exceed any finite number and, thus, will exceed a solution cost if one exists (at depth in the search tree no greater than*m/ε*, where*m*is the solution cost). Because the branching factor is finite, only a finite number of nodes must be expanded before the search tree could get to this size, but the*A*search would have found a solution by then.^{*}**Part B:** The first path to a goal selected is an optimal
path. The *f*-value for any node on an optimal solution path is less than
or equal to the *f*-value of an optimal solution. This is because *h*
is an underestimate of the actual cost from a node to a goal. Thus, the *f*-value of a node on an optimal
solution path is less than the *f*-value for any non-optimal solution.
Thus, a non-optimal solution can never be chosen while a node
exists on the frontier that leads to an optimal solution (because an element with
minimum *f*-value is chosen at each step). So, before it can select a
non-optimal solution, it will have to pick all of the nodes on an
optimal path, including each of the optimal solutions.

It should be noted that the
admissibility of *A ^{*}* does not ensure that every intermediate node
selected from the frontier is on an optimal path from the start node to a
goal node.
Admissibility relieves the algorithm from worrying about cycles and ensures
that the first solution found will be optimal. It does not ensure that
the algorithm will not change its mind about which partial path is the
best while it is searching.

To see how the heuristic function improves the
efficiency of *A ^{*}*, suppose

*c*is the cost of a shortest path from a start node to a goal node.

*A*, with an admissible heuristic, expands every path from a start node in the set

^{*}{p: cost(p)+h(p)<c}

and some of the paths in the set

{p: cost(p)+h(p)=c}.

Improving *h* affects the efficiency of *A ^{*}* if it reduces the
size of the first of these sets.