Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
