Fast, small and optimal are separate requirements
The paper refuses to evaluate a search algorithm by expansions alone. It compares running time, stored states and the cost of the solution path, because a procedure can excel on one axis by failing another.
Korf adopts the problem-space model of Newell and Simon. States form a space; operators are partial functions from states to states; a problem supplies an initial state and a set of goals. A solution is an operator sequence carrying the initial state to a goal.
Two parameters describe the basic tree model. The node branching factor b is the average number of new states produced at an expansion. The solution depth d is the length of a shortest operator sequence to a goal. Time is counted as states expanded and space as states stored, assuming constant work and storage per state for asymptotic analysis.
The paper focuses on optimal solutions while acknowledging that many applications cannot afford or do not require them. Optimal exemplars can still assess approximate solutions. The governing claim is therefore conditional: when a shortest or cheapest path is required in an exponentially growing tree, how much time and memory are unavoidable?
The tree restriction matters. In a graph, several operator sequences may reach the same state. A search that does not detect duplicates can explore exponentially many paths through only linearly many distinct nodes. Node and edge branching then separate, and the clean tree-optimality result does not transfer automatically.
Worked example 1 · one algorithm, three scores
A method finds a length-12 path after one million expansions while storing 500 states. Another finds length 10 after 700,000 expansions but stores 400,000 states. “Better” depends on whether shortest length, time or memory is binding; the metrics must remain visible.
Causal probe 1 · hide the solution cost
A depth-first procedure may appear efficient because it quickly reaches some goal. Without comparing that path to the shortest one, speed has been purchased by silently changing the objective.
The shallowest guarantee builds an exponential warehouse
Breadth-first search expands every state one step from the start, then every state two steps away, and so on. Its level order gives a shortest-length solution in an unweighted tree.
In the worst case it generates all nodes through depth d: b+b²+…+bᵈ, which is O(bᵈ). If a goal is placed randomly on the last level, roughly half that level is inspected on average, leaving the same asymptotic time.
The critical drawback is storage. To generate depth d, breadth-first must retain the depth d−1 frontier, containing b^(d−1) nodes in the uniform model. Peak memory is O(bᵈ), the same exponential order as time. A machine can exhaust memory while its processor is capable of much more search.
Korf's 1985 illustration compares about a million words of memory with about a million instructions per second. If generating a state takes roughly a minute per million and each stored state takes one word, the frontier can fill memory in about a minute. Exact hardware ratios age; the frontier geometry does not.
The shortest-path guarantee also depends on unit operator costs. If steps have different costs, fewest edges need not be cheapest. The later IDA* section replaces depth by a total-cost estimate precisely to handle cost-sensitive optimality.
Worked example 2 · branching four, depth five
The last level contains 4⁵=1,024 nodes. The whole tree through depth five contains 1+4+16+64+256+1,024=1,365. Breadth-first may need a queue on the scale of the entire last frontier even though a returned path contains only six states.
Causal probe 2 · delete parents as soon as children appear
Frontier storage still grows exponentially because the children themselves must wait for level-order expansion. Parent-pointer compression can reduce bytes per node but does not change the count of pending states.
A small stack can wander through an enormous path tree
Depth-first search stores the current route and enough sibling information to backtrack. With cutoff d, its space is O(d), but the saved memory does not guarantee saved time or a shortest answer.
Korf distinguishes node branching b from edge branching e. In a tree each operator reaches a new state, so b=e. In a graph, multiple paths may converge on the same state: the number of applicable edges can exceed the number of new nodes.
A depth-first search without duplicate detection explores paths, not merely distinct states. Korf's Figure 1 has only linearly many nodes at increasing levels but two choices at each step that rejoin. Breadth-first handles its unique frontier linearly; depth-first can enumerate exponentially many operator sequences. Its general time bound to depth d is O(eᵈ).
Depth-first also needs a cutoff on infinite or cyclic expansions. Set it below the nearest goal and the search falsely returns failure. Set it much deeper and the first branch can contain exponentially more work than the optimal depth required. A goal encountered first may be longer than a shallower goal elsewhere.
This exposes why “uses little memory” is not a full evaluation. Depth-first is often time-bound rather than space-bound because its stack grows only logarithmically relative to its path enumeration. Its arbitrary cutoff imports an unverified prediction about solution depth into both completeness and quality.
Worked example 3 · two edges, one new state
At every level, operators L and R lead to the same next state. The graph contains one new state per depth, so b=1, but a duplicate-blind depth-first traversal sees 2ᵈ distinct paths, so e=2 controls its work.
Causal probe 3 · choose a generous cutoff
A cutoff of 50 does not merely include a goal at depth 10. Depth-first may traverse huge subtrees down to 50 before reaching the shallow branch. Overestimation can be exponentially costly and can return a non-shortest goal.
Restart at limits one, two, three, until the goal appears
DFID performs a depth-limited depth-first search at limit one, discards it, restarts at two, and continues. It deliberately repeats work to recover breadth-first order without breadth-first storage.
Because no iteration reaches below its limit, the first successful limit is the shallowest goal depth. Within an iteration the search is depth-first, so only a stack to the current node is required. Solution length matches breadth-first and peak storage matches depth-first: O(d).
The apparent cost is repeated upper levels. A root is visited on every iteration; depth-one nodes are revisited on all but the first, and so on. Yet an exponential tree contains far more nodes at depth d than in all early levels. The cheap part is repeated; the expensive frontier appears only in the final traversal.
Korf defines a brute-force search as using only the initial state, the operators and a goal test. Theorem 4.2 states that DFID is asymptotically optimal among brute-force tree searches in time, space and solution length. The theorem does not claim instance-by-instance minimum expansions, nor does it cover algorithms supplied with informative heuristics.
The adversary lower bound for time is direct. A depth-d tree contains bᵈ possible frontier nodes. If a purported general brute-force algorithm leaves one unexamined, an adversary can place the only goal there. Any complete algorithm therefore needs Ω(bᵈ) time in the worst case, matching DFID's order.
Worked example 4 · who repeats how often
With final depth five, depth-five nodes appear once, depth-four nodes twice, depth-three nodes three times, and the root six times if a zero limit is included. The repetition weight falls exactly where node population rises.
Causal probe 4 · retain every prior frontier
The search remains complete, but memory returns towards breadth-first scale. DFID's exchange depends on discarding earlier traversals and recomputing their cheap prefixes.
The overhead is a constant when branching exceeds one
A node at depth d is generated once, one at d−1 twice, one at d−2 three times. The resulting weighted geometric series has the same asymptotic order as the final level.
For a uniform tree the total is proportional to bᵈ+2b^(d−1)+3b^(d−2)+…. Factor out bᵈ and write x=1/b. The remaining series 1+2x+3x²+… converges to (1−x)⁻² for |x|<1. Its value depends on b, not d.
Therefore DFID runs in O(bᵈ) time for b>1. Repeating every shallow level does not add another factor of d to the asymptotic order. The constant approaches one as branching rises; at low branching near one it grows, matching the intuition that a thin tree has no massive final layer to amortise restarts.
Space optimality is also asymptotic. DFID stores O(d) states. Korf invokes the information requirement that an algorithm taking f(n) time needs at least logarithmic storage to traverse that many distinguishable states without looping or terminating. Since log(bᵈ)=d log b, the linear-depth stack has optimal order for fixed b.
The proof is a model, not a waiver for all overhead. Generating a state may have non-constant cost, transpositions may dominate, and a branching factor can vary by level. But it exposes the governing phenomenon: when work expands geometrically, recomputation of earlier contours is a bounded premium for saving an exponential frontier.
Worked example 5 · branching ten
The asymptotic coefficient (1−1/10)⁻² is about 1.235. Repeated contours add at most a modest fraction over the dominant last level in the uniform full-depth calculation.
Causal probe 5 · let b approach one
The coefficient grows without bound. On a nearly linear search space, upper levels are no longer negligible relative to the frontier, so iterative restart can carry a large constant penalty even though the big-O expression remains.
Meet in the middle when a goal and inverse operators are available
For a single explicit goal and reversible operators, two searches can reduce time by splitting the solution depth. Korf shows how iterative deepening limits the required stored middle frontier.
A conventional bidirectional search grows from start and goal until the frontiers meet, using hashing for constant-time matches. Each direction reaches roughly d/2, so time and space scale near b^(d/2), an exponential improvement over bᵈ but still a substantial memory requirement.
The iterative variant chooses k. It performs a depth-first search from one direction to depth k and stores only the states exactly at that depth. From the other direction it performs depth-first searches to depths k and k+1, matching encountered states against the stored boundary. The second depth covers odd-length solutions.
Repeat k from zero through d/2. Under the model and constant-time hashed matching, optimal solution length is preserved, time remains O(bᵈ) as stated in the paper's notation for the full search progression, while peak stored frontier is O(b^(d/2)). The method explicitly trades more recomputation for the half-depth boundary.
Korf reports use on Rubik's Cube, whose effective branching factor was about 13.5, finding solutions up to eleven moves on a DEC VAX 11/780. This is an application report under a particular representation, not a universal complexity measurement for all reversible state spaces.
Worked example 6 · why k+1 is required
If the optimal path has length seven and the stored forward boundary is depth three, a reverse search only to depth three covers six edges. Extending the reverse pass to four permits a match across the odd seventh step.
Causal probe 6 · use an implicit goal test only
Backward generation requires a concrete goal state and inverse operators. If “goal” is merely a predicate over many unknown states, the reverse frontier may not be constructible without enumerating the goal set.
Let f-cost, not depth, define the contour
IDA* combines iterative deepening with A*. Each pass is depth-first but cuts when f(n)=g(n)+h(n) exceeds a threshold.
The initial threshold is the heuristic estimate at the start. During a pass, every exceeded f-value is observed. If no goal is found, the next threshold becomes the smallest value that exceeded the current one. This avoids searching a cost interval containing no nodes and replaces the unit depth schedule with the actual contours of the evaluation function.
An admissible heuristic never overestimates remaining goal cost. Under a monotone or consistent f-function, f never decreases along a path. IDA* therefore expands all nodes on one cost contour before any higher contour, so the first solution is cheapest.
Korf notes that monotonicity is convenient rather than essential. Lemma 6.2 constructs a pathmax correction f′: at each child take the maximum of its original f and its parent's corrected f′. The result is monotone, remains admissible along the current tree path, and is at least as informed as the original value.
Lemma 6.3 gives optimal solution cost. Theorem 6.4 adds asymptotic time and space optimality among admissible best-first tree searches when the admissible monotone heuristic has constant relative error. The final IDA* pass expands the same relevant contour as a particular A* tie rule; earlier contours are lower-order under exponential growth. The premise and tree scope belong to the claim.
Worked example 7 · skip empty thresholds
A pass at threshold 12 observes exceeded values 14,17 and20. The next threshold is 14, not 13. No node has f=13, so a pass there could expand nothing new.
Causal probe 7 · increment fractional costs by one
With arbitrary real edge and heuristic costs, fixed unit increments may skip the optimal contour or add useless iterations. The minimum-exceeded rule follows the values actually present.
Memory, not expansions, stopped A*
Korf implements IDA* and A* in Pascal on a DEC 2060 using Manhattan distance, then tests 100 random solvable Fifteen Puzzle states.
For each movable tile, Manhattan distance counts horizontal and vertical grid steps from its current square to its goal square; summing gives an admissible lower bound because every tile must travel at least that far, while interactions can add further moves.
IDA* solved all 100 instances. The reported median was 30 CPU minutes at more than 1.5 million generated nodes per minute. Average optimal solution length was 53 moves and the maximum 66. The paper prints each state, initial estimate, actual length and total generated nodes.
A* solved none of these random instances because it exhausted space after storing about 30,000 nodes. IDA* could generate more nodes yet run faster because it avoided open/closed-list overhead. This is precisely why expansions, elapsed time and peak memory must not be collapsed into one performance claim.
The puzzle state space is a graph rather than a strict tree. Korf argues iterative deepening remains effective because the edge branching factor is only slightly larger than the node branching factor. The qualification matters: the earlier converging-path counterexample shows graphs can make duplicate-blind depth-first enumeration pathological.
Worked example 8 · an admissible tile estimate
A tile three columns and one row from its target needs at least four moves of that tile. Summing such lower bounds does not account for tiles blocking one another, so it can underestimate but does not overestimate the remaining puzzle moves.
Causal probe 8 · compare only generated nodes
A* may generate fewer nodes yet fail by memory, while IDA* completes with more generations and lower per-node overhead. Counting a single resource would reverse the practical conclusion.
A completed shallow search becomes insurance and ordering
Game search reverses the optimisation framing. Given fixed time and memory, the aim is to reach the greatest completed depth because static evaluation is assumed to improve with lookahead.
If DFID minimises time and space asymptotically for a specified depth, then under the model it maximises attainable depth for fixed resources. More practically, the time for the next ply is uncertain. If the clock interrupts it, the complete result from the previous shallower iteration remains available for choosing a move.
Earlier iterations also improve successor order for alpha-beta pruning. The best move at one depth often remains best when the horizon grows. Korf reports an observation that the previous best move terminated the next iteration in about 70 per cent of cases. Trying it first can establish useful bounds early and increase cutoffs.
Repeated search is therefore not pure waste even before asymptotics. It produces a fallback answer and information that reorganises the next pass. The shallower result has two roles: operational insurance and a proposal for move order. Alpha-beta still verifies the deeper minimax result.
This link follows Canon 0076 directly. Knuth and Moore showed that ordering controls the size of an alpha-beta certificate. Korf explains how iterative deepening supplies ordering information under a real-time budget while retaining the last finished decision.
Worked example 9 · the clock expires mid-ply
A chess program completes depth six and begins seven. If time expires halfway through seven, it returns the depth-six move rather than a value based on an uneven partial tree. The aborted iteration still may inform future ordering, but it is not reported as complete.
Causal probe 9 · overwrite the last complete move immediately
If a provisional result from an incomplete deeper iteration replaces the finished shallower decision, the anytime guarantee disappears. Frontier imbalance can make that provisional choice incomparable.
The result is powerful because its boundaries are named
DFID is asymptotically optimal for brute-force exponential tree search. IDA* adds heuristic premises. Graphs, low branching and implementation costs can change the practical balance.
Big-O equivalence hides constants and stopping position on the last contour. A goal visited early can make breadth-first's final pass much shorter than the full-level formula, while DFID has already paid for prior limits. Conversely, a larger branching factor makes restarts proportionally cheaper.
The edge/node distinction guards against graph misuse. Duplicate detection can improve time but consumes memory. Transposition tables, cycle checks and problem-specific abstractions create intermediate designs. Korf's paper evaluates a tree-search architecture; a modern graph solver must state how repeated states are controlled.
IDA* also inherits heuristic quality and cost. An admissible estimate may generate many closely spaced thresholds; inconsistent values need pathmax or a more careful proof; non-unit actions require cost contours. Theorem 6.4 explicitly invokes monotonicity, constant relative error, exponential growth and admissible best-first tree-search comparators.
Finally, optimal path cost is a property of the supplied state graph and objective. If operators omit relevant actions or costs omit relevant consequences, the cheapest formal path may be a poor real decision. Search guarantees do not validate the model they search.
Worked example 10 · a tree claim applied to a graph
A puzzle lets two move sequences return to the same board. Plain IDA* may revisit that board on separate paths. The algorithm can remain useful, as the Fifteen Puzzle experiment shows, but the proof's one-expansion-per-tree-node sentence no longer holds literally.
Causal probe 10 · advertise “optimal in all three dimensions” without qualifiers
Remove “asymptotically”, “tree”, “brute-force” or the heuristic premises and the sentence becomes false or undefined. A theorem's scope is part of its result, not small print.
Evidence boundary
Iterative deepening manages computational resources for a supplied goal. It does not choose the goal, evaluate its moral worth, or establish that a machine experiences urgency when a time limit approaches.
Place one goal among 1,024 leaves
Five controls select the four-way branch at each depth of a uniform depth-five tree. Across all 4⁵=1,024 possible goal addresses, the laboratory compares breadth-first, cutoff-five depth-first and DFID, including generated nodes, peak stored states and repetitions by level.
Running shortest-depth audit…
Running memory-bound audit…
Running repetition-accounting audit…
Worked example 11 · move the goal from first to last
Set every digit to zero, then every digit to three. The solution depth and peak DFID stack remain five and six states respectively. Work changes because the final traversal reaches the target early or late within the same contour.
Causal probe 11 · compare only the final iteration
The final DFID pass resembles cutoff-depth DFS, but the complete algorithm also paid the earlier limits that establish no shallower goal exists. The ledger keeps those proof costs visible.
Claims, premises and audit handles
| Claim | Premise | Audit handle |
|---|---|---|
| Breadth-first returns a shallowest goal. | Unit step cost and complete level order. | Check every depth below the returned goal was exhausted. |
| Depth-first uses O(d) memory. | Store the current path and bounded sibling state, not all generated nodes. | Record maximum stack length. |
| DFID returns a shallowest goal with O(d) space. | Limits increase without gaps and every bounded pass is complete. | Audit all limits before the successful one and the peak stack. |
| DFID time is O(bᵈ). | Exponential tree with b>1 and constant per-state work. | Sum weighted levels and factor the convergent geometric series. |
| IDA* returns a cheapest path. | Admissible heuristic, correct cost contours and minimum-exceeded threshold updates. | Compare with a uniform-cost oracle. |
| IDA* is asymptotically time/space optimal in Theorem 6.4's sense. | Tree search, monotone admissible heuristic, constant relative error and exponential growth. | Keep comparator class and tie handling explicit. |
Fidelity, teaching and implementation review
Review one: scholarship. The reconstruction retains the three-axis comparison, Newell-Simon problem space, node and edge branching distinction, BFS time/space, DFS stack and cutoff hazards, brute-force definition, Theorem 4.2's adversary and storage arguments, weighted geometric series and coefficient, bidirectional construction including the k+1 pass, IDA* minimum-exceeded schedule, monotonicity, pathmax, Lemma 6.3, Theorem 6.4's constant-relative-error premise, Fifteen Puzzle sample of 100, and two-person-game uses.
Review two: teaching and execution. Ten paper-specific SVGs have unique titles, descriptions, captions and source scopes; motion disappears under reduced-motion preference. Twelve worked examples and twelve causal probes target every load-bearing boundary. The laboratory exhaustively searches 1,024 goal placements and independently checks first-goal depth, stack bounds and exact generation accounting.
Evidence and AI-telltale review. “Optimal” is never detached from asymptotic order, trees, brute force or heuristic premises. The 1985 hardware and puzzle measurements retain their sample size and platform context. Repetition is explained by a geometric sum, not personified as patience or intuition.
Accessibility and implementation review. Colour is redundant with labels and shapes; control labels name depth and branch; result changes are announced; tables scroll on mobile; all grids collapse at the declared breakpoints. The oracle routines for BFS, DFS and DFID are separate, and the audit traverses every five-digit goal address rather than sampling convenient cases.
Twelve cards for rebuilding iterative deepening
Recomputation is a rational storage policy
Computer science often teaches repeated work as waste. Korf identifies a regime where preserving every result is the larger waste. An exponential frontier is expensive to remember; its prefixes are cheap to regenerate. DFID chooses forgetting because the geometry makes memory more valuable than shallow computation.
The iteration limit is also a certificate boundary. Completing limit four proves there is no goal at depth four or less. The pass at five can therefore return its first goal with a shortest-depth guarantee. Repetition is not merely an implementation trick; it reconstructs the evidence that breadth-first stores in its frontier.
IDA* makes the boundary epistemic. A heuristic says which total costs remain plausible, but admissibility restrains its authority. Each failed contour records the smallest excluded f-value, and that exact witness sets the next investigation. The algorithm progresses through justified cost thresholds rather than arbitrary increments.
In games, earlier computation has option value. A completed shallower move protects against interruption, while its principal move predicts useful ordering for the next alpha-beta search. The work is repeated syntactically but transformed operationally: it buys both a fallback and information about where verification should begin.
Worked example 12 · discard a million nodes, keep six
A completed contour may generate a million states yet leave only the current path and the next threshold. If regenerating the shallow portion is cheap relative to storing the frontier, deliberate loss preserves the capacity to reach a much deeper solution.
Causal probe 12 · make generation enormously expensive
If every regenerated prefix requires a costly external experiment, the constant-factor time premium may dominate and caching becomes rational. DFID's exchange assumes state expansion cost is sufficiently uniform and repeatable.
Boundary statement
Iterative deepening is evidence of resource-aware algorithm design, not of phenomenal memory, frustration at repetition or conscious foresight. Those metaphors add no proof.
From propagated constraints to bounded recomputation
Canon 0077 made a constraint network carry local consequences forward so search would not rediscover the same unsupported values. Canon 0078 appears to move in the opposite direction: it discards whole earlier traversals and regenerates them. The tension is resolved by cost. Mackworth preserves compact general reasons; Korf declines to preserve an exponential mass of individual frontier states.
Canon 0075 supplied A*'s admissible frontier ordering, and Canon 0076 supplied alpha-beta's bound-based omissions. Korf connects both: IDA* obtains A*-like cost order without open-list memory, while game iterative deepening uses prior principal moves to improve alpha-beta ordering.
Canon 0079 turns from systematic contours to repair: Steven Minton and colleagues' “Minimizing Conflicts” (1992) starts with a complete but inconsistent assignment and repeatedly changes a variable to reduce violated constraints.
What this companion adds
This companion follows all eight sections of Korf's 13-page paper. It separates node from edge branching, reconstructs the breadth-first and depth-first failure modes, walks the weighted geometric proof and adversary lower bound, and keeps the tree restriction attached to the result.
Bidirectional iterative deepening, IDA* threshold selection, pathmax, constant relative error, the 100-instance Fifteen Puzzle experiment and the game-search fallback/order benefits receive independent treatment. Later shorthand such as “linear memory” is tied to the current path representation rather than presented as zero storage.
Ten animated SVGs, twelve examples, twelve probes, twelve memory cards and a claim ledger make the resource exchange auditable. The executable laboratory enumerates every one of 1,024 possible depth-five goal locations in a four-way tree, checking the shortest-depth answer, queue and stack peaks, and exact repeated-node accounting.
Primary and contextual sources
- Richard E. Korf, “Depth-First Iterative-Deepening: An Optimal Admissible Tree Search”, Artificial Intelligence 27(1), 97–109 (1985). Publisher DOI.
- Peter E. Hart, Nils J. Nilsson and Bertram Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics 4(2), 100–107 (1968).
- Rina Dechter and Judea Pearl, “The Optimality of A* Revisited”, Proceedings of the National Conference on Artificial Intelligence, 95–99 (1983).
- Judea Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley (1984).
- Ira Pohl, “Bi-directional Search”, in Machine Intelligence 6, 127–140 (1971).
- David J. Slate and Lawrence R. Atkin, “CHESS 4.5 — The Northwestern University Chess Program”, in Chess Skill in Man and Machine (1977).