The precondition on a function the caller writes

Two preconditions have been measured on this ladder and both are properties of the graph. Dijkstra needs arcs that are not negative. The topological relaxation needs a graph with no cycles. Each can be checked by looking at the input, and each either holds or does not.

There is a third kind and it is a stranger object. A heuristic search takes an estimate — a function from a vertex to a guess at the remaining distance — and its guarantee holds provided that function never guesses too high. The function is written by the caller. It is not derived from the graph, it cannot be checked by inspecting the graph, and checking it by inspecting the function is undecidable in general.

That is worth sitting with, because it is a genuinely unusual thing for an algorithm to require. Every other precondition on this site restricts the data — an array of comparable elements, a graph without negative arcs, a text over a stated alphabet, weights satisfying an inequality. This one restricts a callback, and the restriction is not a type. It is a statement about the values the callback returns relative to a quantity nobody has computed yet.

One term in one expression #

The three panels are the same loop. A vertex is taken off a priority queue, its neighbours are relaxed, and improved neighbours are pushed back with a key. The only difference is what the key is:

$$\text{key}(v) = d(v) + w \cdot h(v)$$

where $d(v)$ is the best distance found so far and $h(v)$ is the estimate. At $w = 0$ the estimate is ignored and this is Dijkstra’s algorithm. At $w = 1$ it is A*. Above one it is the weighted variant.

That is genuinely all. The counted primitives are the same primitives, the queue is the same queue, the relaxation is the same relaxation. What changes is the order vertices come off the queue — which is the same observation the queue decides the class made about the queue’s implementation, arriving one level up: there the structure decided the class, here the key decides the search.

The effect of that one term is to make the search directional. Dijkstra expands in a growing disc around the source, because its key is distance from the source alone. A* expands along a corridor towards the goal, because a cell far from the goal carries a penalty even when it is close to the source. The pictures are a disc and a corridor, and the difference in area is the difference in expansions.

It is also worth noticing what the estimate does not change. The answer is identical — 58 in both panels, to the unit, which the gate requires rather than hopes for. The set of vertices reachable is identical. The graph is identical. The only thing an admissible estimate changes is how much of the graph is examined before the answer is known, which makes it the clearest instance on this site of an optimisation that is purely about avoided work rather than about a different computation. The bound with a precondition measured the opposite case, where dropping a precondition changed the answer at four vertices and nothing else.

What admissibility is, and what it guarantees #

The estimate must never exceed the true remaining distance. That is admissibility, and the guarantee it buys is that the first time the goal is taken off the queue, its recorded distance is optimal.

The argument is one line and it is worth having, because it explains what an overestimate breaks. Suppose the goal comes off the queue with a distance worse than optimal. Then some vertex on an optimal path is still in the queue, its key is its true optimal distance plus its estimate, and if the estimate never overstates, that key is at most the optimum — which is less than the goal’s key, so the goal could not have come off first.

Every step of that uses the estimate only through never overstates. It does not need the estimate to be accurate, or consistent, or even continuous. A function returning zero everywhere is admissible, which is why $w = 0$ gives the right answer: Dijkstra’s algorithm is A with the worst legal estimate.*

On a grid where every step costs one, the straight-line distance in cells is admissible for a short and complete reason: any path from a cell to the goal must change its coordinates by at least the coordinate difference, and each step changes them by one. So the estimate is a lower bound by counting, and it is tight on open ground — which is why the corridor is narrow where there are no obstacles and spreads wherever the estimate starts understating.

There is a useful way of stating what a heuristic buys that makes the grid case less special than it looks. Define the estimate’s error at a vertex as the true remaining distance minus the estimate. A vertex is expanded by A* only if its distance-from-source plus its estimate is at most the optimum — which rearranges to: a vertex is expanded only if it lies on a path whose total length exceeds the optimum by no more than the error at that vertex. So the set expanded is a neighbourhood of the optimal path whose width is the estimate’s error, and the pictures above are that neighbourhood drawn. On open ground the error is zero and the neighbourhood is the path; around an obstacle the error is the detour and the neighbourhood swells to match.

The dial past admissibility #

Scaling the estimate by $w > 1$ breaks the precondition deliberately, and the theorem that replaces the guarantee is worth stating exactly: the path returned costs at most $w$ times the optimum.

Measured on the grid at the top of this page, with an optimum of 58:

Two things in that table are worth reading carefully.

