Iterative Deepening Depth-First Search

Iterative Deepening Depth-First Search (IDDFS) is a state-space search strategy that repeatedly runs depth-limited search (DLS) with increasing depth bounds until the target state is discovered. By synthesizing the space efficiency of depth-first search O(d) with the optimality and completeness of breadth-first search on unweighted graphs, IDDFS mitigates the exponential memory footprint of BFS while preserving the guarantee of finding the shortest path in terms of edge traversals.

#include <vector>
#include <optional>
#include <iostream>

using Graph = std::vector<std::vector<int>>;

struct SearchResult {
    bool found;
    int depth_reached;
};

class IDDFS {
private:
    bool dls(int current, int target, int limit, const Graph& graph) {
        if (current == target) return true;
        if (limit <= 0) return false;

        for (int neighbor : graph[current]) {
            if (dls(neighbor, target, limit - 1, graph)) {
                return true;
            }
        }
        return false;
    }

public:
    bool search(int root, int target, int max_depth, const Graph& graph) {
        for (int depth = 0; depth <= max_depth; ++depth) {
            if (dls(root, target, depth, graph)) {
                return true;
            }
        }
        return false;
    }
};

int main() {
    Graph g = {
        {1, 2},
        {3, 4},
        {5},
        {},
        {},
        {}
    };
    IDDFS iddfs;
    bool result = iddfs.search(0, 5, 3, g);
    std::cout << "Target found: " << (result ? "true" : "false") << std::endl;
    return 0;
}

bool dls_safe(int current, int target, int limit, const Graph& graph, std::vector<bool>& visited) {
    if (current == target) return true;
    if (limit <= 0) return false;
    
    visited[current] = true;
    for (int neighbor : graph[current]) {
        if (!visited[neighbor]) {
            if (dls_safe(neighbor, target, limit - 1, graph, visited)) {
                visited[current] = false;
                return true;
            }
        }
    }
    visited[current] = false;
    return false;
}

Mathematical Derivation & Time Complexity Overhead

At first glance, repeating lower-level searches in IDDFS appears computationally wasteful. However, in a search tree with branching factor b and depth d, the nodes at the bottom level d are generated once, those at depth d-1 are generated twice, and so on up to the root, which is generated d+1 times. The total number of generated nodes N(IDDFS) is expressed as: N(IDDFS) = b^d + 2b^(d-1) + 3b^(d-2) + … + d*b. Factoring out b^d yields N(IDDFS) = b^d * (1 + 2/b + 3/b^2 + …). For b > 1, this geometric series converges to a constant factor overhead bounded by b / (b – 1)^2. Thus, the asymptotic time complexity remains O(b^d), matching breadth-first search while maintaining an O(d) memory ceiling.

Architectural Trade-offs: IDDFS vs BFS vs DFS

Breadth-First Search guarantees optimality and completeness but requires O(b^d) memory, rendering it unfeasible for massive state spaces like chess engines or complex robotic path planning. Depth-First Search consumes O(d) space but can loop infinitely on cyclic graphs and fails to find the shortest path. IDDFS bridges this architectural divide: it inherits the O(d) space footprint of DFS while maintaining BFS's shortest-path optimality on unweighted graphs. Engineers must evaluate whether the redundant node generation overhead is acceptable relative to available physical RAM.