Iterative Deepening A* (IDA*) combines A*'s heuristic guidance with iterative deepening's memory efficiency. Repeated depth-first search with increasing -value cutoffs.
Algorithm
``` function IDA_star(initial, goal, h): threshold = h(initial) while True: result, new_threshold = dfs_contour(initial, goal, 0, threshold, h) if result is found: return result if new_threshold == infinity: return failure threshold = new_threshold
function dfs_contour(state, goal, g, threshold, h): f = g + h(state) if f > threshold: return cutoff, f if state is goal: return found min_next = infinity for action in actions(state): next = transition(state, action) result, t = dfs_contour(next, goal, g + step_cost, threshold, h) if result is found: return found min_next = min(min_next, t) return cutoff, min_next ```
Properties
- Complete: yes.
- Optimal: yes with admissible heuristic.
- Time: same as A* in the worst case, often comparable in practice.
- Space: — DFS stack only.
Trade-offs vs A*
- Memory: huge advantage. A* runs out on problems IDA* handles fine.
- Visited tracking: IDA* doesn't keep a closed set. In graphs with many duplicate paths to the same state (lots of cycles or many alternative routes), it re-explores them — repeated work that A* avoids.
- Cache friendliness: DFS exploration is much more cache-friendly than A*'s frontier scan.
Where IDA* shines
- 15-puzzle and similar small-fanout puzzles with good heuristics.
- Planning problems where the state space is huge but the solution depth is moderate.
- Embedded systems with tight memory budgets.
Where it doesn't: graphs with many duplicate states reachable through different paths. A* with a closed set is much better there.
Memory-bounded alternatives
- MA*: bounded memory; drops least-promising fringe nodes when full.
- SMA*: same idea, polished.
- RBFS (Recursive Best-First Search): depth-first with memory but tracks the best alternative -value seen on the side, switching when it becomes the new best.