IDA* (Iterative Deepening A*)

IDA* performs a series of depth-first searches (DFS), each with an increasing cost threshold (often denoted as f-limit or bound). This threshold is the maximum allowed f-cost for a node, where f(n) = g(n) + h(n).

• g(n): The actual cost from the start node to node n.
• h(n): The heuristic estimate from node n to the goal. The algorithm explores all paths where f(n) ≤ threshold. If the goal is not found, the threshold is increased to the minimum f-cost that exceeded the previous bound, and a new DFS begins. This process repeats until the goal is found.

The primary advantage of IDA* is its extremely low memory footprint. Because it uses depth-first search at its core, it only needs to store the current path from the root to the frontier node on the call stack.

• Memory Complexity: O(d), where d is the depth of the solution. This is linear in the depth of the search tree.
• Contrast with A*: Standard A* must maintain both an open set (frontier) and a closed set (explored nodes), leading to memory complexity that is exponential in the depth for many problems (O(b^d), where b is branching factor). IDA* sacrifices time to regain tractable space usage for very deep searches.

Like A*, IDA* guarantees an optimal solution (the shortest path or least-cost path) provided its heuristic function, h(n), is admissible. An admissible heuristic never overestimates the true cost to reach the goal.

• The iterative deepening process ensures the first goal node found is the one with the lowest f-cost.
• Because the threshold increases to the minimum exceeding cost, the algorithm systematically explores nodes in order of increasing f-cost, mirroring A*'s optimal expansion order without storing all frontier nodes.

IDA* is a complete algorithm, meaning it will always find a solution if one exists, given two conditions:

1. The state space has a finite branching factor.
2. The cost function is such that there are no cycles with zero or negative cost that could trap the search indefinitely. Its completeness is inherited from iterative deepening depth-first search (IDDFS), which itself is complete because it eventually searches to any finite depth.

A significant weakness of IDA* is its performance on problems with large areas of states sharing the same f-cost, known as heuristic plateaus or f-cost contours.

• On a plateau, the algorithm conducts a full depth-first search within that entire f-cost contour before increasing the threshold.
• This can lead to excessive node re-expansion, as nodes on the plateau are revisited in each iteration until the threshold finally increases. This makes its time complexity often worse than A*'s for problems where the heuristic provides less discriminative guidance.

IDA* is the algorithm of choice when the state space is extremely large and storing the entire frontier and explored sets is infeasible, but an admissible heuristic is available. Classic Applications:

• The 15-puzzle and other sliding tile puzzles.
• Solving Rubik's Cube optimally.
• Theorem proving and other combinatorial search problems in AI. It is less suitable for real-time pathfinding in video games or robotics, where A*'s faster time performance (using memory) is typically preferred.

The foundational algorithm upon which IDA* is built. A Search* is a best-first graph traversal algorithm that finds the lowest-cost path by combining the actual cost to reach a node, g(n), with a heuristic estimate of the cost to the goal, h(n). It maintains an open list (priority queue) of nodes to explore and a closed list of explored nodes, guaranteeing optimality if the heuristic is admissible (never overestimates). Its primary drawback is memory usage, as it stores all generated nodes, which IDA* was designed to solve.

• Key Property: Optimal and complete with an admissible heuristic.
• Memory Complexity: O(b^d), where b is branching factor, d is solution depth.
• Primary Use Case: Pathfinding in video games (e.g., NPC navigation) and robotics when memory is not a critical constraint.

The memory-saving strategy that IDA* adapts. Iterative Deepening is a graph search strategy that performs a series of depth-limited depth-first searches (DFS), incrementally increasing the depth limit until the goal is found. It combines the space efficiency of DFS (O(bd), where b is branching factor, d is depth) with the completeness and optimality guarantees of breadth-first search (BFS) for unweighted graphs. Each iteration re-explores shallower levels, which seems inefficient but is often acceptable because the number of nodes grows exponentially with depth.

• Core Mechanism: Repeated depth-first searches with increasing cutoff.
• Advantage: Drastically reduces memory footprint compared to BFS or A*.
• Foundation: Provides the iterative, depth-first framework that IDA* enhances with heuristic guidance.

The underlying traversal method for each iteration of IDA*. Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking, using a stack (either explicitly or via recursion) to manage the search frontier. It is not optimal and not complete in infinite spaces, but it has minimal memory requirements, storing only the current path (O(d)). IDA* uses a DFS at its core for each cost-bound iteration, but guides it with a heuristic f-cost threshold instead of a simple depth limit, and prunes branches where f(n) exceeds the bound.

• Memory Use: O(d), ideal for deep search spaces.
• IDA Adaptation*: DFS is modified to use an f-cost limit (g(n)+h(n)) and to return the next minimum threshold.

Another memory-efficient best-first search algorithm often compared to IDA*. Recursive Best-First Search (RBFS) is a recursive algorithm that simulates A* search while using only linear space. It keeps track of an f-limit for each recursive call and updates alternative f-cost values for siblings. When a node's f-cost exceeds its f-limit, recursion unwinds to the next best alternative path. Compared to IDA*, RBFS can be more efficient in terms of node regeneration because it remembers the best alternative path, but it involves more complex bookkeeping and overhead.

• Space Complexity: O(bd), but often more efficient in practice than IDA*.
• Trade-off: Reduces node re-expansion at the cost of increased computational overhead per node.
• Use Case: Useful for problems where the heuristic is expensive to compute, making node regeneration costly.

The guiding intelligence for both A* and IDA*. A heuristic function, h(n), estimates the cost from a given node n to the nearest goal state. The quality of this function directly determines algorithm efficiency.

• Admissible Heuristic: Never overestimates the true cost. Required for A* and IDA* to guarantee optimality. Example: Straight-line distance in pathfinding.
• Consistent (Monotonic) Heuristic: Satisfies the triangle inequality: h(n) ≤ c(n, n') + h(n'), where n' is a successor of n. Ensures A* finds optimal paths without re-opening nodes.
• Dominance: If h₂(n) ≥ h₁(n) for all n, h₂ is said to dominate h₁ and will typically lead to a more efficient search, expanding fewer nodes. IDA*' performance is exceptionally sensitive to the accuracy of the heuristic.

The formal problem context in which IDA* operates. The state space is a conceptual model of a problem, defined by:

• States: All possible configurations of the problem (e.g., a board position in the 15-puzzle, a location on a map).
• Initial State: The starting point.
• Goal State(s): The condition(s) that define a solution.
• Actions/Operators: Rules that define legal moves between states.
• Successor Function: Given a state, returns all states reachable by a single action.
• Path Cost: A function that assigns a numeric cost to a sequence of actions.

The search space is the portion of the state space that is actually explored by an algorithm like IDA*. IDA* excels in large or infinite state spaces where storing the entire explored graph (as A* does) is infeasible, as it only needs memory proportional to the depth of the current path.