The Eight-Kilometer Delivery

One complete A-star run on the town of Riverbend, from empty frontier to certified cheapest route.

The map, with distances: Home–Bakery 2, Home–School 3, Bakery–Park 5, School–Park 2, School–Clinic 3, Park–Grandmother's 5, Clinic–Grandmother's 2. The crow's estimates to Grandmother's: Clinic 2, Park 4, School 4, Bakery 7, Home 7 — each at or under the true remaining cost, so admissible. Start: the frontier holds Home, score 0 plus 7. Turn one: select Home; file Home–Bakery, score 2 plus 7 — nine — and Home–School, score 3 plus 4 — seven. Turn two: select Home–School at seven; file Home–School–Clinic, 6 plus 2 — eight — and Home–School–Park, 5 plus 4 — nine. Turn three: select Home–School–Clinic at eight; file Home–School–Clinic–Grandmother's, 8 plus 0 — eight. Turn four: select that finished path at eight. Goal. The route: Home, School, Clinic, Grandmother's — 8 kilometers, the true optimum. Now audit the manners: the Bakery path, scored nine at birth, was never touched again; the search examined exactly what might have beaten eight, and nothing else. Could anything have beaten eight? Only a path scoring below eight at some turn — and the ledger shows none ever did: the Bakery line opened at nine, the Park line opened at nine, and with admissible estimates a score never understates a path's true final cost. The certificate is not a boast; it is a reading of the table. Read the turns once more and notice what never happened: no path was re-filed, no estimate was revised, no judgment call was made — the strategy's entire intelligence was the score. Compare the blind runs: breadth-first found fewest roads and charged 12 kilometers for them; depth-first's answer depended on filing luck; A-star, holding a spent-plus-optimistic score, touched four paths and certified the cheapest. That is what an informed selection slot buys: provably safe laziness.