A stop that is correct and never sooner

Two estimates that must agree ended on a rule it did not build. A search running from both ends with a shared potential stops when the two frontiers’ smallest keys together reach the length of the best route found so far, and that rule is correct because the two keys are lower bounds in one repriced graph. But each search’s own estimate is still a valid lower bound on any route through its own frontier, even when the two cannot be added. So a search could stop on the sum, or on either own-key reaching the route alone, whichever happened first — and the second possibility was left as a measurement.

This page makes it. The rule is correct, it is implemented, and on forty grids the second half of it never once decides anything.

The two rules, stated so they can be checked #

Write $\mu$ for the length of the best route found so far — a route through some cell both searches have reached — and let the forward search hold distances $d_f$ and the backward search $d_h$.

The sum rule. Under the averaged potential both searches are Dijkstra on one repriced graph, so the smallest key in each frontier is a lower bound on how far that frontier can still be extended, and the sum of the two is a lower bound on any route not yet found. When that sum reaches $\mu$, nothing shorter remains.

The averaged potential is what makes that sentence true, and it is not free. Giving each search its own estimate and summing the keys anyway overstates the ground still to cover — the two estimates are about different destinations — and the search can stop too early: on these same forty grids it returns a longer route than the shortest on twelve of them, while expanding 1,002 cells against the averaged potential’s 1,041. Paying 3.8% more cells to be right on all forty is the trade two estimates that must agree settled, and the own-key rule is an attempt to win some of that 3.8% back.

The own-key rule. The forward search’s own estimate gives every open cell $v$ a value $d_f(v) + h_f(v)$, which never exceeds the true length of any route through $v$. The smallest such value is therefore a lower bound on every route the forward search could still complete. When it reaches $\mu$, the forward search has nothing shorter left — and symmetrically for the backward one.

Both are sound, so a search that stops at whichever fires first returns a shortest route. That is checked rather than assumed: on forty grids the combined rule returns the same length as a one-ended Dijkstra on every one, and a machine that offers the combined rule as an earlier stop is refused by the grids on which it is not.

That plate is the warning the combined rule is built against. The own-key rule by itself was measured when the shared potential was introduced, and was already known to be slow: 3,491 cells against 1,041. The hope for the combined rule is not that the own-key is generally better, but that it is occasionally earlier — that on some grids one search proves the answer before the two of them jointly do.

Traced through one search #

The cheapest way to see whether that can happen is to record all three quantities on one grid, at every expansion.

The three lines rise together and stay in the same relation to each other throughout, and the reason is arithmetic rather than accident. Both searches advance into the same terrain at roughly the same rate, so each covers about half the route by the time they meet. Each own-key measures how far its own search has got; the sum measures how far the two of them have got between them. The sum reaches the whole route because the two halves add. Neither half reaches it because neither half is the whole.

The 64% is not 50%, and the gap between those two figures is where the real explanation is. Each own-key is a distance already walked plus an estimate of the distance still to walk, and on this terrain that second part is badly wrong. An estimate borrowed from an easier problem measured why: the straight-line count of cells is admissible on a grid whose steps cost one to nine, because every step costs at least one, and it is nearly useless there, because it believes every step costs one. An own-key therefore charges the walked half at its true price and the unwalked half at about a fifth of it.

That is a testable account rather than a story, because the estimate can be made exact by making every step cost one.

The result is sharper than a negative. On flat terrain the own-key rule fires on every grid and saves nothing, because the two rules become the same rule: when the estimate is exact, a frontier’s own key already accounts for the whole route and reaches $\mu$ at precisely the expansion where the two keys’ sum does. On rough terrain the own-key is weakened by the estimate and never fires at all.

So the second half of the combined rule fires exactly where it is redundant and is silent exactly where it would have to help. There is no terrain in between on these maps: the estimate is either exact, in which case the rules coincide, or it is not, in which case one of them is weakened and the other is not. That is the finding, and it is a statement about the relationship between the two rules rather than about forty particular grids.

Forty grids, and the same answer on every one #

One grid could be unrepresentative. It is not.

