IDA* is a heuristic search algorithm for shortest paths that combines the evaluation function of A* with the low memory footprint of depth-first search. It is widely used when the search space is too large to store A*’s frontier (OPEN list), e.g., in Rubik’s Cube optimal solving with Pattern Databases.[1][2]
A* prioritizes nodes by
where:
IDA* replaces A*’s best-first expansion with a series of depth-first searches bounded by an -threshold. It starts with
and repeats:
This preserves the A*-style ordering by , but avoids storing the full OPEN list.
In a bounded iteration with threshold , a node is pruned if
If the goal is found within the bound, the returned solution is the best achievable under that bound. With an admissible heuristic, the first solution found (when the bound reaches the optimal cost) is optimal.[1:2][3]
IDA*(start):
bound := h(start)
loop:
t := DFS-F(start, g=0, bound)
if t == FOUND: return solution
if t == +∞: return failure
bound := t
DFS-F(node, g, bound):
f := g + h(node)
if f > bound: return f
if node is goal: mark FOUND and return FOUND
min_excess := +∞
for each successor s of node:
t := DFS-F(s, g + cost(node,s), bound)
if t == FOUND: return FOUND
min_excess := min(min_excess, t)
return min_excess
If is admissible (), then the first solution returned by IDA* is optimal for the chosen cost metric.[1:3][3:1]
IDA* uses linear memory in the depth of the current DFS path (plus recursion/stack), unlike A* which can require exponential memory for the frontier.[1:4]
For Rubik’s Cube, IDA* becomes practical for optimal solving only when is strengthened using techniques such as Pattern Databases.[2:1]
| Feature | IDA* | A* |
|---|---|---|
| Memory Usage | Very Low () | High ( - stores all frontier nodes) |
| Optimality | Yes (with admissible ) | Yes (with admissible ) |
| Redundant Work | High (re-visits nodes in each iteration) | Low (ideally visits each node once) |
| Data Structure | Recursion Stack | Priority queue (OPEN list) |
Richard E. Korf. “Depth-first Iterative-deepening: An Optimal Admissible Tree Search.” Artificial Intelligence 27(1), 1985. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Richard E. Korf. “Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases.” AAAI, 1997. ↩︎ ↩︎
Peter E. Hart, Nils J. Nilsson, Bertram Raphael. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” IEEE Transactions on Systems Science and Cybernetics 4(2), 1968. ↩︎ ↩︎