Proving optimality for tree-search

Suppose some suboptimal goal G2 has been generated and is in the queue2 . Let n be an unexpanded node on a shortest path to an optimal goal G. f (G2) = g(G2) + h(G2) = g(G2) since h(G2) = 0 f (G2) > g(G) = g(n) + h*(n) since G2 is suboptimal f (G2) > g(n) + h(n) = f (n) since h(n) ≤ h*(n) (admissible) Since f (G2) > f (n), A* will never select G2 for expansion