Course contentsShow
← Computer Science
Lesson 2761 of 2,87261. AI and Search AlgorithmsFree lesson

IDA* (Iterative Deepening A*)

Learn memory-efficient iterative deepening combined with A*'s heuristic guidance.

IDA* (Iterative Deepening A*)

What You'll Learn

You'll discover how to combine the memory efficiency of iterative deepening with A*'s powerful heuristic guidance to search large spaces without exhausting memory.

The Core Idea

IDA* (Iterative Deepening A*) merges two concepts you already know: Iterative Deepening DFS and A Search*. Instead of storing all frontier nodes in memory like A* does, IDA* performs depth-first search repeatedly with increasing cost thresholds.

Here's how it works:

  1. Start with a threshold equal to the heuristic value of the start state: f(start) = g(start) + h(start)
  2. Perform depth-first search, but prune any path where f(n) = g(n) + h(n) exceeds the current threshold
  3. Track the minimum f-value that exceeded the threshold during the search
  4. If no goal found, repeat with the new threshold set to that minimum value
  5. Terminate when a goal is reached

Think of it like climbing a mountain in the fog with an altimeter. Each iteration, you explore as far as your altitude budget allows. When you hit your limit everywhere, you raise the budget to the next sensible level and try again—always guided by your heuristic "compass" toward the goal.

Benefits and Trade-offs

Memory: IDA* uses O(bd) space (just the current path), dramatically less than A*'s O(b^d) frontier.

Time: IDA* may re-explore states, but with a good heuristic, overhead is often manageable—especially when memory limits would otherwise prevent A* from running at all.

Best for: Problems where memory is the bottleneck and the branching factor or heuristic makes the re-exploration cost acceptable.

Key Takeaway:
IDA trades some computational overhead for massive memory savings by iteratively deepening depth-first search using A's f-cost as the cutoff threshold, making it ideal when memory constraints prohibit standard A*.**