2024 Term 1 · Forenoon — Worked Solutions

Q1 — Best First Search, A* and Branch-and-Bound on the Grid Map

Three algorithms, three different paths — Best First finds 14, A* finds 10, and only Branch-and-Bound uncovers the cost-8 northern route.

Q2 — TSP Branch-and-Bound: Refine Order and the 402 Tour

Queue simulation gives b1,c1,d1,d2 — then leaf e2 pops at 402 and the six-city tour reconstructs itself.

Q3 — Game Tree: Strategies, Alpha-Beta and SSS*

A three-branch MAX root with nested MAX/MIN pairs — strategies A and C, best line D,E, and five pruned leaves.

Q4 — AO* on an AND–OR Decomposition

OR(A) wins at 22, survives A's refinement to 54, then B's cheap E-branch drags S down to 24 — and E's true cost lands it at 38.

Q5 — Rete Net: Lens Classification

Convex/Plane/Concave surfaces with radius comparisons — R2's Convex-Plane pair is the only listed full match, R3 wins specificity, R6 wins recency.

Q6 — Blocks World: Applicable vs Relevant, Planning-Graph Mutexes

The arm holds D while A, B, E sit clear — applicable vs relevant splits cleanly and the layer-1 mutexes all hinge on holding(D).

Q7 — Waltz Line Labeling: Two Drawings, Both NIL

A house drawing and a podium drawing — the T-junction forces arrows, the boundary edges force W1, and both domains wipe out.