[October 2026 edition]

Indexes and the Art of Searching, Part 5: State-Space Search

Published: Oct 2, 2026
Reading time: ~12 min

Up through Part 4, the series dealt with cases where the candidate answers already exist as data. From Part 5 on, we move to problems where the full set of candidates cannot be surveyed, starting with searches that guarantee optimality or completeness.

1. Candidates Too Many to Survey

Consider a car navigation route. A route from origin to destination can be written as a sequence of intersections, but there are far too many routes to list them all in advance and build an index over them. The number of routes branches out with every intersection you pass. The next move in shogi (Japanese chess) or chess works the same way: each move available in a position produces the next position, and from there the moves branch again.

For car navigation, the task is to find a chain of lines from origin to destination on a map where intersections are points and the roads joining them are lines. The search program does not draw this whole map up front. It examines the roads leaving the intersection it currently stands on, adds the intersections at their far ends, and turns back instead of extending directions that look unpromising. In shogi, positions are the points and moves are the lines. Textbooks call the points states, the lines actions, the length or travel time of a road the cost, and the destination or a checkmate position the goal, and they define the problem as a search over the graph of states and actions (state space search). What separates this from the retrieval covered in Part 4, which has a criterion for matching, is that the search advances by moving back and forth between local evaluation and narrowing down the whole.

2. Basic Traversal: Breadth-First, Depth-First, and Uniform-Cost

The basic ways of traversing a state space differ in the order in which nodes are expanded. Breadth-first search expands nodes in order of their distance from the start and always finds the shallowest solution. In exchange, the number of nodes it must hold grows exponentially with depth. The idea of breadth-first search is credited to Zuse, who devised it in 1945; Moore applied it to mazes in 1959, and Lee to circuit wiring in 1961. Depth-first search follows a single path to a dead end before backing up. It needs to hold few nodes, but it returns the first solution it reaches, which carries no guarantee of being the shortest and depends on the order of traversal. With cycles or unbounded depth, the search can also run forever.

Iterative deepening depth-first search repeats depth-first search while raising the depth limit one step at a time. Shallow levels are visited many times, but because the last level holds the most nodes, the cost of repetition stays small. This lets it find the shallowest solution with memory roughly proportional to the depth. Uniform-cost search expands nodes in order of their cost from the start and returns the shortest solution even when edges have different costs. In substance it is the same as Dijkstra’s algorithm, which was conceived in 1956 and published in 1959.

Bidirectional search advances from both the start and the goal at once and makes the two meet partway. In car navigation terms, the route is connected when the search spreading out from the origin and the search spreading backward from the destination overlap at some intersection. If an average of b roads leave each intersection and the solution lies at depth d, a one-sided search to depth d examines a number of nodes on the order of b to the power d, while advancing half the distance from each side keeps the total to about b to the power d/2. This requires being able to trace which intersections lead into the destination, in other words, being able to compute transitions in reverse. Bidirectional ideas were brought into heuristic search by Pohl in 1971.

3. Cutting Branches by Estimate: Heuristics and A*

A* decides the order of expansion by f, the sum of g, the actual cost from the start to a node, and h, the estimated cost from that node to the goal. Hart, Nilsson, and Raphael proposed it in 1968 while working on path planning for the Shakey robot at SRI. If a car navigation system uses the straight-line distance to the destination as h, the estimate always falls below the actual road distance, since roads take longer ways around than a straight line. As long as the estimate errs low, a route that is truly close always looks promising by the estimate as well and gets expanded before the search ends, so the first route to reach the destination is the shortest. Textbooks call h admissible when it never exceeds the true cost, and this is the condition for reliably finding an optimal solution. A stronger condition says that when you move along a road of length d(x,y) to a neighboring intersection y, the estimate decreases by no more than the length of the road you traveled; straight-line distance satisfies it naturally, because one side of a triangle is at most the sum of the other two. In formula form, h(x) ≤ d(x,y) + h(y) holds on every edge, and this is called consistency. A consistent h is also admissible. The closer h is to the true cost, the fewer nodes are expanded, and when h is 0 everywhere, A* coincides with uniform-cost search.

Above all, how h is built determines where A* is worth using. A typical approach is to take h from the exact solution of an easier problem obtained by lifting some of the original problem’s constraints, such as straight-line distance for roads or Manhattan distance for the 15-puzzle; Part 7 covers how to construct these. The number of nodes A* holds tends to grow exponentially, and in many cases memory runs out first. Variants have therefore been developed, such as iterative deepening A*, which limits memory, and weighted A*, which relaxes optimality to gain speed.

4. Pruning by Lower Bounds: Branch and Bound and Existing Solvers

A* suits problems like shortest paths, where costs accumulate by addition. For problems such as assignment or scheduling, where the best solution is chosen from combinations of variable values, branch and bound is used. Take the problem of assigning jobs to workers one at a time so that the total cost is minimized. You split cases by who gets the first job, then split again on the next job, so the candidate assignments spread out as a tree. On a partially decided branch, if you assume each remaining job goes to its cheapest worker and add those costs, you get an estimate that no assignment further down that branch can beat. Because the value is computed with the constraint that each worker takes only one job lifted, the actual cost is equal to it or higher. If an assignment you have already found costs no more than this estimate, exploring further down the branch is wasted effort, so the whole branch can be discarded. Textbooks define the procedure as splitting the search space into a tree (branching), computing for each branch a lower bound on the solutions reachable from it, and discarding branches whose lower bound is at least the current best solution (bounding). The method was proposed by Land and Doig in 1960, and with poor-quality lower bounds it degrades almost to exhaustive search. As with the constraint lifted in the example above, lower bounds are often obtained by relaxing the problem, and this relaxation also connects to how evaluation functions are built, the topic of Part 7.

