Consistent Heuristic

Consistent Heuristic

In computer science, a consistent (or monotone) heuristic function is an estimated path cost to a goal for a search that approximates the actual path cost in an incremental way without taking any step back. Formally, 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:

and

where

  • h is the consistent heuristic function
  • N is any node in the graph
  • P is any descendant of N
  • G is any goal node
  • c(N,P) is the cost of reaching node P from N

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,

,

making it admissible. ( is any node whose best path to the goal, of length m+1, goes through some immediate child whose best path to the goal is of length m.)

However, an admissible heuristic, can be made into a consistent heuristic, through the following adjustment:

(Known as the pathmax equation.)

Read more about Consistent Heuristic:  Consequences of Monotonicity

Other articles related to "consistent heuristic, consistent heuristics, heuristic, consistent":

Consistent Heuristic - Consequences of Monotonicity
... Consistent heuristics are called monotone because the estimated final cost of a partial solution, is monotonically non-decreasing along the best path to the goal, where is the cost of the best path from start node to ... It's necessary and sufficient for a heuristic to obey the triangle inequality in order to be consistent ... In the A* search algorithm, using a consistent heuristic means that once a node is expanded, the cost by which it was reached is the lowest possible, under the same conditions that Dijkstra's algorithm requires in ...

Famous quotes containing the word consistent:

    The methodological advice to interpret in a way that optimizes agreement should not be conceived as resting on a charitable assumption about human intelligence that might turn out to be false. If we cannot find a way to interpret the utterances and other behaviour of a creature as revealing a set of beliefs largely consistent and true by our standards, we have no reason to count that creature as rational, as having beliefs, or as saying anything.
    Donald Davidson (b. 1917)