2023 Term 1 · Forenoon — Worked Solutions

Q1 — DFS and BFS on a State Space

MoveGen table search — trace DFS and BFS to find a path from S to G.

Q2 — TSP Branch-and-Bound

TSP BnB tree reading — refine order b1,c1,d2,b2, optimal leaf d5 at 366, tour A,B,D,C,E.

Q3 — A* Optimal Solution

A* on a 10x10-tile grid with edge cost 15 — Manhattan overestimates and A* returns S,C,F,K,G at cost 60.

Q4 — Games: Strategy + Alpha-Beta

Backups give root 53 via B,D; alpha-beta prunes G,H,K,L; one leaf change (E=98) forces the MinMax value to 98.

Q5 — AO* Problem Decomposition

AO* on an AND-OR graph — expansions S,C,F, S revises 36 → 28 → 30, final value 32.

Q6 — Rete Expert System

Rete net conflict resolution — Truck wins specificity with four condition tests, recency hands the fire to tuple A.

Q7 — Planning: Applicable/Relevant/Mutex

Blocks World planning graph — applicable B,C,D; relevant F,G; layer-1 mutex pairs A,B for both actions and propositions.

Q8 — Waltz Line Labeling

Waltz labeling on a six-junction drawing — answer Y3,L5,L4,T3