Quote:>Hi all,

>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

>figure?

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 ...

>Cheers,

>Dave

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.

David

[ comp.ai is moderated. To submit, just post and be patient, or if ]

[ ask your news administrator to fix the problems with your system. ]