Heuristic search — where it appears
Named by 8 essays across one field — each of them below, with the objects they name alongside it.
The precondition on a function the caller writes
Dijkstra expands 1,582 cells to find a path of 98 across a fifty-square grid. The same loop, with the straight-line distance to the goal added to each key, expands 405 and finds the same 98. The estimate has to be a function the caller supplies, and the guarantee holds only while that function never overestimates — a condition on somebody else's code, not on the graph.
An estimate borrowed from an easier problem
On a grid where every step costs one, the straight-line distance to the goal cuts a search from 543 cells to 325. On terrain where steps cost between one and nine it cuts 1,572 to 1,550, because it still believes every step costs one. Four exact distance tables, computed once, cut the same search to 252 — and cost 6,328 reads to build, so they pay for themselves on the fifth query.
An estimate is a reweighting
Reprice every arc by the estimate's drop across it and run plain Dijkstra, and it expands the same 325 cells A* does, in the same order, because the two are one algorithm. Replace the estimate with one that is still never too high but drops too fast between neighbours, and 215 arcs go below zero — and on a stated grid the search that refuses to reopen a finished cell returns a path of 178 where the shortest is 169.
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.
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.
Where the landmarks stand
Four tables of exact distances, each from a chosen cell, turn a straight-line estimate that barely helps on rough terrain into one that cuts a search by a factor of six. Averaged over 1,200 queries on eight maps, the same four tables expand 126 cells a query when their cells are the map's corners and 423 when they are near its centre. The standard choice, each landmark as far as possible from the ones before, expands 141 and loses to the corners on all eight maps. Moving four landmarks to the right places buys more than doubling their number.
What the queries know that the map does not
A greedy rule that chooses landmark cells by rerunning a sample of past queries needs two hundred of them to draw level with a rule that reads only the map — and what it finally chooses, on map after map, is the four corners. Give the queries a destination instead of scattering them, and twenty are enough to beat the corners by 29% on eight maps out of eight. A query log is worth reading exactly to the extent that it is not uniform.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Shortest pathAdmissibilitySearch frontierDijkstra's algorithmPotential functionTriangle inequalityBidirectional searchBreak-evenCorrectnessCounterexampleLandmarkParameter choice