The A* Algorithm (A Star)
(from Elements of AI Using Common Lisp, by Tanimoto)

     If the exact distances from the start node can be determined when
nodes are reached, then the uniform-cost procedure (maintaining only 
the actual distances traveled) can be applied.  When additionally, 
some heuristic information is available relating the nodes visited
to the goal node, a procedure known as the A* (A Star) algorithm is
usually better.
     The A* algorithm opens nodes in an order that gives highest priority
to nodes likely to be on the shortest path from the start node to the
goal.  To do this it adds g, the cost of the best path found so far
between the start node and the current node, to the estimated distance h
from the current node to some goal node.  Provided that the estimate h
never exceeds the true distance between the current node and the goal
node, the A* algorithm will always find a shortest path between the start
node and the goal node.  This is known as the admissibility of 
the A* algorithm.
     In a sense, the A* technique is really a family of algorithms, all 
having a common structure.  A specific instance of an A* algorithm is
obtained by specifying a particular estimation function h.
     If the estimate h is always zero, A* is certainly admissible.  In
fact, A* then is no different from the uniform-cost method.  In this case
the search algorithm is called  uninformed.  The most informed
algorithm possible would have h being the exact distance from the 
current node to the goal.  An algorithm A1 is said to be more informed
than an algorithm A2 if the heuristic information of A1 permits it to
compute an estimate h1 that is everywhere larger than h2, the estimate
computed by A2.