astar.alg

有关启发式搜索的经典算法：A*最短路径算法的实例和对应程序。关注的朋友可以留意一下。（比传统的Dijistra算法效率高很多哦！^_^）

  Just a little definition of the terms before we get started!

  Function f is the 'Goodness function'. It is made up of two
other values g and h. G is the cost of getting from the initial
state to the present state (NOTE: this is an actual number, it is
known.) While h is the hypothetical cost of going from the
present state to the final state.)  f=g+h.
  There are two Lists OPEN and CLOSED. OPEN is the list where all
the paths for a node have been found but NOT expanded (i.e have
not had their children found.) While the CLOSED List is the list
where Nodes have been expanded (have had children).
  This algorithm seems complicated (I know I had to review it a
number of times before I understood it,) but it does seem to
offer the best results. 
  NOTE: the breath first and depth first algorithms are just
simplified subsets of this algorithm. Well without further ado,
here's the algorithm.

                         A* Algorithm

1. Start with OPEN containing only the initial node. Set that
node's g value to 0, its h' value to whatever it is, and its f'
value to h'+0, or h'. Set CLOSED to the empty list.

2. Until a goal node is found, repeat the following procedure: If
there are no nodes on OPEN, report failure. Otherwise, pick the
node on OPEN with the lowest f' value. Call it BESTNODE. Remove
it from OPEN. Place it on CLOSED. See if BESTNODE is a goal node.
If so, exit and report a solution (either BESTNODE if all we
want is the node or the path that has been created between the
initial state and BESTNODE if we are interested in the path.)
Otherwise, generate the successors of BESTNODE but do not set
BESTNODE to point to them yet. (First we need to see if any of
them have already been generated.) For each such SUCCESSOR, do
the following:

  a) Set SUCCESSOR to point back to BESTNODE. These backwards
links will make it possible to recover the path once a solution
is found.

  b) Compute g(SUCCESSOR) = g(BESTNODE) + the cost of getting
from BESTNODE to SUCCESSOR. (usually this the cost is set to 1)

  c) See if SUCCESSOR is the same as any node on OPEN (i.e. it
has already been generated but not processed). If so, call that
node OLD. Since this node already exists in the graph, we can
throw SUCCESSOR away and add OLD to the list of BESTNODE's
successors. Now we must decide whether OLD's parent link should
be reset to point to BESTNODE. It should be if the path we have
just found to SUCCESSOR is cheaper that the current best path to
OLD (since SUCCESSOR and OLD are really the same node.) So see
whether it is cheaper to get to OLD via its current parent or to
SUCCESSOR via BESTNODE by comparing their g values. If OLD is
cheaper (or just as cheap), then we need do nothing. If SUCCESSOR
is cheaper, then reset OLD's parent link to point to BESTNODE,
record the new cheaper path in g(OLD). and update f'(OLD).

  d) if SUCCESSOR was not on OPEN, see if it is on CLOSED. If
so, call the node CLOSED OLD and add OLD to the list of
BESTNODE's successors. Check to see if the new path or the old
path is better just as in step 2(c), and set the parent link and
g and f' values appropriately. If we have just found a better
path to OLD, we must propagate the improvement to OLD's
successors. 
     This is a bit tricky. OLD points to its successors. Each
successor in turn point to its successors, and so forth, until
each branch terminates with a node that either is still on OPEN
or has no successors. So to propagate the new cost downward, do
depth-first traversal of the tree starting at OLD, changing each
node's g value (and thus also its f' value), terminating each
branch when you reach either a node with no successors or a node
to which an equivalent or better path has already been found.    
This condition is easy to check for. Each node's parent link
points back to its best known parent. As we propagate down to a
node, see if its parent points to the node we are coming from. If
so, continue the propagation. If not, then its g value already
reflects the better path of which it is part. So the propagation
may stop here. But it is possible that with the new value of g
being propagated downward, the path we are following may become
better that the path through the current parent. So compare the
two. If the path through the current parent is still better, sop
the propagation. If the path we are propagating through is now
better, reset the parent and continue propagation.
   e) If SUCCESSOR was not already on either OPEN or CLOSED, then
put it on OPEN, and add it to the list of BESTNODE's successors.
Compute f'(SUCCESSOR)=g(SUCCESSOR)+h'(SUCCESSOR).