2024 Term 3 · Forenoon — Worked Solutions

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

Best First and A* both get baited right, while Branch-and-Bound assembles the cost-14 northern chain S,A,B,D,G.

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

b1, b2, c3 — an unusual refine order where the ~BC side outranks BD's children — then d1 pops at 230.

Q3 — Game Tree: Strategies, Best Strategy, Dead Leaves, SSS*

A two-branch MAX root — strategies B and C, best line A,B at 49, dead leaves D,E,G,H, and SSS* solving A,B,C,F.

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

A on B, D on C, arm empty — three unstacks/pickups are live and the layer-1 mutexes hinge on armEmpty.

Q5 — AO* on an AND–OR Decomposition

OR(C) wins at 16, the marker flips to AND(A,B) at 22, B resolves at 24 — and E's primitive escape lands S at 30.

Q6 — Rete Net: Property Classification

Lift/3BHK/MIG and lift/gym/3BHK joins on pno — three tuples make the conflict set and specificity hands it to R2's six tests.

Q7 — Waltz Line Labeling: One NIL, One All-L1

Two four-junction drawings — the first wipes out to NIL, the second labels every junction L1.