2025 Term 2 · Afternoon — Worked Solutions

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

One map, three algorithms — this time the heuristic is honest, so A* and Branch-and-Bound agree on the optimal path.

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

Simulate one priority queue over the snapshot tree: refine order, the 366 tour, and why the hidden city E is forced.

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

A three-branch MAX root with nested MIN choices — valid strategies, the 56-value best line, and two pruning stories that agree.

Q4 — AO* on an AND–OR Decomposition

A marked AND-branch that gets abandoned mid-search — AO* walks away from B,C when A's real cost lands at 54.

Q5 — Rete Net: Engines, Turbines and Motors

Match WMEs through alpha/beta nodes, build the conflict set, then let specificity and recency disagree — on purpose.

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

Two towers to restack — four one-minute checks: applicable now, relevant to the goal, and both layer-1 mutex tests.