Past exam of the computer science course of the University of Oxford / 2020 / Artificial intelligence / 1

TODO: the classifications, chosen heuristic functions and least-cost outcomes for G1–G5 cannot be established from the corrupted original Figure 1. The missing edges, costs, priority labels and lower portions of the five search trees are required inputs. The surviving portions and the two heuristic function tables do not determine those answers. No reconstructed graph or invented expansion trace is assumed.

For a readable instance, depth-first search follows the deepest pending branch and breadth-first search expands by search depth; neither generally minimizes unequal edge costs. Uniform-cost search orders by path cost $g$, whereas A-star search orders by $g+h$. A displayed A-star search score would identify the estimate by subtracting the accumulated path cost. Under nonnegative costs and the usual terminating-search assumptions, uniform-cost search returns a least-cost goal state when testing goals on removal from the search frontier; A-star search additionally needs an admissible heuristic with appropriate reopening, or a consistent heuristic for the usual closed-set implementation. These rules explain how the missing information would be used, but cannot identify a particular damaged search tree.

With the conventional strictly positive step costs, the five answers in printed order are false, false, true, true, true. The third answer needs that positivity convention: it is false in general if zero-cost edges and unrestricted ties are admitted. Take the goal test on selection from the search frontier, and assume a finite reachable problem with a reachable goal state; finite branching factor and a positive lower bound on step costs give the corresponding tree search guarantees on an infinite problem. These assumptions make the usual A-star search guarantees precise.^[ref]

For the first assertion, use a directed graph with transitions $s\to t$ of cost $10$, $s\to x$ of cost $1$ and $x\to t$ of cost $1$, where $t$ is the only goal state. The perfect heuristic is $h^{\ast }(s)=2$, $h^{\ast }(x)=1$, $h^{\ast }(t)=0$. Greedy best-first search selects the direct goal of cost $10$ because its priority is zero. The least path cost is $2$. Knowing the exact remaining distance does not account for an expensive transition already taken.

The same counterexample settles the second assertion. Greedy best-first search selects $s,t$, while A-star search selects $s,x,t$: after expanding $s$, the A-star search priorities are $2$ for $x$ and $10$ for the direct copy of $t$. Thus even the expanded state sets differ.

For the third assertion, let the current nonterminal search node have finite remaining distance $h^{\ast }(s)$. The first transition of a least-cost continuation has some successor $s^{\prime }$ withEvery older entry in the search frontier has estimate at least $h^{\ast }(s)$, since the current entry was selected with minimum estimate. A newly generated successor with strictly smaller estimate therefore wins over every older entry. Whichever new successor is selected has smaller remaining distance than the current search node, so the argument repeats. Consequently the selected search nodes form one parent–child chain; include the selected goal, or append it if “expanded” excludes goal processing. This greedy perfect-heuristic descent does not imply least path cost, as the first counterexample demonstrates.

The zero-cost qualification is substantive. Give $s$ two successors $a,b$ of cost $1$, add $a\to x$ of cost $0$, and add $x\to t$ and $b\to t$ of cost $1$. The perfect heuristic has values $2$ at $s$, $1$ at $a,b,x$ and $0$ at $t$. Alphabetical priority ties let greedy best-first search select $s,a,b,t$, which is not one graph path. Thus the unqualified third assertion requires a cost or tie convention absent from the printed text.

For the fourth assertion, a least remaining distance satisfieson every edge, by taking that edge and then a least-cost continuation. Thus $h^{\ast }$ is a consistent heuristic. The usual A-star search graph search finalizes each expanded state's least path cost and returns a least-cost goal.

For the fifth assertion, write $C^{\ast }=h^{\ast }(s_0)$. Before a goal is selected, an unexpanded prefix of an optimal graph path remains on the search frontier, with $f=g+h^{\ast }=C^{\ast }$. A-star search therefore selects only search nodes with $f\le C^{\ast }$. Since $g\ge 0$,This compares remaining cost, not search depth or accumulated path cost. The statement can fail with negative costs; those are outside the convention used here.

