>In the A* algorithm, F = G + H where H is the result returned by the
>heuristic function. In many articles that I read about A*, the one
>thing I can't understand is: why should the heuristic function return
>an underestimate figure?
A* explores nodes in order of increasing total estimated cost F.
If the heuristic H is guaranteed never to overestimate then F is
a lower bound on the actual cost of a path via a given node, ie
the actual cost via that node must always be >= the estimate.
A* may then "waste time" expanding a node whose distance to the
goal is underestimated, but it will eventually discover that the
actual cost is greater than the estimate and immediately switch
to more promising nodes, hence ensuring that it finds an optimal
path (if one exists) before finding a suboptimal one.
If the heuristic overestimates then A* may find a suboptimal
path to the goal before it finds an optimal one, because an
overestimate causes it to defer exploring some node actually on
an optimal path, choosing instead to expand some more promising
node on a suboptimal path.
Quote:>How do we know it is an underestimate in the first place, because at
>any given node N, we do not know the actual (real) distance to the
>goal, so how can we say underestimate if we don't know the real
Finding heuristics that never overestimate is certainly possible
even when we don't know the distance from a node to the goal.
For example, the constant function H=0 never overestimates,
although it provides no guidance in the search. In a 4-connected
grid the "Manhattan Distance" (sum of the absolute values of the
differences in X and Y values between the node and the goal) also
never overestimates, and does provide useful guidance.
Quote:>Can someone please explain it in simple terms, or give me a hint.
>Something is blobked for me here ...
If it's still not clear I suggest you try it out by hand on a
small example, it should rapidly become obvious what's going on.
[ comp.ai is moderated. To submit, just post and be patient, or if ]
[ ask your news administrator to fix the problems with your system. ]