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 $f(n) = g(n) + h(n)$ 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 $f(n)$
• Closed list (hash set): nodes already expanded, to avoid revisiting

At each step, A* extracts the node with the lowest $f(n)$ value from the open list, expands it (generating its successors), and adds the successors to the open list. The evaluation function is:

• $g(n)$: actual cost from the start node to node $n$
• $h(n)$: heuristic estimate of the cost from $n$ to the goal
• $f(n) = g(n) + h(n)$: estimated total cost of the cheapest path through $n$

A* is guaranteed to find the optimal solution when the heuristic $h(n)$ 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 $b$ and solution depth $d$, the number of nodes stored can grow as $O(b^d)$. In practice, this means A* can exhaust available memory long before it exhausts available time. For example, with $b = 10$ and $d = 8$, A* may store up to $10^8 = 100$ million nodes.

How IDA* Works

IDA* combines the optimality guarantee of A* with the memory efficiency of depth-first search. It works in iterations:

1. Set initial threshold to $f(\text{start}) = h(\text{start})$.
2. Perform depth-first search, but prune any node where $f(n)$ exceeds the current threshold.
3. If goal is not found, set the new threshold to the smallest $f(n)$ value that exceeded the previous threshold.
4. Repeat until the goal is found.

1def ida_star(start, goal, h):
2    threshold = h(start)
3
4    def search(node, g, threshold):
5        f = g + h(node)
6        if f > threshold:
7            return f, None
8        if node == goal:
9            return f, [node]
10        min_threshold = float('inf')
11        for neighbor, cost in node.successors():
12            t, path = search(neighbor, g + cost, threshold)
13            if path is not None:
14                return t, [node] + path
15            min_threshold = min(min_threshold, t)
16        return min_threshold, None
17
18    while True:
19        t, path = search(start, 0, threshold)
20        if path is not None:
21            return path
22        if t == float('inf'):
23            return None  # no solution
24        threshold = t

Memory Usage

IDA* only stores the current path from root to the node being explored. This requires $O(d)$ memory, where $d$ is the solution depth. Compared to A*'s $O(b^d)$, 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 $b$, the total work is approximately:

$$\text{Total nodes} \approx b^d + b^{d-1} + b^{d-2} + \ldots = \frac{b^{d+1} - 1}{b - 1}$$

Since this geometric series is dominated by the $b^d$ term, the asymptotic time complexity remains $O(b^d)$, the same as A*. The constant factor overhead is $\frac{b}{b-1}$, which is small for large $b$ (for example, 1.11 when $b = 10$).

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 $f$-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

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 $O(b^d)$ to $O(d)$), 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.