Properties of Heuristics Dominance:
h2 is said to dominate h1 iff h2(n) ≥ h1(n) for any node n.
A* will expand fewer nodes on average using h2 than h1.
Proof:
Every node for which f(n) < C* will be expanded. Thus n is expanded whenever
h(n) < f* - g(n)
Since h2(n) ≥ h1(n) any node expanded using h2 will be expanded using h1.
Using multiple heuristics: Suppose you have identified a number of non-overestimating heuristics for a problem: h1(n), h2(n), … , hk(n)
Then max (h1(n), h2(n), … , hk(n))
is a more powerful non-overestimating heuristic. This follows from the property of dominance
