2025 Term 3 · Forenoon — Worked Solutions

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

A* gets baited by B's low h into a cost-5 path while Branch-and-Bound quietly assembles the cost-4 route through C and F.

Q2 — Alpha-Beta Mid-Flight: The Cutoff Value of N

Even evals only — N = 2 slips under α = 4 at the MIN parent and cuts off its siblings: an α-cutoff.

Q3 — SSS* with Two Root Branches

All four leaves get evaluated and solved — then A, C and D leave the queue when their MAX ancestors resolve.

Q4 — AO* with a Double Marker Switch

AND(B,C) wins, survives C's refinement, then G's true cost of 18 flips B onto primitive K — S lands at 28.

Q5 — Rete Net: Vehicle Classification

Limit 8 makes a Minivan, hp 900 with limit 2 a Luxury-Car — and Truck's three conditions win specificity.

Q6 — Planning Theory: Orderings, Mutex Conditions, All-Producers

The mirror of the AN paper: which condition makes the two orderings disagree, and the ALL-producers test stated positively.

Q7 — GraphPlan Mid-Flight: Populating Layer k+1

Four mutex pairs in layer k rule out the start state — then Putdown(A), Stack(A,B) and Unstack(A,B) populate layer k+1.

Q8 — CSP: Arc Consistency, Path Consistency, Solution

A = 3 has no support on R_AC — not arc consistent; pruning it cascades to a unique solution 2,6,8.