The band is four hundredths wide. Across forty grids the own-key rule fires on none, and the mean distance from firing is 0.640 — it is not close on the easy grids and far on the hard ones; it is the same distance from firing everywhere. A rule whose margin has that little variance is not a rule that occasionally helps. It is a rule with a structural reason for never helping, and the reason is the one the trace shows: the sum is the sum of two halves and the own-key is one of them.

That is a prediction from an earlier page measured and found wrong in the part that named a mechanism. The proposal was that “on grids where one search’s own estimate proves the answer sooner, the combined rule stops earlier”. No such grid was found, and the plate says why one should not be expected: the quantity that would have to vary between grids — how unevenly the two searches share the route — barely varies at all when they are alternated by key.

The proposal was not careless, and it is worth being precise about which part of it held. Its premise is exactly right: the separate estimates’ keys are valid lower bounds for their own searches even when they cannot be added, and a stop on either of them is sound. That is what makes the combined rule correct, and correctness was never the question. What the premise does not supply is any reason for the two rules to fire in the other order, and the step from “both are sound” to “the disjunction is an improvement” is the step that needed a measurement. A limit is not a prediction is the general form of that gap; here the limit is a stopping condition and the prediction was about when it would bind.

Making it fire, and what that costs #

The own-key rule can be made to fire. It requires taking away the thing that stops it: the second frontier’s contribution.

The two curves move in step, and they are the same fact twice. Giving the forward search a larger share of the expansions makes its own key a better bound on the whole route, because it is covering more of the route; it also makes the search worse, because a two-ended search is cheaper than a one-ended one for the reason where two searches should stop measured — two frontiers of radius $r/2$ hold less than one of radius $r$. At the far end the forward search is doing everything, the own-key is exactly the stop, and the search expands 1,745 cells where the sum rule expanded 1,041.

So the own-key rule fires precisely when it has been made the only rule available, and the cost of arranging that is 68% more cells. There is no setting of the alternation at which the combined rule is worth having: every step towards making the second rule usable is a larger step away from the search that made it unnecessary.

The two ends of the range, and what is known about the middle #

Two cases can be settled without a measurement, and they bracket everything above.

With no estimate at all, both potentials are zero, so a frontier’s own key is the distance already walked and the sum rule’s two keys are the two walked distances. If the forward own-key reaches $\mu$ then the sum — that same key plus a second key that cannot be negative — has reached $\mu$ too. The sum rule therefore fires no later than the own-key rule, always, on every graph, and the combined rule is exactly the sum rule with extra bookkeeping. That is a proof and not a measurement, and it is why the two-ended Dijkstra where two searches should stop measured has only ever needed the one rule.

With an exact estimate, a frontier’s own key is the true length of the shortest route through that frontier, so it reaches $\mu$ at the moment the search has proved the answer — which is the moment the sum reaches $\mu$ as well. The two rules coincide, which is what the flat-terrain grids show to the tenth of a cell.

In between, nothing is proved here. A weak estimate weakens each own-key without weakening the sum in the same proportion, and every grid measured on this page has the own-key behind; but “behind on forty grids of one family” is not “behind on every graph”, and no argument above rules out a graph on which one frontier’s estimate is strong, the other’s is weak, and the strong side’s own key arrives first. That graph is what the last section of this page asks for. What can be said is that the two settled cases are the ends of the range and neither of them is a win, so a rule that wins has to be found strictly inside it.

What the second rule costs to have available #

The rule that never fires is not free, because the quantity it tests has to be computed.

Under the averaged potential a frontier’s priority queue is ordered by $d(v) + p(v)$, where $p$ is the shared potential — not by $d(v) + h(v)$, which is what the own-key rule needs. The smallest own-key is therefore not the top of the queue the search already keeps, and finding it means either scanning that queue at every expansion or keeping a second queue ordered the other way. A scan is linear in the frontier at every step; a second queue is what is measured here.

