Graph Search & Duplicate Detection
Why remembering visited states changes everything.
On an open grid, a breadth-first tree search to depth 20 generates more than nodes, yet only 841 cells lie within 20 steps of the start. Remembering where you have been collapses the exponential tree back into the polynomial graph it came from. This lesson proves when that is safe, what it costs, and how researchers search spaces of states that no memory can hold.
What you’ll learn
- Distinguish tree-like search from graph search, and quantify the gap on grids and other spaces full of redundant paths.
- Prove Dijkstra's invariant: with nonnegative costs, a state is popped for the first time with its optimal cost.
- Analyze graph search on explicit graphs, including decrease-key versus lazy deletion, and explain why negative costs break it.
- Describe duplicate detection at scale (frontier search, delayed and structured duplicate detection, bit-state hashing) and the landmark searches it enabled.
Trees versus graphs
Tree-like search treats every path as new. Most state spaces, however, are full of redundant paths: east-then-north and north-then-east reach the same grid cell, and undoing a move in the 8-puzzle returns to the parent's state, a cycle, which is the simplest redundant path of all. Graph search remembers the states it has reached and refuses to expand a state again along an equally good or worse path. How much does that save?
On an unbounded 4-connected grid, how many cells lie within 10 steps of the start, counting the start itself?
Show the answer
221 cells
These are the cells with : one at distance 0 and at distance , so . Tree-like BFS to depth 10 would generate million nodes to cover those 221 cells.
Every cell of an unbounded 4-connected grid has 4 neighbors, so tree-like BFS generates nodes at depth ; even if it never undoes its last move, the count is :
The states within steps are the lattice points with , and there are of them at distance exactly :
For that is about tree nodes against 841 states. Graph search expands each state once, so its cost is polynomial in : the exponential consisted entirely of redundant paths.
In a finite state space, graph search makes BFS, UCS and DFS complete (DFS can no longer cycle) and bounds their work by the number of states and transitions. The price is memory: the table holds every state seen, in the worst case, so graph-search DFS gives up its main advantage. That is why depth-first methods usually check only the current path for cycles.
Why graph search is correct: Dijkstra's invariant
Suppose, for contradiction, that is the first state popped with . Take a cheapest path from to , and let be the first state on that has not yet been expanded. Since has been expanded, has a predecessor on :
was popped before , so by the choice of it was expanded with . Expanding put on the frontier with cost at most , which equals because every prefix of a cheapest path is a cheapest path:
Nonnegative costs make nondecreasing along , so precedes in the priority queue, contradicting that is popped now. (If , the bound gives directly.)
On an explicit graph, breadth-first graph search runs in time. Dijkstra's algorithm takes with a binary heap and with a Fibonacci heap (Fredman & Tarjan, 1987). Instead of decreasing the key of a frontier entry, most implementations push a new copy and skip stale copies when they are popped (lazy deletion), which costs with at most heap entries and is usually faster in practice. The search widget and the Hidden Layer's pseudocode both work this way.
Where does the proof of Dijkstra's invariant use the assumption that edge costs are nonnegative?
- To guarantee that the frontier never becomes empty
- To make the priority queue efficient
- To conclude for a state that comes before on a cheapest path
- To ensure that the graph is finite
Show the answer
C. To conclude for a state that comes before on a cheapest path
Along a cheapest path, can only grow when every edge costs at least 0. That places the frontier state ahead of in the queue and gives the contradiction. With one negative edge, can be cheaper than the states before it, and both the argument and the algorithm fail.
Duplicate detection at scale
Duplicate detection needs a set with fast membership tests: in memory, a hash table keyed by a compact encoding of the state. Memory then becomes the limit. The 15-puzzle has reachable states, so even at one byte per state a complete search needs about 10 terabytes. Breadth-first order helps: in an undirected graph with unit costs, the neighbors of a node at depth lie at depths , or , so duplicates can be removed one layer at a time, in batches. Four ideas push past the limits of RAM:
| Technique | Idea | Introduced by |
|---|---|---|
| Frontier search | Keep only the frontier, not the expanded states. Each frontier node records which operators lead to already-expanded neighbors and never applies them. | Korf, Zhang, Thayer & Hohwald (2005) |
| Delayed duplicate detection | Append generated nodes to disk unsorted, and remove duplicates in bulk, by sorting or hashing, once per layer. | Korf (2003, 2008) |
| Structured duplicate detection | Partition the states with an abstraction so that a node's successors fall into a few partitions, and keep only those partitions in RAM. | Zhou & Hansen (2004) |
| Bit-state hashing | Store a single bit per hash value. A collision can wrongly prune an unseen state, trading completeness for coverage. | Holzmann, in the SPIN model checker |
Transpositions, reopening and symbolic search
Game trees are full of transpositions: different move orders reach the same position. Chess engines store the results of positions they have searched in a transposition table, a hash table keyed by a 64-bit Zobrist hash. Each (piece, square) pair gets a fixed random bit string, a position's key is the XOR of the strings of its pieces, and a move updates the key with a handful of XORs (Zobrist, 1970). Collisions are possible but rare, and engines tolerate them.
With a heuristic, the expansion order is by rather than by , and graph search interacts with it. If is consistent, A* expands each state once, with its optimal , exactly like Dijkstra's algorithm on reduced costs. If is admissible but inconsistent, a cheaper path to an already-expanded state can turn up later, and the state must be reopened; Martelli (1977) showed that this can force exponentially many expansions in the number of states. A* Optimality & Efficiency Proofs has the details.
Model checkers, which verify hardware and software designs by exhaustive search over their states, meet the same wall under the name state-space explosion. Besides hashing tricks they use symmetry reduction, partial-order reduction (exploring only one order of independent actions) and symbolic search, which represents whole sets of states, such as a breadth-first layer, as binary decision diagrams and computes all their successors in one operation (McMillan, 1993).
Key takeaways
- Graph search eliminates redundant paths at the price of memory: on a grid, states instead of tree nodes. In finite spaces it makes BFS, UCS and DFS complete.
- Dijkstra's invariant: with nonnegative costs, a state popped for the first time has its optimal cost, by frontier separation. Negative costs break it.
- On explicit graphs, BFS takes time and Dijkstra's algorithm with Fibonacci heaps; lazy deletion, at , is the practical alternative to decrease-key.
- At scale, duplicate detection moves to disk and to the frontier: delayed and structured duplicate detection and frontier search made a complete breadth-first search of the 15-puzzle possible, showing that every position is within 80 moves.
- Transposition tables keyed by Zobrist hashes bring duplicate detection to game search; inconsistent heuristics force reopening, which can cost exponentially many expansions.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
On an open 4-connected grid, how does the number of states that breadth-first graph search expands before reaching a goal at distance grow?
Show the answer
B.
It expands the states closer than the goal, up to of them. Tree-like search generates nodes, or with parent pruning.
A uniform-cost search implementation pushes a new copy of a state whenever it finds a cheaper path to it, instead of decreasing a key. What must it do when it pops a node?
- Skip the node if its exceeds the best cost recorded for its state
- Expand every copy, since each may lead somewhere new
- Nothing special: stale copies are never popped
- Restart the search from the cheaper copy
Show the answer
A. Skip the node if its exceeds the best cost recorded for its state
The cheaper copy is popped first and expands the state with its optimal cost. A later, stale copy would only regenerate successors with worse costs, so it is skipped. The heap then holds at most entries, for time in total.
What does frontier search (Korf, Zhang, Thayer & Hohwald, 2005) avoid storing, and how does it still avoid regenerating expanded states?
- It stores no frontier, only the expanded states
- It writes every node to disk and never removes duplicates
- It stores only the start and the goal and recomputes everything else
- It stores no expanded states; each frontier node records which of its operators lead to already-expanded neighbors, and those operators are never applied
Show the answer
D. It stores no expanded states; each frontier node records which of its operators lead to already-expanded neighbors, and those operators are never applied
In an undirected graph, the neighbors of a frontier node are frontier or expanded nodes, so marking the operators that lead back into the expanded region keeps the search from regenerating it. Memory then scales with the frontier, often far smaller than the explored region, and the solution path is recovered by divide and conquer.
Why can a chess engine afford to look up every position it reaches in a transposition table?
- Because positions never repeat in chess
- Because the table stores only checkmates
- Because Zobrist hashing updates a 64-bit key with a few XORs per move, so each lookup costs
- Because hash collisions are impossible with 64-bit keys
Show the answer
C. Because Zobrist hashing updates a 64-bit key with a few XORs per move, so each lookup costs
Each (piece, square) pair has a fixed random 64-bit string, and a position's key is the XOR of the strings of its pieces. A move changes only two or three of them, so the key is updated incrementally. Collisions are possible but rare, and engines tolerate them.
Further reading
- E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik 1 (1959), 269–271.
- R. E. Korf, W. Zhang, I. Thayer & H. Hohwald, "Frontier search," Journal of the ACM 52(5) (2005), 715–748.
- R. E. Korf, "Linear-time disk-based implicit graph search," Journal of the ACM 55(6) (2008).
- T. Rokicki, H. Kociemba, M. Davidson & J. Dethridge, "The diameter of the Rubik's Cube group is twenty," SIAM Journal on Discrete Mathematics 27(2) (2013), 1082–1105.
- S. Edelkamp & S. Schrödl, Heuristic Search: Theory and Applications (Morgan Kaufmann, 2012).