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

The first assertion is false. Give the root a first child that is a goal state of cost ten and another child leading to many cheaper non-goal search nodes. Depth-first search can take the first child and stop immediately. A-star search with the admissible heuristic $h=0$ behaves as uniform-cost search and expands the cheaper non-goal search nodes before selecting that goal. Thus an admissible heuristic does not make A-star search expand fewer nodes than every possible depth-first search ordering. The latter need not return an optimal solution.

The second assertion is true under the usual finite-branching factor assumption. Breadth-first search orders by search depth, not path cost. Every finite depth contains finitely many search nodes, so a goal at finite depth is eventually reached even if some steps cost zero. Zero-cost steps can affect cost optimality, but do not obstruct this completeness argument. An infinite branching factor would invalidate the argument irrespective of step costs.

The third assertion is true as a worst-case black-box requirement, with a finite optimum assumed. If outgoing actions are known only by expanding a state, an unexamined reachable branch can conceal a sufficiently negative-cost action followed by a route to a goal. Its total cost can beat the current solution by an arbitrarily large amount. Without additional lower bounds or structural information, finding one cheap solution cannot justify stopping; exhaustive examination can be necessary. This does not assert that every already-described irrelevant state must be visited on every input. Moreover, a reachable negative-cost cycle in a graph that can still reach a goal can make costs unbounded below, in which case no finite-cost optimal solution exists at all.

Iterative deepening depth-first search increases a bound on the number of actions, usually through $0,1,2,\dots$. Iterative lengthening search instead bounds accumulated path cost; after an unsuccessful pass, its next bound is the least path cost among the rejected search nodes. Thus it can distinguish shallow expensive paths from deeper cheap ones.

Both repeatedly perform depth-first search and retain its small active-path storage, trading repeated work for avoiding a large search frontier. With unit step costs their bounds coincide. With unequal positive step costs, iterative deepening depth-first search finds a solution with the fewest actions, while iterative lengthening search, under the termination conditions discussed next, finds one of least total cost. Real-valued path costs can make iterative lengthening search perform many more passes than the depth-bounded method.

Start the threshold at zero and let $C^{\ast }$ be the least solution cost. Suppose an unsuccessful pass has threshold $L<C^{\ast }$. Along an optimal action sequence, take the first prefix whose path cost exceeds $L$. Its preceding prefix is explored, so that rejected prefix contributes to the next-threshold calculation. Positive step costs imply that its cost is at most $C^{\ast }$. Therefore the next threshold is also at most $C^{\ast }$.

By induction, no threshold used before the first solution exceeds $C^{\ast }$. A returned goal state therefore has cost at most $C^{\ast }$; by the definition of $C^{\ast }$ it cannot cost less. The first returned solution is optimal.

The termination qualification matters. In a finitely branching problem with step costs at least $ϵ>0$, a threshold $L$ admits only depths up to $\lfloor L/ϵ\rfloor$, so each pass is finite and only finitely many path costs precede $C^{\ast }$. These conditions establish completeness as well. Strict positivity alone on an arbitrary infinite tree is insufficient: an infinite branch with costs $1/2,1/4,1/8,\dots$ can remain below a finite threshold and trap depth-first search. The optimality argument above is valid whenever the required passes terminate; a finite graph with finitely many strictly positive action costs supplies a uniform positive lower bound.

With initial threshold zero and unit step costs, the thresholds are $0,1,\dots ,d$, so there are $d+1$ passes. Starting the first pass at one instead omits the zero-threshold pass when the root is not a goal.

At depth $i$, at most $b^i$ search nodes are admitted in each pass with threshold at least $i$. Across all passes, the full-to-cutoff visit bound isThis is attained when the only depth-$d$ goal is visited last. If a goal test occurs before expansion, the goal is visited but not expanded, giving the corresponding worst-case expansion countFor $b\ne 1$, the visit bound is $V(b,d)=[b^{d+2}-(d+2)b+d+1]/(b-1{)}^2$, hence the worst-case number expanded is $\Theta (b^d)$ for fixed $b>1$. For $b=1$, it is $\Theta (d^2)$. An earlier goal reduces the final pass, so its exact count cannot be inferred from $b,d$ alone. Children generated and immediately rejected above a threshold are not counted as expanded; counting those generated nodes adds the corresponding branching overhead.

A lower bound on individual step costs does not bound the difference between consecutive path cost thresholds. Two different paths can have costs differing by an arbitrarily small amount, even though every edge costs at least $ϵ$.

