Iterative Deepening A* (IDA*)

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.

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.