Admissibility is not a technicality, it is what keeps A* optimal. Today you feed A* an overestimating heuristic and watch it return a worse path, proving why the estimate must never exceed the true remaining cost.
Show that an inadmissible (overestimating) heuristic makes A* return a suboptimal path.
The optimality guarantee had a condition: the heuristic must never overestimate.
Break that and A* still returns a path, but no longer the best one. Multiply Manhattan
by five and the estimate towers over the real remaining cost, so f = g + h is
dominated by h. A* becomes greedy, chasing whatever cell looks closest to the goal,
and it charges straight through the two expensive cells because that route is short in
steps even though it is dear in cost.
The moment it pops the goal (with cost 10) it stops, never having explored the cheap seven-cell detour that Dijkstra and admissible A* both find at cost 6. The lesson is sharp: a heuristic is a promise not to overstate the distance ahead, and A*’s correctness rests entirely on keeping it. Manhattan, Euclidean, and the diagonal heuristics coming up are all chosen precisely because they never overestimate. With that, four-directional A* is complete, and the next chapter builds maps worth searching.
// inadmissible: it claims far more remaining cost than really existsinadmissible := func(a, b Coord) int { return 5 * Manhattan(a, b) }// with h grossly inflated, f is dominated by h, so A* rushes toward the// goal through the expensive cells and pops the goal before it ever// explores the cheaper detour. Same search, same heap, wrong answer.