2025 Term 3 · Afternoon — Worked Solutions

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

A tie between C and D decides Best First Search, A* settles for 5, and only Branch-and-Bound uncovers the hidden cost-4 route.

Q2 — Alpha-Beta Mid-Flight: The Cutoff Value of N

Five evals on the current path pin the window at N — the smallest odd value ≥ 11 cuts off, and it's a β-cutoff.

Q3 — SSS* on a Deep Narrow Tree

A single MIN child under the root means SSS* walks the whole tree — every leaf gets SOLVED, nothing is pruned.

Q4 — AO* on the AND–OR Decomposition

Four expansions down the A-branch — and the E refinement that flips A onto its primitive I escape hatch.

Q5 — Rete Net: Vehicle Classification

Three vehicles, three rules, one tie — specificity hands it to Truck, recency hands it to F1-Car.

Q6 — Planning Theory: Orderings, Mutex Conditions, Non-Mutex

Three definition questions — when orderings matter, the four action-mutex tests, and the ALL-producers rule flipped.

Q7 — GraphPlan Mid-Flight: Populating Layer k+1

Layer k carries mutex pairs, so it can't be a start state — then Pickup(B), Putdown(A) and Stack(A,B) populate layer k+1.

Q8 — CSP: Arc Consistency, Path Consistency, Solution

Sparse relations over {1..9} — the matching diagram is arc consistent, path consistency fails on (2,6), and 3,5,7 saves the day.