Integer programming solvers use branch and cut, which combines branch and bound with cutting planes. HiGHS is an open-source solver that handles mixed-integer programming with branch and cut, released under the MIT license. The satisfiability problem (SAT) asks whether values can be assigned to true/false variables so that all of the given conditions are satisfied at once. Most state-of-the-art solvers here use CDCL, which tentatively fixes values and moves forward, and whenever it hits a contradiction among the conditions, records the combination of values that caused it as a new condition (a clause), continuing the search while avoiding stepping into the same combination again. In the main track of SAT Competition 2025, AE-Kissat-MAB took first place by solving 173 SAT instances. Google’s OR-Tools CP-SAT combines SAT techniques with constraint programming.

These solvers have pruning and lower-bound computation built in, so once a problem is formalized and handed over, they can be used as is. Part 8 takes up the decision between writing your own search algorithm and passing the problem to an existing solver.

5. Preprocessing and Query Speed: Route Planning on Road Networks

When the same road network is queried for routes many times, it can be processed ahead of the queries. Contraction Hierarchies (CH) rank intersections by importance and add shortcuts in advance that skip over less important intersections, so that a query only needs to climb toward important roads from both the origin and the destination. Hub Labeling (HL) gives each intersection a list of distances to major relay points, and computes a distance by matching the relay points that appear in both the origin’s and the destination’s lists. In the table of a survey comparing methods on the Western European road network (about 18 million vertices), Dijkstra’s algorithm examines 9,326,696 vertices and takes 2,195,080 microseconds (about 2.2 seconds) per query. CH, with 5 minutes of preprocessing and 0.4GiB of space, examines 280 vertices and answers in 110 microseconds. HL, with 37 minutes of preprocessing and 18.8GiB, gets down to 0.56 microseconds. The extreme approach of tabulating the distances between all pairs of vertices takes 145 hours 30 minutes of preprocessing and a table of about 1.2 million GiB, for 0.06 microseconds. Because the implementation and measurement environments differ from method to method, these figures should be read as orders of magnitude.

Real systems choose an approach by weighing the cost of preprocessing against the speed of updates. OSRM has two preprocessing pipelines, CH and Multi-Level Dijkstra (MLD); its README recommends MLD as the default and says CH is still a good fit for very large distance matrices. MLD computes routes more slowly than CH, but it updates traffic information faster. GraphHopper uses CH in its speed mode, Landmarks in its hybrid mode, and Dijkstra’s algorithm and A* without preprocessing in its flexible mode.

Branches can also be cut during the search itself. Jump Point Search works on grid maps where moving to any cell costs the same, and exploits the fact that on stretches free of obstacles, continuing in a straight line is shortest. It jumps straight to cells where a new direction has to be chosen, such as the corners of walls (jump points), expands only the jump points, and skips the nodes in between. It needs no extra memory and no preprocessing, and is reported to speed up A* by an order of magnitude. On an empty map where every cell is passable, though, A* is faster than the 4-connected variant. Whether a method preprocesses does not by itself decide its speed; what matters is whether the method fits the structure of the problem.

On the complexity of Dijkstra’s algorithm itself, a theoretical improvement appeared in 2025. The paper by Duan et al. gave a deterministic O(m log^{2/3} n) time algorithm for directed graphs with non-negative weights, the first to beat Dijkstra’s O(m + n log n) on sparse graphs. The paper was also selected as the STOC 2025 best paper. This is, however, a theoretical result about asymptotic complexity; practical route planning uses approaches with preprocessing such as CH, as in OSRM and GraphHopper above.

6. Search Against an Opponent: Alpha-Beta Pruning and Transposition Tables

In two-player games, a program reads ahead on the assumption that the opponent answers each of its moves with the best reply. Alpha-beta pruning was devised independently by several researchers from the 1950s onward and analyzed by Knuth in 1975. Suppose that, while reading through your candidate moves in shogi, you finish move A and find that you keep at least a certain standing whatever the opponent does. When you start reading move B and find a single reply that leaves you worse off than A, the opponent will choose that reply, so B is settled as inferior to A without reading the rest of the replies to B. Alpha-beta pruning carries along the lower bound of the value you have already secured (alpha) and the upper bound the opponent will allow (beta), and applies this cutoff throughout the search. If a position offers b moves on average, then with the best possible move ordering, the number of nodes in a depth-n search drops from b to the power n to about b to the power n/2. The order in which moves are examined therefore has a large effect on how well the pruning works.

Different move orders often lead to the same position. A transposition table stores the results of positions already searched in a hash table and reuses them when the same position comes up again. The position hash is the Zobrist hashing mentioned in Part 2.

NNUE is an approach that builds the evaluation function through learning. Stockfish introduced NNUE in version 12 in 2020 and reported that, in matches against its handcrafted evaluation, game pairs it won outnumbered those it lost by more than 10 times. AlphaZero defeated world-champion programs in Go, chess, and shogi using only reinforcement learning from self-play. Learning evaluation functions is covered in Part 7.

Every search covered so far aims at an optimal solution. Part 6 lets go of the optimality guarantee and turns to search for cases where a good solution is enough. It explains local search and methods inspired by animal behavior, separating them into components and parameters.