In computer science
, a heuristic
) if, for every node n and every successor p of n generated by any action a, 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. In other words:
- * h is the consistent heuristic function
- * N is any node in the graph
- * P is any child of N
- * G is any goal node.
A consistent heuristic is also admissible. This is proved by induction. By assumption, , where denotes the cost of the shortest arc from n to the goal. Therefore,
making it admissible.
Note: not all admissible heuristics are consistent.