2024 Term 2 · Forenoon — Worked Solutions

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

Best First wanders through E and D, while A* and Branch-and-Bound both settle on the cost-24 C–G express lane.

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

Queue simulation: b1, c2, d1, b2 — then d3 pops at 244 and the excluded AD edge forces the five-city loop.

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

A deep MIN-heavy tree — strategies A and C, best line I,J at 56, and six pruned leaves.

Q4 — AO* on an AND–OR Decomposition

OR(C) wins at 12, C's true cost of 54 flips the marker to AND(A,B) — and A's primitive pair drags it to 56.

Q5 — Rete Net: Vehicle Classification

F1-Car (slick + limit-1 + hp≥700), Luxury-Car and Truck all match — Truck's three conditions win specificity, F1-Car's ts-109 wins recency.

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

D stacks on A, E on B — the same start/goal as the AN paper with identical answers.

Q7 — Waltz Line Labeling: One Solvable, One NIL

A rare treat — 7.1 actually has a consistent labeling (L4, L2, W2, T3) — while 7.2's drawing wipes out to NIL.