Abstract
This 1991 study provides a definitive guide to the trade-offs between fundamental heuristic search algorithms: Best-First Search (A), Iterative Deepening (ID), and Depth-First Branch-and-Bound (DFBB). The authors demonstrate that algorithmic performance is dictated by two key problem features: heuristic branching factor and solution density. They introduce DFS, a hybrid algorithm designed to outperform traditional methods in sparse, slow-growing search spaces such as mazes.
Introduction
In combinatorial optimization, Best-First Search (specifically A) is theoretically optimal because it expands the minimum number of nodes. However, its significant memory requirements—storing every encountered node—often lead to failure in practice. For instance, A can exhaust several megabytes of RAM in minutes on complex problems like the 15-puzzle.
To address this, depth-first variants were developed: Iterative Deepening (IDA*), which uses linear space by repeating searches with increasing cost thresholds, and Depth-First Branch-and-Bound (DFBB), which uses an upper bound to prune branches. This paper establishes an analytical framework to predict which memory-efficient algorithm is best suited for a given problem.
Methodology
The authors analyze time complexity based on two primary variables:
- Heuristic Branching Factor ($b$): The ratio of nodes at a specific cost to the nodes at the preceding cost level.
- Solution Density ($s$): The rate at which the number of solutions increases relative to search depth or cost.
They also propose DFS, a hybrid algorithm. DFS begins like Iterative Deepening but employs more liberal cost threshold increases to reduce iteration overhead. Upon finding a potential solution, it transitions to a DFBB phase to prune the remaining space and ensure optimality.
Experimental Evaluation
The theory was validated across three domains representing different combinations of $b$ and $s$: the 15-Puzzle (high $b$, low $s$), the Traveling Salesperson Problem (low $b$, high $s$), and Maze Navigation (low $b$, low $s$).
Traveling Salesperson Problem (TSP)
In the TSP domain, DFBB proved highly efficient, while IDA performance degraded significantly. As shown in Table 2, IDA became impractical for instances with more than 12 cities, whereas DFBB expanded only 10-20% more nodes than the theoretical minimum established by A*.
Maze Navigation
Maze navigation represents a "dead zone" where both ID and DFBB struggle due to low branching factors and low solution density. In this environment, the hybrid DFS algorithm demonstrated superior performance. For cost ranges between 200 and 500, DFS expanded approximately 1,901 nodes, significantly fewer than DFBB (~5,413) and ID (~58,585).
Discussion
The research highlights several key insights:
- Memory-Time Trade-offs: While A* expands fewer nodes, depth-first algorithms are often faster in real-time due to lower overhead (no priority queue maintenance) and efficient state-undoing.
- Algorithm Selection: IDA* is optimal when the search tree grows exponentially ($b > 1$), as the overhead of re-scanning earlier levels becomes negligible. Conversely, DFBB excels when solutions are plentiful, allowing for massive pruning once an initial solution is found.
- The Hybrid Advantage: DFS* effectively bridges the gap in problem spaces where neither exponential growth nor high solution density is present.
Conclusion and Future Work
The current analysis is primarily limited to state-space trees. Problems involving graphs with redundant paths or cycles require additional mechanisms, such as transposition tables, which were not the focus of this study. Future research could refine the cost-increment strategy for DFS* by dynamically sampling node distributions during search to optimize threshold adjustments.
Summary updated