"A* Search"
Informed searches: Best first search.
Searches without weighted costs: DFS, Breadth-F S, Best-F S.
Searches with weighted costs:
Uniform-cost search.
Define f(n) = total cost of the shortest path from the start node s to a goal node q such that the path goes through n.
Let g(n) = cost from start node
to n.
Let h(n) = cost from n to nearest
goal node.
Then f(n) = g(n) + h(n)
Here's a picture.
s --- g(n) ------- n ------- h(n) ------- q
+---------------- f(n) ----------------+
As the search proceeds, working out from s, and reaching each node n of many in turn, neither g(n) nor h(n) are known.
What CAN be determined are:
^
g(n) = the actual distance along
the best path found so far from s to n.
^
h(n) = the result of applying the
heuristic evaluation function to n; this is an estimate of h(n).
Adding these together we get
^
^ ^
f(n) = g(n) + h(n)
(Note: the estimate of f(n) is read as "f hat of n".)
It is used to find a shortest path from the start node to a goal node.
1. Initialize: Set the list OPEN
to contain only the start node s. Set CLOSED to empty. Set G[s] to 0. Set
PRED[s] to NULL; set found to false;
2. If OPEN is empty and not found,
then print failure and halt.
3. Else let L be the set of nodes
on OPEN for which F is the least.
If L has only
one element, let X be that element.
Else if L contains
any goal nodes, let X be one of them.
Otherwise let
X be any member of L.
4. Remove X from OPEN and put X
on CLOSED.
5. If X is a goal node, print the
path from s to X (by calling extract=path) and halt.
6. Let SUCCESSORS be the successors
of X.
7. For each Y in SUCCESSORS, do:
If Y is not already on OPEN or on CLOSED then
set G[Y] to G[X] + distance(X,Y);
set F[Y] to G[Y] + h(Y);
set PRED[Y] to X;
put Y on OPEN;
else
set Z to PRED[Y];
set temp to F[Y] - G[Z] - distance(Z,Y)
+ G[X] + distance(X,Y);
if temp < F[Y] then
set G[Y] to G[Y] - F[Y] + temp;
set F[Y] to temp;
set PRED[Y] to X;
if Y is on CLOSED then
insert Y on OPEN and take Y off of CLOSED;
Note: If there are no goal nodes in a particular state space, that does not prove the inadmissibility of any search algorithm.
Note: The Uniform-Cost algorithm is admissible. It finds a shortest path to each it reaches, and it gets there the first time by a shortest path.
Therefore A* is admissible provided h^ (n) is low enough. (if h^ (n) = 0 for all n, then A* reduces to uniform-cost search).
As the value of h^ (n) increases,
A* remains admissible provided h^ (n) never exceeds h(n).
However, if h^ (n) were to get "unbalanced", that could throw off the search and cause it to examine nodes that it should not.
Suppose we have two A* search algorithms, A1 and A2 such that A1 is more informed than A2. If they satisfy the "consistency assumption", then A1 does not open any node not opened by A2.
An A* algorithm satisfies the consistency assumption provided for any two nodes n1 and n2 the difference in their h^ values never exceeds the distance between them.
It is in this sense that we sometimes
speak of "optimality of A* search."
(Do not confuse this with admissibility
-- the limited guarantee of finding an optimal path).
Last modified: November 2, 1998
Steve Tanimoto