Q: Why domination implies faster search in A*

If we have 2 heuristics h1 and h2 and h1<=h2 for all n, then we say that h2 dominates h1. The question was why this always means that h2 in A* expands fewer nodes. Say for instance that h2 is constant at each level but bigger then h1 but the latter would show some interesting distribution over nodes revealing information about which branches look more promising.

The reason why domination translates into fewer nodes expanded is that A* is guaranteed to expand every node with a total cost smaller than the cost of the optimal goal node. Since for all nodes in the search tree g(n) is the same, and f(n)=g(n)+h(n), then it means that if A* with h2 would expand the node (because its f2(n) is smaller than f(G)), then A* with h1 would certainly also expand that node (because f1(n)<=f2(n)). Thus for both cases above, even though the distribution shows which branch is more promising, we would have to backtrack and expand all these nodes anyway.