2023 Term 1 · Afternoon — Worked Solutions

Q1 — DFS and BFS on a State Space

MoveGen table search — trace DFS and BFS to find a path from S to G, inspecting only new nodes.

Q2 — TSP Branch-and-Bound: Six Cities

A six-city TSP instance resolved via a 6-level BnB tree — the 456 tour through A,C,E,D,B,F.

Q3 — A* Search for Optimal Solution (Edge Cost 5)

A* on a uniform-cost graph (edge = 5) — the h function overestimates and A* returns S,B,F,L,G at cost 20.

Q4 — Games: Strategies, Alpha-Beta, Force MinMax

A 3-ply game tree — strategy I,K, best line B,D at 46, α-β pruning, and forcing the MinMax value to 36.

Q5 — AO* on an AND–OR Decomposition

S=10, A=12, B=2, C=6 — OR(C) wins at 8, the marker flips to AND(A,B) at 14, and S lands at 16.

Q6 — Rete Net: Vehicle Classification

Luxury-Car, Minivan and Truck all match — Truck's three conditions win specificity, Luxury-Car's ts-107 wins recency.

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

D stacks on B, C on A — the same start/goal as the 2024/2025 papers with identical answers.

Q8 — Waltz Line Labeling

A six-junction drawing with a cross-connector — the propagation wipes out to NIL.