Ask a Question
Categories
prove that a heuristic if consistent then it admissible too but vice verse is not true
Rajni
on 2011-08-30 09:30:00Admissible heuristics • A heuristic h(n) is admissible if for every node n, h(n) ≤ h*(n), where h*(n) is the true cost to reach the nearest goal state from n. • An admissible heuristic never overestimates the cost to reach the goal, i.e., it is optimistic • Example: hSLD(n) (never overestimates the actual road distance) • Theorem: If h(n) is admissible, A* using TREESEARCH is optimal. That is, there is no goal node that has less cost than the first goal node that is found.
Rajni
on 2011-08-30 09:30:00Optimality of A* (proof) • Lemma 1: f(n) is never greater than the shortest path from the initial state to a goal state via n. • Proof: Since h(n) never overestimates h*(n), g(n)+h(n) (which is f(n)) never overestimates g(n)+h*(n) (which is the cost of the shortest path from the initial state to a goal state via n). • Lemma 2: f(n)=g(n) for every goal node n. That is, f(n) is the true cost to reach node n. • Proof: If n is a goal node, h*(n)=0. So h(n)=0 since h(n) ≤ h*(n). Thus, f(n) = g(n)+h(n) =g(n). • Suppose some suboptimal goal G2 has been generated and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G. 1. g(G2) > g(G) since G2 is suboptimal 2. f(G2) > f(G) from (1) since (Lemma1) f=g at goal nodes 3. f(G) ≥ f(n) by Lemma 2 4. f(G2) > f(n) from (2) and (3) Since f(G2) > f(n), A* will not select G2 for expansion
Rajni
on 2011-08-30 09:30:00Consistent heuristics • A heuristic is consistent if for every node n, every successor n\' of n generated by any action a, h(n) ≤ c(n,a,n\') + h(n\') • If h is consistent, we have f(n\') = g(n\') + h(n\') = g(n) + c(n,a,n\') + h(n\') ≥ g(n) + h(n) ≥ f(n) i.e., f(n) is non-decreasing along any path. • Theorem: If a heuristic is consistent then it is admissible. • Theorem: If h(n) is consistent, A* using GRAPH-SEARCH is optimal.