An estimate borrowed from an easier problem

The precondition on a function the caller writes measured A* as a dial. A search guided by an estimate of the remaining distance expands fewer vertices than one guided by nothing, returns the same path so long as the estimate never overestimates, and trades path quality for fewer expansions once the estimate is scaled past that point. It left one thing unexamined: where the estimate comes from. Every search on that page used the same one, the straight-line distance on the grid, and it happened to be a good estimate on the grid it was used on.

It is not a good estimate in general, and the reason it is good when it is good is worth stating precisely, because the same reason says what to use instead.

The straight line is the answer to an easier problem #

An admissible estimate has to be a lower bound on the true remaining distance from every vertex. The standard way to produce one is to relax the problem — remove a constraint, so that the problem becomes easy to solve exactly — and use the exact answer to the easier problem as the estimate. Removing constraints can only make paths shorter, so the easier problem’s answer is always a lower bound on the harder one’s.

The Manhattan distance on a grid is that construction with two constraints removed. It is the exact shortest path on the same grid with the walls deleted and every step costing one. On a maze whose steps really do cost one, only the first relaxation is doing any damage: the estimate is wrong exactly where a wall forces a detour, and right everywhere else. That is why it works.

Once the problem’s costs are not all one, the second relaxation starts doing damage too, and it does it everywhere at once. If a step costs between one and nine, the true remaining distance from any cell is roughly five times the number of steps left, and the straight-line estimate still reports the number of steps. It is admissible — nothing it says is too high — and it is about a fifth of the truth.

An estimate that is uniformly a fifth of the truth guides a search about as much as no estimate at all. A* orders its queue by distance travelled plus estimate remaining, and when the estimate is small against the distance travelled, the order is decided by the distance travelled — which is Dijkstra’s order.

Why a fifth of the truth buys almost nothing #

It is worth being precise about why an estimate that is merely too small by a constant factor is nearly useless, because “admissible” sounds like a guarantee of some benefit and gives none.

A* with an admissible estimate expands every vertex whose distance travelled plus estimate is below the cost of the shortest path, $C^*$, and possibly some on the boundary. With no estimate that is every vertex closer than $C^*$ — a disc of radius $C^*$ around the source, in cost. With an estimate $h$, a vertex at distance $g$ from the source is expanded only if $g + h(v) < C^*$, so the estimate removes exactly the vertices for which $h(v)$ is large enough to push $g + h(v)$ over the line.

If $h$ is a fifth of the true remaining distance, a vertex is pruned only if its distance from the source plus a fifth of its distance to the goal exceeds the whole path’s cost. Almost no vertex in the disc satisfies that. The ones that do are far from the goal and nearly as far from the source as the goal is — a thin crescent on the far side of the disc — and that crescent is the 22 cells the straight line saved on this terrain.

The tempting repair is to scale the estimate up by the average step cost, five, so that it is about right on average. That estimate is no longer admissible: along any route through cheap cells it overestimates, and the search may return a longer path. It is exactly the weighted search the earlier rung measured, with the weight chosen by looking at the terrain — faster, and within a factor of five of optimal rather than optimal. The largest admissible scaling of the straight line is by the cheapest step cost, which here is one, so no scaling of it helps without giving up the path. An estimate that is too small in a way that varies across the graph cannot be repaired by a constant, and the variation is the terrain.

On weighted terrain it collapses, and a landmark table does not #

The middle panel is the collapse. Its shading is almost identical to the left panel’s: the straight-line search expands cells in nearly the order Dijkstra does, sweeping out a disc of equal cost from the corner, because the estimate is too small to pull the frontier towards the goal.

The right panel uses a different estimate, and it expands a sixth as many cells.

The estimate is built from landmarks. Choose a few vertices and compute, with an ordinary Dijkstra search from each, the exact distance from that landmark to every vertex in the graph. That table costs one full search per landmark, once. Afterwards, for any vertex $v$ and goal $t$ and any landmark $L$, the triangle inequality gives

$$d(v, t) \;\ge\; \lvert\, d(L, t) - d(L, v) \,\rvert,$$

because a path from $L$ to $t$ could go through $v$, and a path from $L$ to $v$ could go through $t$. Each landmark therefore gives a lower bound on the remaining distance, and the estimate is the largest of those bounds. It is admissible for the same reason the straight line is: it is the exact answer to an easier problem — the shortest distance between two vertices if every route had to be measured along a landmark’s shortest-path tree — and it can only be too low.

