Any consistent heuristic is also admissible. But when is a heuristic admissible but not consistent (monotone)?
Please provide an example in which this is the case.
4 Answers
Admissible heuristic
never overestimates the cost to reach the goal. f(n) never overestimates the the cost of a solution along the current path through n. An obvious example of an admissible heuristic is the straight-line distance.
Consistency heuristic
- Consistent heuristic: for every node n and every successor n' of n generated by any action a: h(n) ≤ c(n,a,n') + h(n')
- Required only for applications of A* to graph search
- Every consistent heuristic is also admissible.
It is best to think of a consistent heuristic as an admissible heuristic which obeys the triangle inequality:
Cost(a -> c) <= Cost(a -> b) + Cost(b -> c)
for any three nodes a, b and c in the search space, with the understanding that the cost is computed using the actual cost between adjacent nodes and using the heuristic otherwise.
Related