Consistent heuristic

From Wikipedia, the free encyclopedia

 The introduction to this article provides insufficient context for those unfamiliar with the subject.
Please help improve the article with a good introductory style.
This article does not cite any references or sources. (October 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

In computer science, a heuristic is consistent (or monotone) 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(N) \leq c(N,P) + h(P) and
h(G) = 0.\,

where

  • 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. If node n is separated from the goal by an arc of cost c(n,G), then that cost is the lowest possible cost to goal. Therefore h(n) \leq h^*(n), making it admissible.

Note: not all admissible heuristics are consistent.

Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.