In A* on a road map, what must the heuristic guarantee for the returned route to stay optimal?

## The one-line difference from Dijkstra Dijkstra pops the frontier vertex with the smallest `g(n)` - cost accumulated from the source. A* pops the smallest `f(n) = g(n) + h(n)`, where `h(n)` is a guess at the cost still to come from `n` to a **specific goal**. Everything else - relaxation, the settled set, the priority queue - is identical. A* is therefore a goal-directed Dijkstra: it spends its expansions on vertices that look like they lie toward the destination instead of expanding a symmetric ball in every direction. Set `h(n) = 0` everywhere and `f = g`: A* *is* Dijkstra. That equivalence is worth saying out loud in an interview, because it makes the rest of the discussion about `h` alone. ## Admissibility: the optimality condition `h` is **admissible** when, for every vertex `n`, `h(n) <= h*(n)`, the true cost of the cheapest remaining route from `n` to the goal. In words: the heuristic may be optimistic but never pessimistic. Why this is exactly the right condition: A* returns a route when the goal is popped. Suppose it popped the goal with cost `C` while a cheaper route of cost `C' < C` existed. That cheaper route has some vertex `n` still on the frontier, whose key is `f(n) = g(n) + h(n) <= g(n) + h*(n) = C' < C`. A smaller key was sitting in the queue, so the goal could not have been popped first - contradiction. The inequality that makes this work is precisely `h(n) <= h*(n)`. ## Consistency: the condition that removes reopening Admissibility alone guarantees the final answer but does not guarantee that a vertex settled once stays settled; a merely-admissible heuristic can require reopening a closed vertex when a cheaper route to it turns up later. **Consistency** (or monotonicity) - `h(u) <= w(u, v) + h(v)` for every edge, and `h(goal) = 0` - makes `f` non-decreasing along any route, which restores the exact Dijkstra invariant: the first time you pop a vertex, its `g` is final. Every consistent heuristic is admissible. In practice most natural geometric heuristics are consistent, which is why implementations get away with a plain settled-set check. ## The courier map, and the units trap On a road map, the obvious `h` is straight-line distance from an intersection to the destination. If edge weights are **distances**, that is admissible by the triangle inequality - no road route can be shorter than the straight line - and it is consistent too. Now switch the weights to **travel time in seconds**, which is what a courier service actually optimizes, and keep `h` in metres. The comparison `g + h` is now adding seconds to metres, and the heuristic dwarfs the real costs; it wildly overestimates and the route you get is arbitrary. The fix is a unit conversion using an upper bound on speed: `h(n) = straight_line_metres(n, goal) / max_speed_metres_per_second`. That is a genuine lower bound on remaining travel time, so it is admissible. Note the direction: dividing by the **maximum** speed makes the estimate as small as it needs to be. Divide by an average speed and you are inadmissible again. ## What an inadmissible heuristic actually costs Nothing crashes. The search terminates, returns a route, and reports success. It is simply not guaranteed to be the cheapest one, and nothing in the output says so. That silence is why inadmissible heuristics survive code review and turn up months later as "why did it route the van through the industrial estate?" Sometimes the trade is deliberate. Multiplying an admissible `h` by a factor `1 + e` (weighted A*) expands far fewer vertices and returns a route guaranteed to cost at most `(1 + e)` times optimal. That is a legitimate engineering decision **when the bound is stated and accepted**; the defect is inadmissibility that nobody chose. ## What a better heuristic buys, and what it does not Among admissible heuristics, a larger one dominates: it expands no more vertices than a smaller one. The extreme is `h = h*`, which walks straight to the goal. But the worst-case asymptotic bound is unchanged - on a map where the heuristic carries no information, A* expands what Dijkstra expands, plus the cost of evaluating `h` at every vertex. And A* is a *goal-directed* method: for a one-to-all query there is no goal to aim at, so there is nothing for it to do. Choosing A* also means paying for `h` at every expansion, which for an expensive heuristic can outweigh the expansions it saves.