What makes it good on terrain is that the easier problem kept the terrain in it.

It is also worth seeing that the construction is not special to landmarks. Every admissible estimate used in practice is the exact solution of some relaxed problem: the straight line relaxes walls and costs, a puzzle solver’s pattern database relaxes the puzzle to a smaller puzzle and stores its exact solution, and a road router’s landmark tables relax “the best route” to “the best route measured through a landmark”. What distinguishes a good estimate from a poor one is how much of the structure that makes the real problem expensive the relaxed problem kept. The straight line kept the grid and discarded the costs; on a terrain whose difficulty is entirely in the costs it kept nothing that mattered. Two parameters are not enough either made the same observation from the other end — that a graph’s cost for an algorithm often lives in structure its size parameters do not describe — and an estimate is a summary of structure in exactly that sense. The tables were computed on the real graph with the real costs, so a landmark’s estimate knows that a region is expensive to cross, which is exactly the knowledge the straight line threw away. This collection’s theme for results of this shape is that the cost model is an input rather than a background assumption: the straight line hard-codes a cost model of one per step, and a landmark table reads the cost model from the graph.

The same comparison as a count, and what the table cost #

As bars, the result is stark and it is also incomplete, because one of the three searches did work before it began that the bar does not show.

The four landmark tables are four complete Dijkstra searches over the grid — 6,328 reads, where a read is a vertex settled with its adjacency scanned, the same unit an expansion is counted in. So a single query answered with landmarks cost 252 expansions plus 6,328 reads of preprocessing, which is four times what the plain Dijkstra query cost.

That is the right way to draw it for one query, and it changes the question from “which estimate is best” to “how many queries will there be”. Each landmark query saves about 1,320 expansions against Dijkstra on this terrain, and the tables cost 6,328 once, so the tables have paid for themselves after about five queries between arbitrary points — and every query after that is a sixth of the cost.

The structure paid for before the first query is this collection’s name for exactly this accounting in a different field, and where the table starts paying finds the crossing for a precomputed table in text search. Both land on the same shape as this one: a preprocessing cost proportional to the size of the data, a per-query saving, and a break-even count that is a property of the workload rather than of the method. A route planner answering millions of queries on one road network is far past the crossing. A game computing one path on a map that changes every turn is never going to reach it.

More landmarks, fewer expansions, and faster growing costs #

The obvious next question is whether more landmarks help, and the answer is that they help less than they cost. Sixteen tables give a tighter estimate, since the maximum over more lower bounds can only be larger, and the search expands 199 cells instead of 252. But every table is a full search and a full array of distances, so the preprocessing grew in proportion to the landmark count while the per-query saving grew by 53 expansions.

The diminishing return has a geometric explanation. A landmark’s bound $\lvert d(L,t) - d(L,v)\rvert$ is tight when $v$ lies on a shortest path from $L$ to $t$ — roughly, when the landmark is behind the source or behind the goal, so that the search is moving along the landmark’s tree. The first few landmarks, chosen far apart around the edge of the graph, already put one roughly behind most source-goal pairs; further landmarks mostly duplicate directions the first ones cover.

One landmark gets most of the way. The table is one Dijkstra search, the estimate is a single subtraction, and it cuts the search to under a fifth. It works this well on this query because the landmark was chosen as the vertex farthest from the source — which, for a search from one corner towards the other, lands very close behind the goal. A landmark behind the goal gives an almost exact estimate for every cell along the way.

That is also where the method’s weakness is. The landmarks are chosen once, and a query whose goal is not near any landmark’s line gets a much looser bound. The farthest-point rule used here works greedily: the first landmark is the vertex farthest from the source, each later one is the vertex farthest from all landmarks chosen so far, and “farthest” is measured by the same exact distances the tables hold, so choosing a landmark costs nothing beyond computing its table. The rule spreads landmarks towards the extremities of the graph, which is where a landmark can be behind the most source-goal pairs. The farthest-point rule used here spreads landmarks around the boundary of the graph so that most queries have some landmark roughly in line; a workload that concentrates its queries in one region would do better with landmarks chosen for that region, which is a statement about the queries rather than about the graph.

A different grid #