Let the input words be $s,t$, let $L$ be their common length, let $\Sigma$ be the finite alphabet, and let $D_L$ contain the dictionary words of length $L$. Unequal input lengths immediately make the puzzle impossible because a mutation preserves length. A word ladder search problem can use the state space $S=D_L\cup \{s\}$, with initial state $s$; including $s$ handles an input word not itself in the dictionary.

At word $w$, an action is a position–letter pair $(i,\ell )$ with $1\le i\le L$, $\ell \in \Sigma$ and $\ell \ne w_i$, permitted precisely when replacing $w_i$ by $\ell$ gives $w^{\prime }\in D_L$. The search transition model returns that $w^{\prime }$, and the goal test is $w=t$. If $s=t$, the empty sequence is accepted; if $t\notin D_L$ and $s\ne t$, no transition can reach $t$.

Assign each permitted transition cost $1$. A search node at search depth $k$ hasThus minimizing path cost is exactly minimizing the number of mutations. Uniform-cost search, with repeated states handled by graph search and the goal test on selection, finds a shortest word ladder if one exists. Because all costs are equal, breadth-first search gives the same optimal-length guarantee.

The proposed Hamming distance is both an admissible heuristic and a consistent heuristic. WriteEvery position differing from the target must change at least once along any successful word ladder. One mutation changes only one position, so every solution from $w$ has at least $h(w)$ steps. This proves $h(w)\le h^{\ast }(w)$, including an unreachable target with $h^{\ast }(w)=\infty$. Dictionary restrictions may force extra changes, but cannot remove that lower bound.

Adjacent words differ in one position, so their Hamming distances to $t$ differ by at most one. Since every transition costs one,These are exactly the consistent heuristic conditions. Equivalently, allowing all length-$L$ words gives a relaxation heuristic whose exact distance is the Hamming distance; restoring the dictionary can only increase the minimum required number of steps.

The difficulty is representing dictionary membership and the one-letter relationship in positive conjunctive STRIPS preconditions; a finite dictionary nevertheless admits an exact encoding. Pure STRIPS does not provide string indexing, a “differs in one position” operator, arbitrary disjunctive tests or a procedure that calls a dictionary lookup. Those relationships must be represented by ground facts or compiled into ground actions.

One exact whole-word encoding uses a planning fluent $\mathrm{At}(w)$ and a static predicate $\mathrm{Next}(w,w^{\prime })$ containing exactly the permitted dictionary mutations. For the action schema $\mathrm{Change}(w,w^{\prime })$, useInitialize $\mathrm{At}(s)$ and the static transition facts, and use goal $\mathrm{At}(t)$. Only one $\mathrm{At}$ fact is true initially. Each applicable ground action deletes it and adds exactly its permitted successor, so mathematical induction proves that exactly one current-word fact remains true and that every plan is a legal word ladder. Conversely, every legal word ladder directly supplies a plan. An isolated non-dictionary start is handled as in (c). A shortest plan has the fewest mutations.

This encoding moves the hard lexical relationship into preprocessing. For $N$ dictionary words, checking all ordered pairs takes $O(N^{2}L)$ character comparisons, although indexing can do better; the number of stored transitions is at most $NL(|\Sigma |-1)$ when all states are dictionary words. The STRIPS representation is finite, but its size and preprocessing cost matter.

A position-based representation instead uses planning fluents $\mathrm{Letter}(i,\ell )$. Changing position $i$ must delete its old letter and add its new one; all other positions persist through the STRIPS update rule. Merely requiring each position to contain a letter admits non-dictionary strings. A disjunction over all dictionary words is not a positive conjunctive STRIPS precondition. It can be compiled into separate ground actions, each requiring every letter of a valid source word and changing one position to reach a valid destination. This again enumerates lexical cases and can be large. Arbitrary letter changes followed by an unconstrained “validate” action are unsound: several illegal intermediate strings could otherwise lead to a legal goal. Legality must hold after every mutation, not only at the endpoint.