Abstract: Best-first search (BFS) expands the fewest nodes among all admissible algorithms using the same cost function, but typically requires exponential space. Depth-first search needs space only linear in the maximum search depth, but expands more nodes than BFS. Using a random tree, we analytically show that the expected number of nodes expanded by depth-first branch-and-bound (DFBnB) is no more than $O(d \cdot N)$, where $d$ is the goal depth and $N$ is the expected number of nodes expanded by BFS. We also show that DFBnB is asymptotically optimal when BFS runs in exponential time. We then consider how to select a linear-space search algorithm, from among DFBnB, iterative-deepening (ID) and recursive best first search (RBFS). Our experimental results indicate that DFBnB is preferable on problems that can be represented by bounded-depth trees and require exponential computation; and RBFS should be applied to problems that cannot be represented by bounded-depth trees, or problems that can be solved in polynomial time.
Introduction
In heuristic search, researchers face a classic trade-off between time and memory. Best-First Search (BFS), such as A, is "node-optimal"—it expands the absolute minimum number of nodes necessary to find an optimal solution. However, it stores every generated node in memory, leading to exponential space requirements that can quickly exceed system limits. Linear-space alternatives like Depth-First Branch-and-Bound (DFBnB), Iterative Deepening (ID), and Recursive Best-First Search (RBFS)* solve the memory problem but often at the cost of expanding more nodes due to re-exploration. This paper provides a rigorous comparison of these algorithms, establishing new theoretical bounds and practical selection criteria.
Methodology
The authors employ a combination of analytical modeling and empirical testing:
- Analytical Model: A "random tree" model is used where edge costs are independent and identically distributed (i.i.d.). This allows for mathematical derivation of the expected number of nodes expanded.
- Complexity Analysis: Search problems are categorized by the product $bp_0$, where $b$ is the mean branching factor and $p_0$ is the probability of a zero-cost edge. This value determines the transition between polynomial and exponential search time.
- Experimental Domains: Claims are validated on synthetic random trees, sliding-tile puzzles (8, 15, 24, and 99-puzzles), and the Asymmetric Traveling Salesman Problem (ATSP) using subtour elimination.
Theoretical Insights
A major contribution of this work is proving that the expected number of nodes expanded by DFBnB is at most $O(d \cdot N)$, where $d$ is the goal depth and $N$ is the number of nodes BFS expands. This bound suggests that the overhead of depth-first search is much lower than previously feared.
Furthermore, the authors identify a critical phase transition at $bp_0 = 1$. As shown in Figure 2, this boundary separates regimes of different computational complexity. If $bp_0 < 1$, the search typically runs in exponential time, and both BFS and DFBnB are asymptotically optimal. If $bp_0 \geq 1$, the problem becomes significantly easier, often solvable in polynomial time.
Experimental Results
The empirical results across various branching factors and cost distributions (Figure 6) confirm the theoretical findings. While BFS expands the fewest nodes, it incurs a hidden computational cost: maintaining a large priority queue. As search depth $d$ increases, the $O(\log N)$ or $O(d)$ overhead for queue operations can make BFS slower in wall-clock time than DFBnB, which processes nodes in $O(1)$ constant time.
Key findings from specific domains include:
- ATSP: DFBnB and RBFS significantly outperformed Iterative Deepening. On difficult instances with unique node costs, DFBnB was the clear winner due to lower regeneration overhead compared to RBFS.
- Sliding-Tile Puzzles: DFBnB is superior for smaller puzzles (8-puzzle). However, as puzzle size increases (99-puzzle), the branching factor and $bp_0$ rise, making RBFS the more efficient choice.
Conclusion and Algorithm Selection
The study concludes with a practical guide for algorithm selection:
- DFBnB is best for problems with bounded depth and exponential complexity (e.g., ATSP).
- RBFS is superior for problems that cannot be represented by bounded-depth trees or those solvable in polynomial time.
While these results provide a strong foundation for tree search, future work is needed to address graph search scenarios where duplicate node detection is critical and may require additional memory-efficient techniques.
Summary updated