Sixty per cent is a large number for a rule that changes nothing, and it is worth seeing where it comes from. Every relaxation that improves a distance pushes the cell onto the search’s queue, and now onto the second queue as well, at a different key; both pushes sift. Every expansion pops stale entries off the second queue before reading its top. The second queue therefore does approximately the same work as the first, and the search’s total heap work roughly doubles, which against the relaxation count gives the sixty per cent.

The space is the same story in the other currency. Measuring what an algorithm keeps is the argument that this axis has to be counted rather than assumed, and here it doubles the frontier’s storage to hold a second copy of exactly the same cells. A search that scanned the frontier instead would hold nothing extra and would pay the scan at every expansion; neither version is cheap, and both buy the same nothing.

Why an extra correct rule can be a bad rule #

There is a habit of reasoning that this result contradicts, and it is worth naming because it is not obviously wrong. Two sound stopping rules can be combined into a third that fires when either does, and the third is sound and never stops later than the better of the two. It looks like a free improvement, in the way that taking the better of two admissible estimates is a free improvement.

It is not free, for two reasons the measurement separates. The first is that “never later” is not “sometimes earlier”: whether the combination gains anything depends entirely on whether the two rules’ firing times are ever in the other order, and that is an empirical question about the searches, not a property of the rules. Here they are never in the other order, and the trace shows a structural reason.

The second is that a rule has to be evaluated to fire, and evaluation is not free when the quantity it tests is not one the algorithm already maintains. An estimate is a reweighting is why the two quantities differ at all: choosing the averaged potential is choosing which key the queue is ordered by, and the own-key is then a quantity about a different ordering of the same cells. A combined rule looks like a disjunction of two tests and is in fact a disjunction of one test and a second data structure.

The same shape appears wherever a guard is added for a case that does not arise. The depth limit that almost never fires measured a guard in real sorting code that fires on almost no input and is worth having anyway, because what it costs to have available is a comparison against a counter the algorithm already keeps. The difference between that guard and this one is not how often each fires; it is what each costs to be able to ask.

What is not measured here #

One family of maps, two estimates of one kind. Every grid is 50 × 50 with 28% of cells removed, and both terrains use the straight-line count in both directions. A map on which the forward and backward estimates differ sharply in quality — a hierarchy, where one direction is guided well and the other badly — would unbalance the two searches without unbalancing their alternation, and is the case most likely to make the own-key rule fire. It is not drawn here.

Estimates that are exact or hopeless, and nothing between. The terrain plate compares a weak estimate with an exact one. A landmark estimate on weighted terrain sits between them, and where the landmarks stand measured how far between: four tables cut a search on these grids by a factor of six without making the estimate exact. Where an own-key stalls under an estimate of that intermediate quality is not measured, though the two points here bracket it.

Corner-to-corner queries. Source and goal are the two far corners of every grid, so the two searches face terrain of similar difficulty by construction. The 0.640 figure is a statement about that arrangement.

One alternation family. The sweep takes a fixed share of expansions forward. A rule that alternated on some other quantity — the frontier sizes, the keys’ rate of increase — might produce imbalance where this one produces only waste, and nothing here rules that out.

The second queue, not a frontier scan. The 60% is the cost of one implementation of the test. A scan of the frontier at each expansion would move the cost from heap work to a linear pass and would be cheaper on small frontiers and dearer on large ones; the frontier here reaches 46 entries, so a scan would probably cost less. It would still be paid at every expansion for a test that never returns true.

Still open: an estimate that is good in one direction only #

The plate that made the own-key rule fire did it by unbalancing the work, which made the search worse at the same time. There is a way to unbalance the two searches that does not: give them estimates of different quality. A forward search guided by landmark tables and a backward search guided by the straight-line count cover very different shares of the route for the same number of expansions, and the well-guided one’s own key should then be a much better bound on the whole route than half of it.

The measurement that follows runs the two ends with estimates of deliberately different strength — landmark tables one way, straight-line the other, and a sweep of how many landmark tables the strong side gets — and asks whether the own-key rule ever fires then, by how many cells it stops the search early when it does, and whether the asymmetry costs more in expansions than the early stop saves. That is the one arrangement on which an extra correct rule could pay for its own bookkeeping, and neither plate here reaches it.