Abstract
Iterative Deepening A (IDA) is a widely used search algorithm designed to find optimal paths while maintaining a significantly smaller memory footprint than the standard A algorithm. For years, the academic community operated under the assumption that IDA is always asymptotically optimal on trees under specific conditions. This paper provides a rigorous theoretical re-evaluation of these assumptions, proving that previously established conditions for IDA efficiency are neither necessary nor sufficient. By introducing the concept of "dummy iterations," the authors establish new, precise conditions for IDA optimality and demonstrate that on acyclic graphs, IDA can perform exponentially worse than A due to its lack of a memory-based closed list.
Introduction
In the field of heuristic search, A is considered the gold standard for finding the shortest path. However, its primary drawback is its memory consumption: it must store every node it visits, which often leads to system crashes on complex problems. IDA was introduced to mitigate this by employing a depth-first approach that resets with an increasing "cost threshold" in each iteration, requiring only linear memory relative to the search depth.
Historically, researchers relied on a set of conditions proposed by Richard Korf in 1988, which suggested that IDA would expand the same number of nodes as A (asymptotically $O(N)$) on trees. This paper addresses the critical gap between that theoretical assumption and practical reality, showing that IDA* can be significantly slower than expected in common search scenarios.
Methods and Tree Analysis
The authors utilize formal mathematical analysis and counter-example construction to challenge existing search theories. They categorize IDA* iterations into two distinct types:
- Active Iterations: Iterations where the number of new nodes grows exponentially.
- Dummy Iterations: Iterations where the number of new nodes does not grow significantly.
By constructing specific tree structures, the authors demonstrate that the presence and placement of these dummy iterations are the true determinants of performance. Even when Korf's conditions are met, IDA* can be forced into inefficient behavior.
Key Insights
- Flaws in Korf’s Conditions: The paper proves that the "Mandatory Condition" (Heuristic Branching Factor > 1) is not necessary, and the "Secondary Conditions" (exponential search space, finite precision) are not sufficient to guarantee $O(N)$ performance.
- The "Dummy Iteration" Trap: The real bottleneck for IDA* is not simply the total number of iterations, but where they occur. If many "dummy" iterations happen at the end of the search, the algorithm wastes massive amounts of time re-scanning the same tree structure without discovering significant new portions of the state space.
- Memory vs. Time Trade-off: The authors establish a "negative" result, proving that no best-first search algorithm using sub-linear memory can match A*’s efficiency on all possible tree structures.
Graph Performance and Results
The analysis extends to Directed Acyclic Graphs (DAGs), highlighting a massive hidden cost of using IDA on non-tree structures. Because IDA "forgets" nodes to save space, it lacks a closed list to prevent the re-expansion of previously visited nodes. On a DAG with $N$ nodes, IDA can expand $\Omega(2^{2N})$ nodes, while A would only expand $O(N)$.
Key results from the study include:
- Tree Complexity: On trees, IDA* can be forced into $O(N \log N)$ or even $O(N^2)$ node expansions in the worst case.
- The New Optimality Rule: Theorem 4 states that IDA is $O(N)$ if and only if the number of dummy iterations occurring after* the last active iteration is bounded by a constant.
Conclusion
While IDA remains a valuable tool for memory-constrained environments, this research warns against the blind assumption of its optimality. The authors suggest that for graph searches, it is often more efficient to use dedicated graph search algorithms rather than forcing a tree-search variant like IDA to handle them. Future work may focus on refining limited-memory algorithms like MA* and MREC to better bridge the gap between memory conservation and computational speed.
Summary updated