Past exam of the computer science course of the University of Oxford / 2015 / Intelligent systems / 1 / b / Solution

A-star search is best-first search with priorityHere $u$ is a search node, $s(u)$ is its state, $g(u)$ is its accumulated path cost, and $h^{\ast }(s)$ is the minimum remaining cost to any goal state, interpreted as $\infty$ if no goal is reachable. The inequality defines an admissible heuristic. Thus $f(u)$ is a lower bound on the cost of any solution extending that particular action history.

Initialize the search frontier with the root. Repeatedly remove a search node of least $f$, apply the goal test, and, if it is not a goal, insert its applicable-action children with their updated $g$ and $f$. In tree search, different action histories remain distinct search nodes even when they reach the same state; there is no global visited-state set.

For the finite branching factor and unit costs here, an admissible heuristic ensures that any first goal removed is optimal. If a cheaper solution existed, the search frontier would contain an unexpanded prefix of it with $f$ at most that cheaper cost, contradicting selection of the more expensive goal. Nonnegative $h$ also means only finitely many search nodes can have $f$ below any fixed finite cost, so a finite solution will eventually be reached. This does not guarantee termination when no proof exists.