Iterative Deepening A* (IDA*)

IDA* operates by performing a series of depth-first searches (DFS) with an increasing cost threshold (f-cost). The f-cost for a node is calculated as f(n) = g(n) + h(n), where g(n) is the actual cost from the start, and h(n) is the heuristic estimate to the goal.

• The algorithm begins with a threshold equal to the heuristic estimate of the start state: threshold = h(start).
• It performs a DFS that prunes any branch where f(n) > threshold.
• If the goal is not found, the threshold is increased to the minimum f-cost that exceeded the previous threshold among all pruned nodes, and the search repeats.

This iterative process guarantees that the first solution found is optimal if the heuristic is admissible.

The primary advantage of IDA* over standard A* is its extremely low memory footprint. While A* must maintain an open list (frontier) and a closed list (explored set), IDA* only needs to store the current path from the root to the active node on the recursion stack.

• Space Complexity: O(d), where d is the depth of the solution. This is linear in the depth, compared to A*'s O(b^d) in the worst case for storing all explored nodes.
• This makes IDA* suitable for problems with massive state spaces where storing the entire explored graph is infeasible.
• The trade-off is the recomputation of nodes in each iteration, as the DFS does not remember previously visited states across iterations.

Like A*, IDA* requires the heuristic function h(n) to be admissible to guarantee an optimal solution. An admissible heuristic never overestimates the true cost to reach the goal.

• Consistency/Monotonicity: While not strictly required for correctness, a consistent heuristic (where h(n) ≤ c(n, n') + h(n') for all successors n') ensures that f(n) is non-decreasing along any path. This improves efficiency in IDA* by reducing the number of node re-expansions.
• If the heuristic is not admissible, IDA* may find a solution, but it will not be guaranteed to be the cheapest path.
• Common admissible heuristics include Euclidean distance for pathfinding on a plane or Manhattan distance for grid-world problems with 4-directional movement.

The intelligence of IDA* lies in how it updates the cost threshold between iterations. It is not simply incremented by a fixed amount.

• During a depth-first search, the algorithm tracks the minimum f-cost encountered that exceeded the current threshold. This value is often called the next_threshold or flimit.
• When the DFS completes without finding the goal, the threshold for the next iteration is set to this next_threshold.
• This ensures each iteration explores all nodes with an f-cost less than or equal to the new threshold, systematically exploring the state space in order of increasing f-cost, mirroring A*'s optimal expansion order.
• This update rule is what allows IDA* to be both complete and optimal.

IDA*'s performance is a direct trade-off between time and space. Its time complexity is difficult to state precisely but is generally higher than A*'s due to node re-expansion.

• Time Complexity: In the worst case, it can be O(b^d), where b is the branching factor and d is the solution depth. However, with a good heuristic, it is often far better.
• Major Drawback: If the heuristic provides little guidance or if the cost function has many distinct values, IDA* can suffer from excessive node regeneration, leading to long runtimes. For example, in a tree with a unique f-cost for each node, IDA* may perform a new DFS for every node on the solution path.
• Optimizations: Techniques like transposition tables (to cache visited states) or recursive best-first search (RBFS) can mitigate recomputation overhead but reintroduce memory usage.

IDA* occupies a specific niche in the heuristic search landscape.

• vs. A Search*: IDA* is memory-optimal but generally slower due to recomputation. Use IDA* when the state space is too large for A*'s memory requirements.
• vs. Iterative Deepening DFS (IDDFS): IDA* is informed by a heuristic, making it exponentially faster than uninformed IDDFS on many problems.
• vs. Recursive Best-First Search (RBFS): Both are linear-space algorithms. RBFS uses slightly more memory to store sibling f-limits and often regenerates fewer nodes than IDA*, but its implementation is more complex.
• Typical Applications: IDA* is historically famous for solving the 15-puzzle and other single-agent puzzle problems. It is less common in real-time applications like video game pathfinding due to its unpredictable, iteration-based runtime.

A Search* is the foundational best-first pathfinding algorithm upon which IDA* is built. It finds the lowest-cost path by evaluating nodes using the function f(n) = g(n) + h(n), where g(n) is the exact cost from the start node and h(n) is a heuristic estimate to the goal. Unlike IDA*, A* typically requires storing the entire open list and closed list in memory, which can be prohibitive for large state spaces. IDA* was created to preserve A*'s optimality and heuristic guidance while eliminating its memory footprint.

Iterative Deepening is a general search strategy that performs a series of depth-limited depth-first searches (DFS), incrementally increasing the depth limit. This approach combines the completeness and optimality (for uniform-cost trees) of breadth-first search with the linear memory efficiency of DFS. IDA* adapts this core idea, but instead of using a simple depth limit, it uses a cost threshold (f-cost) based on the A* evaluation function, making it suitable for weighted graphs.

Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along a branch before backtracking, using a stack (implicitly via recursion) to manage the frontier. IDA*'s underlying exploration mechanism is a depth-first search, but it is guided by a cost threshold and a heuristic. This allows IDA* to inherit DFS's memory efficiency—it only needs to store the current path, requiring O(d) memory where d is the depth of the solution—while being far more directed and optimal.

A heuristic function, h(n), estimates the cost from a node n to the nearest goal. For IDA* (and A*) to guarantee an optimal solution, the heuristic must be admissible (never overestimates the true cost) and ideally consistent (monotonic).

• Admissibility ensures the algorithm does not miss a better path.
• Consistency ensures that the f-cost is non-decreasing along any path, which is critical for IDA*'s iterative threshold increases to work correctly. Poor heuristics can cause IDA* to degrade to exhaustive iterative deepening.

Recursive Best-First Search (RBFS) is another memory-limited search algorithm designed as a more efficient alternative to IDA*. It operates similarly to a recursive best-first search but keeps track of a second-best f-value (an alternative) for each node to allow intelligent backtracking. Compared to IDA*:

• RBFS can be more efficient as it uses stored f-cost information to avoid re-exploring entire subtrees.
• IDA* is often simpler to implement and can have lower overhead per node, but may re-explore significant portions of the state space with each iteration.

The search space is the set of all possible states and transitions a search algorithm like IDA* must explore. The state space is its formal representation, defined by:

• An initial state (the start node).
• A successor function (generates possible next states/actions).
• A goal test.
• A path cost function. IDA* is particularly advantageous when this space is large or infinite and memory is constrained. Its efficiency is highly dependent on the branching factor and the quality of the heuristic used to prune the space.