 Home

Codex Wiki

List of universities

University of Oxford

Course of the University of Oxford

Undergraduate course of the University of Oxford

Computer science course of the University of Oxford

Past exam of the computer science course of the University of Oxford

2022

Artificial intelligence

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.

Solution

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

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

 Ancestors (11)

 Discussion (0)

 Articles by others on the same topic (0)

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

 Ancestors (11)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (0)

 Discussion (0)