search
Shortest path through the map
It is the dawn of practical routing, and a road network of a million nodes sits between a traveler and a destination — and someone is waiting, tapping a screen, for an answer in a fraction of a second. Find provably optimal routes fast enough for interactive use. Blind exploration of a million-node graph is far too slow; guide the search with an admissible heuristic — an estimate that never overpromises distance-to-goal — so vast regions can be pruned while the returned route stays provably shortest. Get it wrong and you return routes fast but subtly suboptimal, quietly wasting time and fuel, or compute the true optimum too slowly to be usable — the art is provable optimality that returns before the user gives up.
Who this problem belongs to
The two figures whose methods fit it best, out of 69 in contention.
This is Dijkstra's problem in the most literal sense available in this game: his 1959 paper 'A Note on Two Problems in Connexion with Graphs' gave the shortest-path algorithm that every routing engine descends from, reportedly conceived in twenty minutes at a café while thinking about Dutch cities. The label-setting method with its correctness argument — settled nodes carry provably final distances — is the foundation A* merely accelerates with a goal-directed reweighting. And the problem's other demand, 'provably,' is Dijkstra's second signature: he spent the rest of his career insisting programs be derived with proofs, so the optimality guarantee would be stated and defended in his style. Gaps exist — admissible heuristics (1968) and million-node preprocessing are others' contributions — but no one's actual historical toolkit sits closer to this problem's center.
Before Bayesian networks made him famous, Pearl wrote the book on this exact problem: 'Heuristics: Intelligent Search Strategies for Computer Problem Solving' (1984) is the definitive theoretical treatment of A* — admissibility, consistency, conditions for node-expansion optimality, the precise relationship between heuristic accuracy and search effort, and analyses of when and why heuristics prune exponentially. Where Hart, Nilsson, and Raphael introduced A* in 1968, Pearl and his students (including the branch-and-bound connections and semi-admissible relaxations) explained it, quantifying exactly the trade this problem stages between provable optimality and speed. If the question is 'why does an admissible heuristic let you prune vast regions and still guarantee the shortest route,' Pearl authored the standard answers. Only the million-node systems engineering lies outside his contribution; the intellectual core is his home ground.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
69 figures are scored on this problem. Draw it in a battle to see where you land.