*** Welcome to piglix ***

Consistent heuristic


In the study of path-finding problems in artificial intelligence, 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.

Formally, for every node N and each successor P of N, the estimated cost of reaching the goal from N is no greater than the step cost of getting to P plus the estimated cost of reaching the goal from P. That is:

where

A consistent heuristic is also admissible, i.e. it never overestimates the cost of reaching the goal (the opposite however is not always true!). This is proved by induction on , the length of the best path from node to goal. By assumption, , where denotes the cost of the shortest path from n to the goal. Therefore,


...
Wikipedia

...