Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Bidirectional search — where it appears

A shortest-path search run from the source and from the goal at once, ending when the two frontiers together prove that no shorter route remains. Each search covers a smaller region than one search alone, and the rule for when to stop is where it is easy to be wrong.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

Also named here as stopping rule — the same set of essays touches all of them, so they are one junction rather than several.

stop where they meetextra path length42321stop when keys reach itextra path length110203040grid, by seedV = 900, 28% blocked, steps cost one to nine5 of 40 wrong under the meeting rule

Where two searches should stop

Search from both ends of a shortest-path query at once and the two frontiers meet somewhere in the middle, having expanded about two thirds of what one search would. Stop at the first vertex both searches have finished, and on five of forty weighted grids the path returned is longer than the shortest. The rule that is always right stops on a different condition, and on one of those grids it also stops sooner.

graphs · Graph steps cost one to ninesteps cost one01,0002,0003,000cells expanded, mean over the gridsA* from one endalways shortestalways shortesttwo-ended Dijkstraalways shortestalways shortesttwo A*, separate estimateswrong on 12always shortesttwo A*, stop on either keyalways shortestalways shortesttwo A*, averaged potentialalways shortestalways shortest40 grids a bar, 2,500 cellsestimate: straight-line cells

Two estimates that must agree

Run A* from both ends of a query at once, each search guided by its own straight-line estimate, and stop by the rule that is correct for two-ended Dijkstra. On 40 weighted grids it expands 1,002 cells on average and returns a longer path than the shortest on 12 of them. Give both searches one potential, half of one estimate minus half of the other, and the same rule is correct again — on all 40 grids, for 1,041 cells. Two estimates that measure different things cannot share a stopping rule until they are made to measure the same thing.

graphs · Graph 0.000.250.500.751.0005001,0001,500by key60% forward70% forward80% forward90% forwardone-endedhow the expansions are sharedcells expandedseparate key ÷ route40 grids, 2,500 cellsdashed: how close the separate key got to firing

A stop that is correct and never sooner

A two-ended search can stop when the two frontiers' keys together reach the best route found, and it can also stop when either frontier's own estimate reaches it alone. Both rules are safe, so a search may use whichever fires first. On forty weighted grids the second never fires: at the moment the first one stops the search, the larger of the two own-keys stands at 64% of the route. The extra rule costs 60% more counted work and a second priority queue to find that out.

graphs · Graph

Named alongside it

The objects these essays reach for when they reach for this one.

Heuristic searchSearch frontierShortest pathStopping ruleAdmissibilityCorrectnessCounterexampleDijkstra's algorithmPotential functionBookkeepingCheckConstant factor

All concepts