2024 Term 2 · Afternoon — Worked Solutions

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

h values are given outright — Best First detours through E and D, while A* and Branch-and-Bound both find the cost-24 southern route.

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

Queue simulation: b1, c2, d1, b2 — then leaf e1 pops at 282 and the five-city tour falls out of the degree constraints.

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

Three MIN branches under MAX — valid strategies A and C, best line D,E at 56, and six pruned leaves.

Q4 — AO* on an AND–OR Decomposition

OR(A) wins at 12, A's true cost of 54 flips the marker to AND(B,C) — and after C resolves at 18, B's 40 hands the win back to A: 56.

Q5 — Rete Net: Vehicle Classification

Same vehicle net as the 2025 papers — Luxury-Car, Minivan and Truck all match; Truck's three conditions win specificity, Luxury's ts-107 wins recency.

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

D stacks on B, C on A — the same start/goal as the 2025 T2 FN paper, with identical answers.

Q7 — Waltz Line Labeling: Two Drawings

Two line drawings, both official answers NIL — classify the junctions, force the T, propagate, and watch a domain wipe out.