Relax the Problem

This video presents the same text shown beside it, spoken and on screen. It adds nothing the text does not say.

State

A dependable heuristic is manufactured by deleting rules from the problem, solving the easier version exactly, and using its answer as the estimate.

Show

Delete "travel on roads" and route-finding becomes a ruler: the straight line, admissible by construction.

Watch for

Every legal route is also a legal crow-flight, so the relaxed answer can only undershoot — the guarantee arrives free.

Builds on