Recall that in A*, a number is assigned to each node, its f-cost.
f-cost is defined as f(n)=g(n)+h(n), where g(n) is the cost of
traveling to node n, and h(n) is the heuristic guess at traveling from
node n to the goal.  A* expands nodes based on minimal f-cost (i.e. it
looks at all the nodes it knows about but hasn't yet examined closely,
and picks the one with the smallest f(n)).  Let's look at the
following situation:

                                 +-+   
                                 |n|   
                                 +-+
       	       	       	       	/   \
			      +-+   +-+
                              |o|   |p|  
                              +-+   +-+ 
       	       	       	     / 	       \
			   +-+ 	       +-+ 	
      			   |g|---------|q|
			   +-+         +-+

n is an already expanded node, and A* is trying to decide if it wants
to expand o or p.  If g is the goal node, then o is on the shorter
path, so we want A* to pick o.  Lets assume that g(n) = 5 and the cost
between nodes is always 1.  Therefore g(o)=6 and g(p)=6.  Now lets
assume that our heuristic sometimes overestimates, so that h(o)=5,
h(p)=3 and h(q)=2. 

In this case, f(o)=g(o)+h(o) = 6+5=11
	      f(p)=g(p)+h(p) = 6+3=9,
so A* would expand p next, discovering node q.  Then it decides which
node to expand, f(o)=g(o)+h(o) = 6+5=11
		f(q)=g(q)+h(q) = 7+2=9,
so A* would expand q next, discovering g.  Then it decides which node
to expand, f(o)=g(o)+h(o) = 6+5=11
	   f(g)=g(g)+h(g) = 8+0=8,
So A* would discover node g, notice that it is a goal and return the
path n->p->q->g, which is _not_ the shortest path.

The intuition here is that the overestimate of h(o) led A* to look at
another path where the overestimate was less bad.

© 2008 FAQS.ORG. All rights reserved.