The second terrain is included to check that the result is not a property of one map. The straight line again buys almost nothing — 23 cells out of 1,813 — for the same reason as before, since the terrain’s costs are drawn from the same range. The landmark estimate does even better, and the break-even count is slightly lower, because the tables cost about the same while the saving is larger.

What varies between the two grids is how well the four landmarks happen to line up with the one query. That variation is the honest error bar on the claim: a landmark estimate expands somewhere between a sixth and a fifteenth of the cells on these two maps, for this pair of corners, and nothing on this page says what the distribution over all pairs of vertices looks like.

Why the landmark estimate is consistent, not merely admissible #

There is a stronger property than admissibility that the landmark estimate has, and it matters for the next rung. An estimate $h$ is consistent if for every arc from $u$ to $v$ with cost $w$, $h(u) \le w + h(v)$ — the estimate never drops by more than the cost of a step. Consistency implies admissibility, and it is what guarantees that A* never needs to take a vertex off the queue twice.

Each landmark’s bound is consistent because distances satisfy the triangle inequality: $d(L,u) \le w + d(L,v)$ and $d(L,v) \le w + d(L,u)$ for any arc of cost $w$, so the difference $\lvert d(L,t) - d(L,\cdot)\rvert$ can change by at most $w$ across the arc. And the maximum of consistent estimates is consistent. So the landmark estimate inherits consistency from the metric it is computed in, which is the property a distance that is not a distance found missing from string costs that break the triangle inequality — and a search built on such a cost would lose this guarantee along with it.

The straight-line estimate is consistent too, since a step changes the Manhattan distance by exactly one and every step costs at least one. Both estimates on this page are therefore the well-behaved kind. What happens to a search with an estimate that is admissible but not consistent is a different measurement, and it is not a small change.

What the measurement leaves out #

Memory. Four landmark tables on a grid of 2,500 vertices are 10,000 distances, held for as long as the estimate is wanted. On a road network with tens of millions of vertices that is the dominant cost, and landmark methods are usually described in terms of it rather than in terms of preprocessing time. The table nobody has to keep is the reminder that a precomputed table is space before it is time.

A changing graph. The tables are exact distances on the graph as it was when they were computed. If a cost rises, a landmark bound may overestimate, and an overestimating bound is no longer admissible — so a landmark method on a changing graph needs either recomputation or bounds that are deliberately loosened. The straight line has no such problem, because it never read the costs.

Search from one corner to another. Every query here crosses the whole grid, which is the case where estimates matter most. A short query between neighbouring regions expands few cells under any method, and the break-even count rises accordingly.

The unit of preprocessing. A read of a vertex during preprocessing and an expansion during a query are counted alike, which is the counted-primitive convention counting on a graph established. A real preprocessing pass is sequential and a real query is scattered, and on a machine that makes scattered access dear the break-even count falls further.

The queue. Every search on this page uses the same binary heap, and the counted work includes its comparisons. The queue decides the class showed that the queue can dominate a shortest-path search’s cost on a sparse graph, and a better estimate shrinks the queue as well as the number of expansions, since fewer vertices are ever inserted. The saving from landmarks is therefore slightly larger in comparisons than in expansions, and the plates report expansions.

Where this ladder goes next: an estimate is a reweighting #

The last section named a property both estimates here have — consistency — and said what it buys: A* with a consistent estimate never takes a vertex off its queue twice. That is usually presented as a lemma. It is actually an identity, and it is worth a rung.

Replace every arc’s cost $w(u,v)$ by $w(u,v) + h(v) - h(u)$. Along any path the $h$ terms telescope, so every path’s new cost is its old cost plus a constant that depends only on the endpoints, and shortest paths do not move. The new costs are all non-negative exactly when $h$ is consistent — which is exactly Dijkstra’s precondition. So A with a consistent estimate is Dijkstra’s algorithm on reweighted arcs*, and the equivalence can be checked expansion for expansion rather than argued.

The interesting half is what happens when the estimate is admissible but inconsistent. Some reweighted arcs go negative, Dijkstra’s precondition fails, and a search that does not allow vertices to be reopened can return a path that is not the shortest. The next rung measures that failure on a stated grid, measures what reopening costs to fix it, and connects the reweighting to the one the bound with a precondition needed — where the same telescoping trick, with the estimate computed rather than supplied, is what makes negative arcs safe for Dijkstra at all.