2025 Term 2 · Forenoon — Worked Solutions

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

A tie at f=20 makes A* work hard for the win — full traces for all three algorithms on an admissible map.

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

Queue simulation gives the refine order b1,c2,b2,c3 — then d3 pops as the 434 tour over five forced cities.

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

Three MIN branches under MAX — the 54 value hides behind a β-cutoff at the very first MAX grandchild.

Q4 — AO* with Edge Cost 10: a Marker That Switches Twice

AND(A,B) looks cheap, gets abandoned for C, then re-wins after B's true cost lands — S settles at 80.

Q5 — Rete Net: Diesel and Petrol Engines

Crankshafts, armatures and line counts — the conflict set has four tuples, and specificity and recency disagree.

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

D and C sit loose on a pile — unstack them, pick up E, then run the four layer-1 checks.

Q7 — Map Colouring CSP: Arc Consistency, Path Consistency, Solution

Three mutually adjacent regions, domains {r,b,g}/{r,b}/{r,b} — arc consistent, NOT path consistent, but solvable: g,r,b.