The Gorge Trap

One purpose-built map shows greedy selection walking into a trap that an admissible, even accurate, estimate cannot prevent.

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.