2022 Term 3 · Afternoon — Worked Solutions

Q1 — SEARCH

Blind BFS over the 5-4-1 water jug state space finds 221 in exactly 4 moves via 140 and 131.

Q2 — SEARCH FOR OPTIMAL SOLUTION

DFID is provably optimal only because every iteration re-inspects nodes it closed in earlier iterations.

Q3 — SEARCH FOR OPTIMAL SOLUTION

Every edge on the 10 x 10 tile grid costs more than ten rupees per Manhattan tile, so Manhattan distance can never overestimate.

Q4 — SEARCH FOR OPTIMAL SOLUTION

With unit costs and an unknown-quality heuristic, only the heuristic-free algorithms — BFS, Dijkstra and Branch-and-Bound — carry optimality guarantees.

Q5 — SEARCH FOR OPTIMAL SOLUTION

Euclidean edge costs retire BFS; the best admissible heuristic admits Dijkstra, BnB, A* and SMGS into the optimal club.

Q6 — SEARCH FOR OPTIMAL SOLUTION

In TSP Branch-and-Bound the root is every tour at once, each node is a set of tours, and bounds only ever grow on the way down.

Q7 — GAMES

Minimax backs up 59 through the left subtree while alpha-beta silently kills G, H, J, L and all of M, N, O, P without reading them.

Q8 — CONSTRAINT SATISFACTION

Forward checking binds d then 1 into instant domain wipeouts, and lands on a,e,2,5,p after one rejected value of X4.

Q9 — PROBLEM DECOMPOSITION

AO* walks S, C, D, G and backs 101, 161, 183, 194 up to the root - while h(B)=200 quietly overestimates B's real cost of 102.

Q10 — RULE BASED EXPERT SYSTEMS

Seven WMEs trickle through the Rete net; four rule-data tuples survive the joins, and specificity vs recency pick different winners.

Q11 — AUTOMATED PLANNING

Applicable actions read preconditions off the start state; relevant actions fall out of regressing the goal — Stack(D,B) and Unstack(C,B) are the unavoidable achievers.