= Solution
Write $h^*(s)$ for the optimal remaining cost and suppose $h_i(s)\le h^*(s)$ for $i=1,2$. The conclusions hold pointwise:
* \b[$\max(h_1,h_2)$ is an <admissible heuristic>], because both arguments are at most $h^*$.
* \b[$\min(h_1,h_2)$ is an <admissible heuristic>], since it is no larger than either argument.
* \b[$h_1+h_2$ is not necessarily an <admissible heuristic>.] A state with a single cost-one move to a goal can have $h_1=h_2=1$ at that state and both zero at the goal. Both original <heuristic functions> are exact, but their sum is $2>1$.
* \b[$\alpha h_1+(1-\alpha)h_2$ is an <admissible heuristic> for $0\le\alpha\le1$], since nonnegative weighting gives $\alpha h_1+(1-\alpha)h_2\le\alpha h^*+(1-\alpha)h^*=h^*$.
These are <admissible heuristic combinations>. An unweighted sum needs an extra condition, such as distributing action costs between the component estimates, to prevent counting the same required work twice.
Back to article page
