IDA* (Iterative Deepening A*)

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]

Core idea

A* prioritizes nodes by

f(n) = g(n) + h(n),

where:

• g(n) is the cost from start to n,
• h(n) is a heuristic estimate from n to the goal.

IDA* replaces A*’s best-first expansion with a series of depth-first searches bounded by an f-threshold. It starts with

B_0 = f(\text{start}),

and repeats:

• run a DFS that only expands nodes with f(n) \le B,
• if no solution is found, increase B to the smallest f that exceeded the bound during the previous iteration.^[1:1]

This preserves the A*-style ordering by f, but avoids storing the full OPEN list.

Bounded DFS rule

In a bounded iteration with threshold B, a node n is pruned if

g(n) + h(n) > B.

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]

Minimal pseudocode

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

Guarantees

Optimality

If h is admissible (0 \le h(n) \le h^*(n)), then the first solution returned by IDA* is optimal for the chosen cost metric.^[1:3][3:1]

Memory

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]

Practical profile

• Strengths: very low memory; simple to implement; strong performance when paired with powerful heuristics.
• Weaknesses: repeated iterations can revisit many nodes; runtime can still be very large without strong heuristics.

For Rubik’s Cube, IDA* becomes practical for optimal solving only when h is strengthened using techniques such as Pattern Databases.^[2:1]

Comparison: IDA* vs. A*

References