Past exam of the computer science course of the University of Oxford / 2022 / Artificial intelligence / 2 / e / Solution

Use $H=\max (h_1,h_2)$ if each estimate is available at comparable cost. For every $\alpha \in [0,1]$,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^{\ast }$ region, where $C^{\ast }$ 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^{\ast }$ 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.