Admissible heuristic combination

If $h_1,h_2\le h^{\ast }$, their pointwise minimum, pointwise maximum and each convex combination $\alpha h_1+(1-\alpha )h_2$ with $0\le \alpha \le 1$ are admissible heuristics. Each inequality follows directly by comparison with $h^{\ast }$. The maximum has heuristic dominance over the minimum and every such convex combination.

A sum need not be an admissible heuristic: two exact estimates of the same cost-one remaining action sum to two. A sufficient condition for a valid additive construction is separate nonnegative action-cost allocations $c_1,c_2$ with $c_1+c_2\le c$, and estimates bounded by the corresponding optimal allocated costs. Every goal-reaching graph path then costs at least $h_1+h_2$ under its original costs. Taking the minimum proves admissibility without counting the same work twice.

If $h_1,h_2$ are consistent heuristics, their maximum, minimum and fixed convex combinations are also consistent heuristics. For the maximum, choose an index attaining it at the source and bound its successor by the successor maximum. For the minimum, choose an index attaining it at the successor and bound the source minimum by that component. For a convex combination, multiply the two consistency inequalities by their nonnegative weights and add them. All these combinations vanish at goals when the inputs do.