= Solution
\b[Use $H=\max(h_1,h_2)$] if each estimate is available at comparable cost. For every $\alpha\in[0,1]$,
$$
\min(h_1,h_2)\le\alpha h_1+(1-\alpha)h_2\le H\le h^*.
$$
Thus $H$ has <heuristic dominance> over all the other combinations guaranteed to remain <admissible heuristics>. <A-star search> orders nodes by $f=g+h$, where $g$ is the accumulated path cost. A larger <admissible heuristic> excludes more nodes from the compulsory $f<C^*$ region, where $C^*$ is the optimal solution cost. Under the usual nonnegative-cost and goal-normalization assumptions, this gives at least as informative a search guide while preserving the optimality guarantee of <A-star search> with <tree search>.
The unweighted sum loses that guarantee. The dominance statement does not promise smaller wall-clock time in every implementation: evaluating estimates costs time, and nodes with $f=C^*$ depend on tie handling. Nor does admissibility of the inputs alone imply <consistent heuristics>. If both inputs are <consistent heuristics>, however, their pointwise maximum is also a <consistent heuristic>.
Back to article page
