Running Time and Heuristic Quality

Higher quality heuristic implies no more work.

• We say a heuristic h' is higher quality than another h if $h'(v) \le h(v)$ for all v (and admissibility and monotonicty hold).
• Therefore, the f values under h' will be smaller than those under h.
• Recall that A^* brings inside all nodes with f values below that of the destination.
• Therefore, running with h' will bring inside no more nodes than running with h.