Iterative Deepening

Depth-First Search is a fundamental graph and tree traversal algorithm that explores as far as possible along a single branch before backtracking. It uses a LIFO stack to manage the search frontier. While memory-efficient (O(b*m) for depth m and branching factor b), it can get stuck in deep, non-terminating paths and is not guaranteed to find the shortest solution. Iterative deepening mitigates these weaknesses by imposing a series of increasing depth limits on DFS.

Breadth-First Search is a graph traversal algorithm that explores all nodes at the present depth level before moving to nodes at the next depth level. It uses a FIFO queue to manage the frontier. BFS is complete and optimal (for uniform cost) because it finds the shallowest goal first. However, its memory requirement is exponential (O(b^d)), where b is the branching factor and d is the solution depth. Iterative deepening achieves BFS's optimality guarantees with DFS's linear memory footprint.

Depth-Limited Search is a variant of DFS that imposes a maximum depth limit l on the search. The algorithm backtracks when it reaches this limit, preventing infinite loops in infinite state spaces. The core challenge is selecting an appropriate l; if set too low, the goal may be unreachable, resulting in a failure. Iterative deepening automates this by performing a series of depth-limited searches, incrementing l until a solution is found, thus eliminating the need to guess the correct depth limit a priori.

Heuristic search algorithms, such as A* and Best-First Search, use an evaluation function f(n) to guide exploration toward the most promising nodes. A*, which combines the path cost g(n) and a heuristic estimate h(n), is both complete and optimal under admissible heuristics. While highly efficient in many domains, these algorithms often require storing the entire frontier in memory (O(b^d)). Iterative Deepening A* (IDA*) applies the iterative deepening principle to A*, using f(n) as the cutoff instead of depth, regaining optimality with linear memory.

The branching factor (b) is the average number of successor states generated from a given node, defining the exponential growth of the state space. A high branching factor (e.g., 35 in chess) makes exhaustive search intractable. Iterative deepening's time complexity is O(b^d), the same as BFS, but its memory complexity is only O(b*d). This makes it particularly valuable for problems with large branching factors where storing the entire BFS frontier is impossible, but repeated exploration of upper layers is computationally acceptable.

Tree search is the overarching paradigm for exploring possible sequences of actions represented as nodes and edges in a tree. Backtracking is a specific DFS technique used for constraint satisfaction problems (e.g., N-Queens, Sudoku) that abandons a partial candidate as soon as it violates constraints. Iterative deepening can be layered on top of backtracking to systematically explore deeper candidate solutions, ensuring a complete search is performed in a memory-efficient manner, even when the solution depth is unknown.