Let $C^{\ast }$ be the optimal solution cost. Every unsuccessful threshold is the path cost of some search node below $C^{\ast }$. Such a node has depth strictly less than $C^{\ast }/ϵ$. For a uniform branching factor $b>1$, the number of passes is therefore bounded byIf a solution of depth $d$ exists, each of its edges costs at most one, so $C^{\ast }\le d$ and an associated bound is $O(b^{\lceil d/ϵ\rceil })$ passes. If $d$ denotes the optimal solution's depth, the same inequality applies. With no solution-cost or solution-depth bound, $b$ and $ϵ$ alone give no finite uniform iteration bound.

The exponential behavior is possible. Put a depth-$d$ goal on a branch with unit costs and let a large competing subtree use costs just above $ϵ$. Choose tiny distinct perturbations so that its many search nodes below cost $d$ have distinct path costs. The threshold can advance through those costs one at a time. Thus a bound such as $\lceil d/ϵ\rceil$ on the number of passes is unjustified: it bounds admitted depth, not the number of distinct costs. For $b=1$ there is only one path, so the corresponding count is linear in the admitted depth rather than exponential.

For the three-colourability problem, represent a candidate by a complete colour assignment $c:V\to \{r,g,b\}$, initially chosen at random. Give it the conflict objective functionA neighbor changes the colour of one vertex to either other colour. For hill climbing, maximize $-H$, or equivalently repeatedly choose a recolouring that reduces $H$. One can inspect all $2|V|$ neighbors, or focus on conflicted vertices and evaluate their alternative colours using only incident edges. Stop successfully as soon as $H=0$, which is exactly a proper graph colouring with three colours.

If no improving move exists at positive $H$, the method is stuck in a local minimum. Random restarts, limited sideways moves or other exploratory local search choices can reduce this failure mode, but do not turn a finite unsuccessful run into a proof of impossibility. On a graph with no proper graph colouring using three colours, every complete colouring has $H>0$, so this procedure cannot return a valid colouring. Conversely, a positive-conflict stopping point also occurs on some graphs admitting a proper graph colouring with three colours. Failure of hill climbing alone does not certify non-colourability. For a concrete trap, use a bipartite graph with three vertices on each side and every cross-edge, and give each side one vertex of each colour. There are three conflicts. Recolouring any single vertex leaves it with exactly one same-colour neighbor, so no single change improves $H$, even though colouring each whole side differently solves the instance.

For an action sequence $\pi$, let $T_{\pi }(B)$ be the set of all physical states obtainable by applying it to the initial belief state $B$. Under a deterministic model this is an image; for nondeterministic outcomes it is the union of all permitted images. For $B^{\prime }\subseteq B$,If each action is applicable to every current possibility from $B$, it is also applicable to every possibility from $B^{\prime }$. If the final belief state for $B$ is contained in the physical goal set $G$, then $T_{\pi }(B^{\prime })\subseteq G$. Thus the same plan solves every subset of $B$.

Nothing comparable follows for an arbitrary superset. For example, let an action take $s_1$ to a goal and leave $s_2$ at a non-goal. It solves $\{s_1\}$ but not $\{s_1,s_2\}$. A larger belief state is solved by this particular sequence exactly when all added states also permit it and end in $G$. It may succeed on some supersets and fail on others; it cannot be guaranteed merely from success on $B$.

Use incremental belief-state search to find only the initial possibilities needed to constrain a successful plan. Choose one possible initial state, or a small subset $B_0$ of the full initial belief state $B$. Find an action sequence solving this restricted problem, then simulate it from every state in $B$.

If validation succeeds, return the candidate. Otherwise choose a state that makes some action inapplicable or ends outside the goal, add it to $B_0$, and search again for a plan that works for every selected state. Replanning can revise the earlier sequence; merely appending a repair to one arbitrary candidate can miss solutions. For a finite initial belief state, there are at most $|B|$ additions before every initial possibility has been included. If a complete restricted solver proves that even the selected subset is unsolvable, part (g) shows that the full problem is unsolvable.

The benefits are smaller intermediate belief states, fewer states propagated through candidate actions, and avoidance of unnecessary portions of the full power set search space. One physical-state counterexample can eliminate many invalid candidates. The worst case can still require all initial states; the method exploits instances where a few representative possibilities already force a plan that passes universal validation.