## Definition **Iterative Deepening A\* (IDA\*)** combines [[Iterative Deepening Search]] with the A* evaluation function. Instead of a depth limit, the cutoff is an **$f$-cost limit** that grows monotonically across iterations. ## Algorithm ``` cutoff ← h(start) loop: next_cutoff ← ∞ found, next_cutoff ← DFS_with_f_limit(start, cutoff) if found: return found if next_cutoff == ∞: return failure cutoff ← next_cutoff ``` `DFS_with_f_limit` recurses with DFS but prunes any node with $f > \text{cutoff}$, recording the minimum pruned $f$ for the next iteration. ## Properties - **Complete:** yes. - **Optimal:** yes, with an admissible heuristic. - **Time:** comparable to A* on most problems. - **Space:** $O(bd)$ — the killer feature. ## When to Prefer IDA* Over A* - Memory matters more than recomputation. - The state space is too large for A* to fit in memory (the 15-puzzle, Rubik's cube, large planning problems). ## Limitation IDA* doesn't store visited states across iterations. In state spaces with many *cycles* or many paths to the same state, it re-expands the same states repeatedly. **Transposition tables** mitigate this for problems where the same state recurs often. ## Notable Use The 15-puzzle, where A* runs out of memory but IDA* completes in seconds with a good heuristic (e.g., Manhattan distance + linear conflicts). IDA* was the first algorithm to solve the 15-puzzle in optimal moves for arbitrary instances. ## Related - [[A Star Algorithm]] - [[Iterative Deepening Search]] - [[Heuristic Search]]