The bound is nowhere near tight. Counting on a graph makes the same observation about a traversal’s bound and this field has repeated it at every rung since. At $w = 2$ the theorem permits a path of 116 and the measured path is 64. At $w = 8$ it permits 464 and the measurement is 66. The guarantee is a worst case over graphs and estimates, and on a grid with a good estimate the realised excess is a tenth of what is allowed. That is the ordinary relationship between a bound and a measurement on this site, and it is a limit is not a prediction in its clearest form: the bound is true, it is useful for what it guarantees, and it says almost nothing about what will happen.

And the expansions stop falling. From $w = 2$ to $w = 8$ the count moves from 71 to 69. The search is already following the estimate almost exclusively, and increasing the weight cannot make it follow it more than exclusively — so the dial saturates, and every further increase is quality given away for nothing. The useful range of this parameter is narrow and its right-hand end is not where the theorem’s is.

Why the precondition is a different kind of object #

Non-negativity is a property of an input. Acyclicity is a property of an input. Admissibility is a property of a function the caller wrote, and three things follow that do not follow for the other two.

It cannot be checked by the algorithm. Verifying that $h(v) \le d^*(v)$ for every vertex requires knowing $d^*$ for every vertex, which is the problem the search was called to solve — and for one vertex rather than all of them. A library cannot validate this argument, and no library does.

It is a property of the pair, not of the function. The same estimate is admissible on one graph and not on another. Straight-line distance is admissible when every step costs at least one; on a grid where some steps cost 0.5 it is not, and the same code with the same estimate silently starts returning suboptimal paths. So a heuristic is not reusable in the way a comparison function is.

And its failure is graded rather than binary. An overestimate does not produce a wrong answer; it produces a longer answer, by an amount related to how much it overestimates. That is unlike either of the other two preconditions on this ladder — a negative arc gives Dijkstra an answer that is simply wrong at four vertices, with no notion of how wrong — and it is why the weighted variant is a usable technique rather than a bug.

The general shape is worth naming: a precondition on a supplied function is a contract, and a contract that cannot be checked is a comment. Every one of the three consequences above is a consequence of that.

Where the weighted variant is actually used #

The saturation in that table changes what the dial is for, and it is worth saying what practitioners do with it rather than leaving it as a curiosity.

The usual pattern is not to pick a weight and live with it. It is anytime search: run with a large weight, which returns a path quickly with a loose guarantee; then rerun with a smaller weight, reusing what the first run learned, which tightens the guarantee. Each run’s path is an upper bound on the optimum, each run’s weight is a multiplicative guarantee, and the process can be stopped whenever the answer is good enough or the time is up.

That converts the dial from a parameter somebody has to choose into a schedule, and the quantity that matters becomes how the excess falls with time rather than what it is at any one setting. The measurements on this page are the input to such a schedule — they say that going from a weight of eight to a weight of two costs nothing in expansions and recovers two units of path — and they are not the schedule.

The general form is one this collection meets often enough to name. A guarantee with a parameter in it is more useful as a sequence than as a choice, because a sequence lets the caller decide when to stop on evidence rather than in advance. That is exactly what a band as wide as the answer does with a band width in the tables field: run at a guess, find out whether the guess was adequate, and double it if not.

What the counter says and does not #

The expansion count is the quantity this page is about and it is not the same as the work.

An expansion scans the vertex’s adjacency and pushes its improved neighbours, so the counted work rises with expansions — but it also rises with queue operations, and a heuristic search’s queue holds keys that are sums rather than distances, which changes nothing about the comparisons’ cost. Measured on the grid at the top of the page the total counted work runs 5,686, 2,278 and 1,407 for the three panels, against expansions of 543, 168 and 71. The work ratio is smaller than the expansion ratio, because every search pays a fixed cost for the vertices near the goal that all of them must examine.

Two further things are unpriced.

The estimate is called once per push and costs nothing here. On a grid it is two subtractions. In a route planner it is a great-circle distance with trigonometry in it, and in a planner using precomputed landmarks it is a table lookup per landmark — which can be the dominant cost, and which is the reason those systems care how many times $h$ is evaluated rather than how many vertices are expanded.

And the queue is a binary heap throughout. The queue decides the class established that this choice moves the counted work by a factor of thirty-seven on the same graph, and every panel here uses the same one, so the comparison is clean and the absolute numbers are a statement about that choice as well.

What the three preconditions on this ladder now look like together #

Four rungs of this ladder have each turned on a clause at the end of a sentence, and the four are different enough to be worth tabulating by behaviour rather than by name.

