 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2022/artificial-intelligence/2/d/solution

Write

h^{*} (s)

for the optimal remaining cost and suppose

h_{i} (s) \leq h^{*} (s)

for

i = 1, 2

$max (h_{1}, h_{2})$ is an admissible heuristic, because both arguments are at most $h^{*}$ .
$min (h_{1}, h_{2})$ is an admissible heuristic, since it is no larger than either argument.
$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$ .
$α h_{1} + (1 - α) h_{2}$ is an admissible heuristic for $0 \leq α \leq 1$ , since nonnegative weighting gives $α h_{1} + (1 - α) h_{2} \leq α h^{*} + (1 - α) 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.

 New to topics? Read the docs here!