4
$\begingroup$

A heuristic function is said to be consistent, or monotone, if its estimate is always less than or equal to the estimated distance from any neighboring vertex to the goal, plus the step cost of reaching that neighbor.

I know I can be sure if a heuristic is consistent by verifying the property for each couple (node, child), but is there a smarter and quicker way for doing that?

$\endgroup$
1
$\begingroup$

Another option rather then verifying it for each couple node-child is to use some problem specific properties and prove it this way.

Iff it is known that the triangle inequality stands for the distance between the nodes in the specific problem, then the heuristic is consistent. The triangle inequality is part of definition of a metric. So if the distance in the problem space is some well known metric you can state that the heuristic is consistent. Example for that is the distance metric in the Euclidean geometry.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.