Non-negative weights, from the bound with a precondition: a property of the input, unchecked by the algorithm, and its violation gives a wrong answer with no signal. The worst combination of the four.

Acyclicity, from the precondition that removes the queue: a property of the input, checkable for one comparison, and its violation is refused rather than answered. The best combination.

Connectivity, which every traversal measurement in this field needs: a property of the input, checkable, and its violation shows in the output as an incomplete traversal.

Admissibility, this page: a property of the caller’s function against the input, uncheckable in principle, and its violation degrades the answer by a bounded and measurable amount rather than breaking it.

Reading down the last column is the useful direction. A precondition is only dangerous where it is both uncheckable and silently wrong, and only one of these four is — which is a more optimistic conclusion than a reader of the second rung would expect, and it is the reason a weighted heuristic search is a technique with a name rather than a bug with a workaround.

What is not measured here #

Consistency is not distinguished from admissibility. A stronger condition — that the estimate never drops by more than the arc cost along any arc — guarantees that a vertex is never expanded twice, which admissibility alone does not. Straight-line distance on a unit grid is consistent, so nothing on this page exercises the difference, and the re-expansion behaviour of a merely admissible estimate is unmeasured.

The heuristic is the only one drawn. A real system’s estimate is a landmark bound, a contraction hierarchy or a learned function, and each has a different accuracy profile. What the plates show is what accuracy does, not what any particular way of obtaining it costs.

Nothing here is bidirectional. Searching from both ends at once is the other standard way to shrink the expanded set, it composes with a heuristic awkwardly rather than cleanly, and this site measures it nowhere.

And every grid is uniform. Every step costs one, which is what makes the straight-line distance tight on open ground. With varying terrain costs the same estimate is still admissible — scaled by the minimum cost — and much weaker, so the corridors would be wider than anything here shows.

Where a good estimate comes from #

The plates measure what an estimate is worth and say nothing about how to get one, which is the entire subject in any system that uses this.

Geometry, when the graph is embedded. A road network’s vertices have coordinates, so a straight-line distance divided by the fastest legal speed is admissible and cheap. That is the estimate this page draws, in its simplest form.

Landmarks. Pick a handful of vertices, compute the exact distance from every vertex to each of them once, and store it. Then for any query, the triangle inequality gives $|d(v, L) - d(t, L)| \le d(v, t)$ for every landmark $L$ — a lower bound, therefore admissible, and the maximum over the landmarks is the estimate. It costs one shortest-path computation per landmark in preprocessing and a few table lookups per vertex at query time, and it is far more accurate than geometry on a network where the roads do not go where the crow flies.

Abstraction. Solve a simplified version of the problem exactly and use its answer as the estimate for the real one. A puzzle’s distance-to-solved is estimated by relaxing a rule; a route’s is estimated on a coarsened graph. The relaxation guarantees admissibility, since removing constraints can only shorten the answer.

All three share a shape worth naming: an admissible estimate is the exact answer to an easier problem. Geometry is the answer with the obstacles removed; a landmark bound is the answer with a detour forced; an abstraction is the answer with a rule dropped. That is why admissibility is obtainable at all rather than being a lucky property — it comes from the relaxation being a relaxation, which is checkable by construction even though the resulting inequality is not checkable by inspection.

It also says where the effort goes. A search’s speed is decided by the estimate’s accuracy, the accuracy is decided by how close the easier problem is to the real one, and every practical advance in this area for thirty years has been an advance in constructing easier problems rather than in the search loop, which has not changed.

Where this ladder goes next: two parameters are not enough either #

The second rung of this ladder found that a graph’s cost is in two parameters, that $E \log V$ and $V^2$ have no order between them, and that which is smaller is a property of the graph rather than of the algorithm. Everything since has been written in those two.

Two is not enough. Take two graphs with the same number of vertices and the same number of edges — identical in both parameters every bound in this field is written in — one built from uniformly random pairs and the other grown by attaching to whatever is already popular. Enumerating every pair of neighbours of every vertex costs the sum of the squared degrees, and the second graph’s is more than twice the first’s. No bound in $V$ and $E$ can predict that, because the two graphs are the same point in $(V, E)$.

What makes it a rung rather than a curiosity is that the fix is known and is a third parameter with a name: pointing each edge at its busier endpoint first bounds the work by the graph’s degeneracy, which is computable in linear time, which is nearly the same on both graphs, and which appears in no statement of the problem. The measurement is a pair of graphs a two-parameter bound calls identical, doing work that differs by a factor.