2025 Term 1 · Afternoon — Worked Solutions

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

Three algorithms, one map — why each returns a different path, and why only Branch-and-Bound finds the shortest one.

Q2 — Reading a TSP Branch-and-Bound Search Tree

The search tree is the answer sheet: refine order, optimal tour, number of cities — all extracted by simulating one priority queue.

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

One game tree, four questions — what a strategy really is, where Alpha-Beta cuts, and which leaves SSS* actually solves.

Q4 — AO* on an AND–OR Decomposition

Trace AO* expansion by expansion — marked arcs, cost revision, and why S finally settles at 44.

Q5 — Rete Net: Conflict Set, Specificity, Recency

Place every WME in its alpha node, join through the beta network, build the conflict set — then let specificity and recency fight over who fires.

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

One start state, one goal — four checks that take a minute each: applicable actions, relevant actions, and both mutex tests in layer 1.

Q7 — Waltz Line Labeling: Is the Drawing Consistent?

Classify six junctions, propagate edge labels from the T-junction outward — and watch every branch die. NIL.