IDA* (Iterative Deepening A*)

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 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.