Is an admisible heuristic always monotone (consistent)? -
for a* search algorithm, provided heuristic h, supose h admisible. that is: h(n) ≤ h*(n) every node n, h* real cost n goal . does ensure heuristic monotone? that is: f(n) ≤ g(n') + h(n') every sucesor n' of n, f(n)= h(n) + g(n) , g(n) accumulated cost. no. assume have 3 successor states s1 , s2 , s3 , goal state g s1 -> s2 -> s3 -> g . s1 starting node. consider following values h(s) , h*(s) (i.e. true cost): h(s1) = 3 , h*(s1) = 6 h(s2) = 4 , h*(s2) = 5 h(s3) = 3 , h*(s3) = 3 h(g) = 0 , h*(g) = 0 following path goal can have that: g(s1) = 0, g(s2) = 1, g(s3) = 3, g(g) = 6 , coinciding true cost above. although heuristic function admissible ( h(s) <= h*(s) ), f(n) not monotonic. instance f(s1) = h(s1) + g(s1) = 3 while f(s2) = h(s2) + g(s2) = 5 f(s1) < f(s2) . same holds between f(s2) , f(s3) . of course means have quite uninformative heuristic.