= Solution
\b[None of the three variants is an <optimal search algorithm> in general.] The following single <search tree> supplies counterexamples for all three. Its <heuristic function> is nonnegative, admissible and even a <consistent heuristic>.
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2021/artificial-intelligence-search-priorities.png]
{title=One four-node search tree showing the failure of each altered A-star rule}
The least-cost goal is $G_4$, reached at cost $1+3=4$; the other goal $G_5$ costs $5$. Assign $h(S)=0$, $h(P)=3$, and zero to both goals. For the first variant, expanding $S$ generates $G_5$ and immediately returns it, before $P$ can be expanded. A <goal test> at generation therefore returns cost $5$.
For priority $g(n)+h(n')$, the root's children have priorities $1$ for $P$ and $5$ for $G_5$. Expanding $P$ generates $G_4$ with priority $4+3=7$. The algorithm next selects $G_5$, again returning cost $5$.
For priority $g(n')+h(n)$, the root's children instead have priorities $3$ for $P$ and $0$ for $G_5$. The suboptimal goal is selected immediately. The example uses no tie-breaking assumption. In contrast, ordinary <A-star search> with its <goal test> on selection compares the genuine estimated total costs and returns $G_4$.
Back to article page
