Introduction
In the field of automated deduction and logic programming during the mid-1980s, researchers faced a fundamental trade-off between search completeness and computational efficiency. Traditional Breadth-First Search (BFS) offered completeness—the guarantee of finding a solution if one exists—and the ability to find the shortest path. However, BFS suffers from exponential memory requirements, as it must store the entire frontier of the search tree. Conversely, Depth-First Search (DFS) is highly memory-efficient, requiring space only linear to the depth of the search, but it is "incomplete"; it can easily become trapped in infinite branches, failing to explore other potentially successful paths.
This paper analyzes Consecutively Bounded Depth-First Search (CBDFS), a strategy now widely recognized as Iterative Deepening Depth-First Search. CBDFS bridges the gap between BFS and DFS, providing the completeness of the former with the space efficiency of the latter.
The CBDFS Algorithm
The mechanism of CBDFS is straightforward. The algorithm performs a series of depth-limited DFS passes:
- It begins with a depth limit of 1.
- If no solution is found within that limit, the search is terminated, and a new DFS is initiated from the root with a depth limit of 2.
- This process repeats, incrementing the depth limit by 1 in each successive iteration, until a goal node is reached.
While re-exploring the tree from the root in every iteration may intuitively seem inefficient, the authors demonstrate through mathematical analysis that the overhead is remarkably low in search spaces with exponential growth.
Theoretical Analysis of Overhead
The efficiency of CBDFS relies on the "Exponential Growth Paradox." In a search tree with a uniform branching factor $b$, the number of nodes at any given level $d$ is $b^d$. The total number of nodes in the tree up to depth $d$ is given by the geometric series:
$$N = \sum_{i=0}^{d} b^i = \frac{b^{d+1} - 1}{b - 1}$$
Because the number of nodes grows exponentially, the majority of the work in any search is concentrated at the deepest level. The authors prove that for a uniform branching factor $b$, the total number of nodes generated by CBDFS compared to the number of nodes generated by a single BFS to the same depth is approximately $b / (b - 1)$.
For example:
- If $b = 2$, CBDFS performs roughly twice the work of BFS.
- If $b = 10$, CBDFS performs only about 1.11 times the work of BFS (an 11% overhead).
This small computational cost is a minor price to pay for the massive reduction in memory requirements, shifting the space complexity from $O(b^d)$ to $O(d)$.
Applications in Logic Programming
A significant portion of the paper discusses the relevance of CBDFS to PROLOG and automated deduction systems. DFS is the native search strategy for PROLOG because it allows for an extremely efficient implementation of variable bindings and backtracking. In a DFS, the system only needs to maintain a single "environment" or set of variable assignments at any time.
Implementing BFS in a PROLOG-like environment would require the system to maintain multiple independent environments for every node on the search frontier, which is computationally prohibitive. CBDFS allows researchers to leverage the existing, highly optimized DFS machinery of PROLOG while gaining the completeness and shortest-path guarantees of BFS.
Heuristics and Admissibility
The authors also extend the analysis to include heuristic-driven searches. By incorporating a heuristic estimate—representing the remaining distance to a goal—the search can prune branches where the current depth plus the heuristic estimate exceeds the current bound. This approach is analogous to the A* algorithm. The authors confirm that CBDFS is "admissible," meaning it is guaranteed to find the shortest solution path first, provided the heuristic never overestimates the actual cost to the goal.
Conclusion and Limitations
While CBDFS is highly effective in exponential search spaces, its performance is sensitive to the branching factor. In "thin" search spaces where the branching factor is close to 1 (e.g., a single long chain of nodes), the overhead of CBDFS can degrade to $O(d^2)$. Additionally, the authors acknowledge that the re-computation of nodes is technically "wasted" effort, though they argue that the implementation efficiencies of DFS in practical systems like PROLOG often more than compensate for this theoretical waste.
Ultimately, CBDFS provides a robust framework for automated deduction, enabling complete and optimal searches within strict memory constraints—a legacy that continues to influence modern AI search strategies.
Summary updated