Simple Algorithm
Artificial Intelligence · Deep Layer · 24 min

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 101210^{12} 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 101310^{13} 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?

Predict before you look

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 ∣x∣+∣y∣≤10\abs x+\abs y\le10: one at distance 0 and 4k4k at distance kk, so 1+4(1+2+⋯+10)=221=2⋅102+2⋅10+11+4(1+2+\cdots+10)=221=2\cdot10^2+2\cdot10+1. Tree-like BFS to depth 10 would generate (411−1)/3≈1.4(4^{11}-1)/3\approx1.4 million nodes to cover those 221 cells.

DerivationCounting the gap on a grid
  1. ∑k=0d4k=4d+1−13\sum_{k=0}^{d}4^k=\frac{4^{d+1}-1}{3}

    Every cell of an unbounded 4-connected grid has 4 neighbors, so tree-like BFS generates 4k4^k nodes at depth kk; even if it never undoes its last move, the count is Θ(3k)\Theta(3^k):

  2. #{(x,y):∣x∣+∣y∣≤d}=1+∑k=1d4k=2d2+2d+1\#\{(x,y):\abs x+\abs y\le d\}=1+\sum_{k=1}^{d}4k=2d^2+2d+1

    The states within dd steps are the lattice points with ∣x∣+∣y∣≤d\abs x+\abs y\le d, and there are 4k4k of them at distance exactly k≥1k\ge1:

  3. (421−1)/3841≈1.7×109\frac{(4^{21}-1)/3}{841}\approx1.7\times10^9

    For d=20d=20 that is about 1.5×10121.5\times10^{12} tree nodes against 841 states. Graph search expands each state once, so its cost is polynomial in dd: 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, Θ(V)\Theta(V) 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

DerivationProof by frontier separation
  1. P: s→⋯→y→x→⋯→uP:\ s\to\cdots\to y\to x\to\cdots\to u

    Suppose, for contradiction, that uu is the first state popped with g(u)>g∗(u)g(u)>g^*(u). Take a cheapest path PP from ss to uu, and let xx be the first state on PP that has not yet been expanded. Since ss has been expanded, xx has a predecessor yy on PP:

  2. g(x)≤g∗(y)+c(y,x)=g∗(x)g(x)\le g^*(y)+c(y,x)=g^*(x)

    yy was popped before uu, so by the choice of uu it was expanded with g(y)=g∗(y)g(y)=g^*(y). Expanding yy put xx on the frontier with cost at most g∗(y)+c(y,x)g^*(y)+c(y,x), which equals g∗(x)g^*(x) because every prefix of a cheapest path is a cheapest path:

  3. g(x)≤g∗(x)≤g∗(u)<g(u)g(x)\le g^*(x)\le g^*(u)<g(u)

    Nonnegative costs make g∗g^* nondecreasing along PP, so xx precedes uu in the priority queue, contradicting that uu is popped now. (If x=ux=u, the bound gives g(u)=g∗(u)g(u)=g^*(u) directly.)

On an explicit graph, breadth-first graph search runs in O(V+E)\order{V+E} time. Dijkstra's algorithm takes O((V+E)log⁡V)\order{(V+E)\log V} with a binary heap and O(E+Vlog⁡V)\order{E+V\log V} 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 O(Elog⁡V)\order{E\log V} with at most EE heap entries and is usually faster in practice. The search widget and the Hidden Layer's pseudocode both work this way.

Check your understanding

Where does the proof of Dijkstra's invariant use the assumption that edge costs are nonnegative?

  1. To guarantee that the frontier never becomes empty
  2. To make the priority queue efficient
  3. To conclude g∗(x)≤g∗(u)g^*(x)\le g^*(u) for a state xx that comes before uu on a cheapest path
  4. To ensure that the graph is finite
Show the answer

C. To conclude g∗(x)≤g∗(u)g^*(x)\le g^*(u) for a state xx that comes before uu on a cheapest path

Along a cheapest path, g∗g^* can only grow when every edge costs at least 0. That places the frontier state xx ahead of uu in the queue and gives the contradiction. With one negative edge, uu 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 16!/2≈1.05×101316!/2\approx1.05\times10^{13} 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 kk lie at depths k−1k-1, kk or k+1k+1, so duplicates can be removed one layer at a time, in batches. Four ideas push past the limits of RAM:

TechniqueIdeaIntroduced by
Frontier searchKeep 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 detectionAppend generated nodes to disk unsorted, and remove duplicates in bulk, by sorting or hashing, once per layer.Korf (2003, 2008)
Structured duplicate detectionPartition 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 hashingStore a single bit per hash value. A collision can wrongly prune an unseen state, trading completeness for coverage.Holzmann, in the SPIN model checker
The first three keep the search exact; the last gives up completeness to cover more of a huge space.

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 f=g+hf=g+h rather than by gg, and graph search interacts with it. If hh is consistent, A* expands each state once, with its optimal gg, exactly like Dijkstra's algorithm on reduced costs. If hh 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, 2d2+2d+12d^2+2d+1 states instead of Θ(4d)\Theta(4^d) 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 O(V+E)\order{V+E} time and Dijkstra's algorithm O(E+Vlog⁡V)\order{E+V\log V} with Fibonacci heaps; lazy deletion, at O(Elog⁡V)\order{E\log V}, 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.

Question 1

On an open 4-connected grid, how does the number of states that breadth-first graph search expands before reaching a goal at distance dd grow?

  1. Θ(d)\Theta(d)
  2. Θ(d2)\Theta(d^2)
  3. Θ(3d)\Theta(3^d)
  4. Θ(4d)\Theta(4^d)
Show the answer

B. Θ(d2)\Theta(d^2)

It expands the states closer than the goal, up to 2d2+2d+12d^2+2d+1 of them. Tree-like search generates Θ(4d)\Theta(4^d) nodes, or Θ(3d)\Theta(3^d) with parent pruning.

Question 2

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?

  1. Skip the node if its gg exceeds the best cost recorded for its state
  2. Expand every copy, since each may lead somewhere new
  3. Nothing special: stale copies are never popped
  4. Restart the search from the cheaper copy
Show the answer

A. Skip the node if its gg 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 EE entries, for O(Elog⁡V)\order{E\log V} time in total.

Question 3

What does frontier search (Korf, Zhang, Thayer & Hohwald, 2005) avoid storing, and how does it still avoid regenerating expanded states?

  1. It stores no frontier, only the expanded states
  2. It writes every node to disk and never removes duplicates
  3. It stores only the start and the goal and recomputes everything else
  4. 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.

Question 4

Why can a chess engine afford to look up every position it reaches in a transposition table?

  1. Because positions never repeat in chess
  2. Because the table stores only checkmates
  3. Because Zobrist hashing updates a 64-bit key with a few XORs per move, so each lookup costs O(1)\order{1}
  4. 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 O(1)\order{1}

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).