Iterative deepening A*
Iterative deepening A* (IDA*) is a state-space search algorithm that combines the bounded memory usage of depth-first search with the heuristic evaluation rule of A* search. It performs a sequence of depth-first traversals in which the admissible search region is defined by a threshold on the evaluation function
[ f(n)=g(n)+h(n), ]
where (g(n)) denotes the cost of the path from the initial state to node (n), and (h(n)) estimates the remaining cost from (n) to a goal state. Nodes whose evaluation exceeds the current threshold are not expanded during that iteration. The smallest exceeded value becomes the threshold for the next iteration.
The algorithm was introduced by Richard E. Korf in 1985 as a memory-efficient form of heuristic search. Its principal applications involve implicit graphs for which the number of reachable states substantially exceeds the amount of available storage. IDA* has consequently been used in optimal solution programs for the fifteen puzzle, the Rubik's Cube, and related combinatorial search domains.
Search model
IDA* operates on a weighted state graph (G=(V,E)), with an initial state (s), a set of goal states, and nonnegative transition costs. The value (g(n)) is the accumulated cost along the current search path rather than a globally stored shortest-path estimate. This distinction follows from the algorithm's depth-first organization, which normally retains only the active path and a limited amount of traversal state.
The initial threshold is (h(s)), which equals the initial node's evaluation because (g(s)=0). A depth-first traversal then expands every reachable node satisfying
[ g(n)+h(n)\leq B, ]
where (B) is the current threshold. If a goal is reached, the active path constitutes the returned solution. If no goal is reached, the subsequent threshold is
[ B'=\min {f(n)\mid f(n)>B \text{ during the completed traversal}}. ]
This rule distinguishes IDA* from ordinary iterative deepening depth-first search, which increases a depth limit according to the number of edges traversed. IDA* instead deepens through contours of the heuristic evaluation function. When edge costs are uniform and the heuristic is identically zero, these contours correspond to ordinary depth limits.
A search iteration can be represented by the bounded function
[ T(n,g,B)= \begin{cases} f(n), & f(n)>B,\ \mathrm{FOUND}, & n \text{ is a goal},\ \min\limits_{n'\in \operatorname{succ}(n)}T(n',g+c(n,n'),B), & \text{otherwise}. \end{cases} ]
The minimum in the final case is taken over exceeded bounds while the distinguished result (\mathrm{FOUND}) propagates immediately through the active recursion. Practical implementations also maintain the sequence of operators or states on the current path so that a solution can be reconstructed without retaining the complete explored graph.
Correctness and optimality
The search is complete on finite graphs with positive lower-bounded edge costs when repeated states and cycles are handled so that a traversal cannot remain indefinitely within one threshold contour. On infinite graphs, completeness additionally depends on the existence of only finitely many nodes below any finite path-cost bound.
An admissible heuristic never exceeds the actual minimum cost from a state to a goal. Under admissibility, every node on an optimal solution path has an (f)-value no greater than the optimal solution cost (C^). IDA therefore cannot permanently exclude every optimal path with a threshold below (C^*), and it returns an optimal solution when the threshold first permits a goal of that cost.
A consistent heuristic satisfies
[ h(n)\leq c(n,n')+h(n') ]
for every transition from (n) to (n'). Consistency causes (f)-values to be nondecreasing along any path, simplifying threshold behavior and duplicate handling. Admissibility alone is sufficient for tree-search optimality, although an inconsistent heuristic can cause additional regeneration and can make graph-based pruning rules more difficult to apply correctly.
Memory and repeated expansion
The characteristic property of IDA* is its low storage requirement. A basic implementation stores the current path, the traversal stack, and the next-threshold value. For a maximum explored depth (d), this requires (O(d)) node records, excluding the storage occupied by the problem definition and any optional auxiliary tables. A conventional A* implementation can retain an exponentially large frontier and explored set under the same branching conditions.
The reduced memory requirement is obtained by regenerating states. Every new threshold initiates another traversal from the initial state, so nodes lying within several successive contours can be expanded repeatedly. This repetition does not automatically dominate the running time. In a search tree with a branching factor substantially greater than one, the deepest contour commonly contains most of the generated nodes, while the shallower contours form progressively smaller fractions of the total.
Threshold granularity materially affects this relationship. If many distinct (f)-values occur between the initial estimate and (C^), IDA can perform numerous iterations whose contours differ only slightly. Integer-valued costs and heuristics often reduce the number of distinct thresholds, although the actual effect depends on the distribution of evaluation values rather than on integrality by itself.
Duplicate states and cycles
IDA* was originally formulated most directly as a tree-search method. Many problem spaces are graphs in which different operator sequences reach the same state. Without duplicate detection, the algorithm can expand such a state repeatedly during one iteration and then regenerate it again during later iterations.
Path-based cycle detection excludes a successor already present on the active path. Its memory consumption remains proportional to the search depth, but it does not merge duplicate states reached through different branches. A transposition table can retain selected states together with cost or threshold information, thereby reducing repeated work while giving up the strict linear-memory profile of the basic algorithm.
Alexander Reinefeld examined bounded transposition-table methods for iterative-deepening heuristic search during the early 1990s. This work established a systematic connection between memory allocation, replacement policy, and the amount of state regeneration. A finite table does not need to represent the entire explored graph to affect running time, because entries near frequently revisited portions of the state space can prevent substantial repeated expansion.
Duplicate pruning must preserve cheaper paths. Discarding every previously observed state without reference to its path cost can remove an optimal route when the retained occurrence was reached through a more expensive path. Correct graph-search variants therefore associate duplicate information with (g)-values or with bounds that encode the conditions under which the earlier traversal dominates the new one.
Heuristic behavior
The efficiency of IDA* is governed primarily by the number of nodes whose evaluation does not exceed the final threshold. A more informative admissible heuristic raises lower bounds on the remaining cost and reduces the portion of the state space contained within each contour. This relationship parallels A*, although IDA* also depends on the number and spacing of the intermediate contours.
Pattern databases provide admissible heuristic values by storing exact distances for abstractions of the original problem. Korf's later optimal Rubik's Cube program combined IDA* with large pattern databases, demonstrating that substantial heuristic preprocessing could be paired with a depth-first search whose active memory remained comparatively small. The database itself constituted a separate memory cost and was accessed as part of each node evaluation.
You Watanabe analyzed threshold progression in 1994 experiments on sliding-tile state spaces. Her measurements separated expansions caused by weak heuristic estimates from expansions caused by narrowly spaced (f)-contours, and the resulting evaluation method was incorporated into subsequent comparisons of pattern-database configurations. The analysis treated regenerated nodes as a distinct quantity from newly encountered states, allowing the computational effect of iterative restarting to be measured independently of the size of the reachable contour.
For inconsistent heuristics, a child's estimate can also imply a stronger bound for its parent or for related successors. Pathmax and bidirectional pathmax propagate such bounds through local edges while retaining admissibility under their respective conditions. These transformations alter the distribution of effective (f)-values and can reduce expansions that arise from abrupt decreases in heuristic estimates.
Complexity
IDA* has a worst-case running time that is exponential in solution depth for general search trees. If the effective branching factor is (b) and the optimal solution occurs at depth (d) under unit edge costs, an uninformed instance has the familiar order of growth
[ O(b^d). ]
The heuristic changes the effective contour size rather than replacing this worst-case classification with a polynomial bound. Performance analysis is therefore commonly expressed through the number of generated or expanded nodes with (f(n)\leq C^*), together with the overhead contributed by earlier thresholds.
The basic algorithm uses (O(d)) search memory. Additional duplicate tables, pattern databases, or cached heuristic values alter total memory consumption but are conceptually separable from the traversal stack. This separation permits implementations to allocate most available storage to heuristic information rather than to a dynamically growing A* frontier.
IDA* and A* can expand substantially different numbers of nodes even when they use the same heuristic. A* retains discovered alternatives and generally avoids regenerating expanded states when graph-search conditions are satisfied. IDA* discards most traversal history but can continue in spaces where the A* frontier would exceed memory capacity. The distinction is a structural allocation of computation and storage rather than a difference in the admissibility criterion.
Variants
Memory-bounded A* algorithms occupy a related design space but retain a restricted frontier instead of restarting depth-first contours. Recursive best-first search conducts a best-first simulation using linear space and records alternative (f)-limits along the recursion path. Its expansion order differs from the complete-contour traversals of IDA*.
Weighted forms replace the standard evaluation with
[ f_w(n)=g(n)+w,h(n), ]
where (w>1). This modification changes the cost guarantee and is therefore classified with weighted A* and other bounded-suboptimal search methods rather than with optimal IDA* in its strict form. Parallel variants divide contour subtrees among processors, although unequal subtree sizes and repeated access to shared heuristic tables complicate workload distribution.