Artificial Intelligence / Unit 2 AI 0105 worked example, 60 to 90 seconds
The Gorge Trap
The idea
One purpose-built map shows greedy selection walking into a trap that an admissible, even accurate, estimate cannot prevent.
In practice
A hiking trip, Camp to Lodge, gorge between. Trails: Camp–Cliff, 1 kilometer; Cliff–Lodge, a 10-kilometer switchback; Camp–Bridge, 3; Bridge–Lodge, 3. The Cliff sits directly across the gorge from the Lodge, so the straight-line estimates read Cliff 1, Bridge 2, Camp 3 — all honest. Run greedy: from Camp the frontier holds Camp–Cliff, estimate 1, and Camp–Bridge, estimate 2. Greedy takes the Cliff. The only extension reaches the Lodge, and greedy returns Camp–Cliff–Lodge: 11 kilometers, against the 6 of Camp–Bridge–Lodge. The estimate was admissible and locally accurate — and the trap sprang anyway, because greedy never glanced at the meter running on the past.
Where people slip
The failure is the strategy's, not the estimate's — the same numbers serve a better selector perfectly.
Your place on the trail
Every lesson rests on earlier ones and opens later ones. Tap any to jump.
Unlocks
Something wrong in this lesson? Flag it · Sources for Artificial Intelligence