2022 Term 3 · Forenoon — Worked Solutions

Q1 — SEARCH

A 5-3-2 water jug puzzle solved breadth-first: four moves turn 500 into 131, and BFS level-counting proves no shorter route exists.

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

When the whole search space cannot sit in memory, SMGS is the only listed algorithm whose optimality proof survives the memory cut.

Q4 — SEARCH FOR OPTIMAL SOLUTION

Edges priced 6 on a 10x10 tile grid undercut the 10-per-tile floor, so Manhattan distance overestimates along the cheap corridors — not admissible.

Q5 — SEARCH FOR OPTIMAL SOLUTION

Arbitrary edge costs retire BFS, and an unknown-quality heuristic retires everything that trusts h — only Dijkstra and Branch-and-Bound remain.

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

A 4-ply tree worth 49 at the root: two legal strategies survive scrutiny, the best one touches A,B,E,F, and Alpha-Beta kills D before anyone else.

Q8 — CONSTRAINT SATISFACTION

Forward checking assigns d, stumbles twice on X3 (two domain wipeouts), then locks 3,4,q - giving both official sequences depending on how you count retries.

Q9 — PROBLEM DECOMPOSITION

AO* on an AND-OR graph: markers hop between connectors as primitives fall, and the two counting conventions behind the dual-keyed answers.

Q10 — RULE BASED EXPERT SYSTEMS

Seven engine-shop WMEs race through the Rete net; five tuples reach the conflict set and R1 out-ranks them all on both specificity and recency.

Q11 — AUTOMATED PLANNING

Holding D opens exactly three doors right now, but relevance only blesses the two Stack actions that write goal facts directly.