What is the point of IDA vs A algorithm
Master System Design with Codemia
Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.
Introduction
A* (A-star) and IDA* (Iterative Deepening A-star) are two important informed search algorithms for finding least-cost paths in graphs. Both use the evaluation function to guide their search, but they differ fundamentally in how they manage memory. A* stores all explored and frontier nodes in memory, while IDA* uses iterative deepening to achieve the same optimal results with dramatically less memory. This article explains when and why to choose IDA* over A*.
How A* Works
A* is a best-first search algorithm that maintains two data structures:
- Open list (priority queue): nodes discovered but not yet expanded, ordered by
- Closed list (hash set): nodes already expanded, to avoid revisiting
At each step, A* extracts the node with the lowest value from the open list, expands it (generating its successors), and adds the successors to the open list. The evaluation function is:
- : actual cost from the start node to node
- : heuristic estimate of the cost from to the goal
- : estimated total cost of the cheapest path through
A* is guaranteed to find the optimal solution when the heuristic is admissible (never overestimates the true cost) and consistent (satisfies the triangle inequality).
A* Memory Problem
A* stores every generated node. For a branching factor and solution depth , the number of nodes stored can grow as . In practice, this means A* can exhaust available memory long before it exhausts available time. For example, with and , A* may store up to million nodes.
How IDA* Works
IDA* combines the optimality guarantee of A* with the memory efficiency of depth-first search. It works in iterations:
- Set initial threshold to .
- Perform depth-first search, but prune any node where exceeds the current threshold.
- If goal is not found, set the new threshold to the smallest value that exceeded the previous threshold.
- Repeat until the goal is found.
Memory Usage
IDA* only stores the current path from root to the node being explored. This requires memory, where is the solution depth. Compared to A*'s , this is an enormous saving.
The Trade-Off: Redundant Work
The downside is that IDA* re-explores nodes across iterations. In the worst case, the last iteration explores roughly the same number of nodes as A*, but all previous iterations add overhead. For a branching factor , the total work is approximately:
Since this geometric series is dominated by the term, the asymptotic time complexity remains , the same as A*. The constant factor overhead is , which is small for large (for example, 1.11 when ).
When to Use IDA* Over A*
Memory-Constrained Environments
IDA* is the clear choice when memory is the bottleneck. If A* would need gigabytes of memory to solve a problem, IDA* can solve it with kilobytes.
Classic Puzzle Problems
IDA* excels at sliding tile puzzles (8-puzzle, 15-puzzle), Rubik's Cube solvers, and similar combinatorial puzzles where:
- The solution path is relatively short
- The branching factor is small to moderate
- The state space is enormous but the goal is reachable
Multi-Agent Path Finding (MAPF)
In MAPF, the state space grows exponentially with the number of agents. IDA*'s minimal memory footprint makes it feasible where A* would quickly run out of memory.
When A* Is Better
A* is preferable when:
- Memory is not a concern
- The graph has many distinct -values (causing IDA* to perform many iterations, each exploring only slightly more than the previous)
- You need to detect and avoid re-expanding the same states (A*'s closed list prevents this)
Comparison Table
| Feature | A* | IDA* |
| Memory | ||
| Time | (with small constant overhead) | |
| Optimal | Yes (with admissible heuristic) | Yes (with admissible heuristic) |
| Duplicate detection | Yes (closed list) | No (may revisit nodes) |
| Best for | Memory-rich environments | Memory-constrained environments |
| Implementation | Priority queue + hash set | Recursive DFS with threshold |
Variants and Improvements
- SMA* (Simplified Memory-Bounded A*): A compromise that uses as much memory as available, dropping the worst nodes when memory fills up.
- RBFS (Recursive Best-First Search): Similar to IDA* but uses a more refined threshold based on the best alternative path, reducing redundant work.
- Transposition tables: Adding a small cache to IDA* to remember recently visited states can significantly reduce re-exploration without requiring full A* memory.
Summary
IDA* provides a compelling alternative to A* when memory is the limiting factor. By trading a small constant factor in time for an exponential reduction in memory (from to ), it makes optimal pathfinding feasible in environments where A* would exhaust memory. The choice between them depends on your problem's characteristics: use A* when you have enough memory and want the fastest solution, and use IDA* when memory is scarce or the state space is too large to fit in memory.

