When tackling complex combinatorial optimization problems, researchers traditionally face a stark algorithmic choice between two competing philosophies: Best-First Search (BFS) and Depth-First Search (DFS).
- Best-First Search (such as A or AO) is globally informed. It uses heuristics to expand the most promising nodes across the entire search frontier. This global perspective makes it excellent at systematically tightening the theoretical bounds of a problem and proving global optimality. However, because it spreads its attention across many paths, it can suffer from massive memory overhead and often takes a long time to reach a leaf node and return its very first valid solution.
- Depth-First Search (and its variants like branch-and-bound or greedy backtracking) is locally focused. It dives straight down a single path until it hits a leaf. This allows it to find a valid, feasible solution almost immediately. The downside is myopia: it can spend massive amounts of time exploring highly suboptimal subtrees because it lacks the global perspective to realize a better path exists elsewhere.
For real-time or resource-constrained applications, neither pure strategy is ideal. We want anytime performance: the algorithm should find a decent solution quickly, but continuously improve that solution and provide a guarantee of how close it is to the optimum if interrupted.
To achieve this, a powerful paradigm has emerged: interleaving best-first and depth-first search. By combining these two strategies, solvers can squeeze the optimality gap from both sides simultaneously.
The Core Mechanism: Dual Bound Tightening
To understand why interleaving works, it helps to view optimization through the lens of bounding. For any minimization problem, the true optimal cost lies somewhere between a lower bound (the optimistic theoretical minimum proved so far) and an upper bound (the cost of the best valid solution found so far). The distance between these two is the optimality gap.
Pure Best-First: [Lower Bound ───►] . . . . . . . . . . . . . . . . . [True Optimum]
Pure Depth-First: [True Optimum] . . . . . . . . . . . . . . . . . [◄─── Upper Bound]
Interleaved: [Lower Bound ───►] . . . . . [◄─── Upper Bound]
A pure best-first search focuses entirely on raising the lower bound. A pure depth-first search focuses entirely on finding feasible solutions to lower the upper bound. Interleaved search does both.
As shown by Radu Marinescu et al. in the context of Marginal MAP (MMAP) problems, combining these strategies allows an algorithm to simultaneously tighten global upper bounds and discover feasible lower-bound solutions. In Anytime Best+Depth-First Search for Bounding Marginal MAP and AND/OR Search for Marginal MAP, the authors demonstrate that executing best-first steps to guide the global search frontier, punctuated by depth-first "dives" to find valid assignments, creates a shrinking confidence interval. This ensures that a valid solution is always available while its quality is rigorously certified.
This dual-bounding philosophy is not unique to tree search; it maps directly onto discrete optimization frameworks like MaxSAT and Pseudo-Boolean optimization:
- Core-guided search acts like best-first search, analyzing unsatisfiable cores to systematically raise the lower bound of the objective function.
- Model-guided (or linear) search acts like depth-first search, finding satisfying assignments to lower the upper bound.
In Exploiting the Structure of Unsatisfiable Cores in MaxSAT, Carlos Ansótegui et al. integrated a core-guided backbone with periodic model-guided optimization steps to rapidly discover high-quality upper bounds. Similarly, Jo Devriendt et al. applied this to Pseudo-Boolean optimization in Cutting to the Core of Pseudo-Boolean Optimization: Combining Core-Guided Search with Cutting Planes Reasoning. The authors proved that alternating between core-guided search and linear search creates a synergistic effect, narrowing the optimality gap far more robustly than using either strategy in isolation.
Balancing Exploration and Exploitation
Another way to understand the success of hybrid search is through the balance of exploration (global search) and exploitation (local refinement).
In online planning and reinforcement learning, this is often framed as balancing optimistic and conservative strategies. Truong-Huy D. Nguyen et al. explored this in Bootstrapping Simulation-Based Algorithms with a Suboptimal Policy, hybridizing optimistic search strategies that rapidly identify promising regions with conservative strategies that maintain rigorous value bounds. In a similar vein, Zongzhang Zhang et al. introduced an online planner in FHHOP: A Factored Hybrid Heuristic Online Planning Algorithm for Large POMDPs that combines upper-bound heuristics for exploration with lower-bound heuristics to refine high-quality policies during tree search.
The concrete implementation of this balance typically follows one of two patterns: phased switching or continuous interleaving.
Phased Switching
The earliest hybrid algorithms used a distinct transition point. In their classic study Depth-First Versus Best-First Search, Nageshwara Rao Vempaty et al. analyzed a hybrid mechanism that uses liberal cost threshold increases during an initial iterative deepening phase to accelerate the discovery of a first solution. Once that solution is found, the algorithm immediately switches to a branch-and-bound strategy to prune the remaining space and guarantee optimality. This prevents the excessive re-computation typical of pure iterative deepening.
Continuous Interleaving
Modern approaches prefer to alternate dynamically between the two modes to prevent the search from stalling. For instance, in Low-Level Search on Time Intervals in Branch-and-Cut-and-Price for Multi-Agent Path Finding, Edward Lam et al. designed a low-level pathfinder that periodically alternates between depth-first and best-first exploration. This prevents the high-level optimization framework from getting stuck in complex, redundant subtrees by periodically prioritizing nodes that appear closer to a valid solution.
Similarly, Junkyu Lee et al. utilized continuous interleaving within AND/OR search spaces for probabilistic planning in Probabilistic Planning With Influence Diagrams. By using best-first steps to tighten utility bounds and depth-first steps to quickly identify valid policies, the hybrid approach mitigates the slow convergence of pure best-first search while avoiding the local myopia of pure depth-first methods.
Broad Application Domains
Because the trade-off between global bounds and local solutions is universal to optimization, interleaved search has driven breakthroughs across highly diverse domains:
1. Optimal Decision Trees
Traditional decision tree induction algorithms use greedy, depth-first heuristics that do not guarantee global optimality. To find mathematically optimal sparse decision trees, Ayman Chaouki et al. framed the problem as an AND/OR graph search. In Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees and Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO*, the authors demonstrated that utilizing an informed best-first strategy (AO*) yields vastly superior anytime performance compared to depth-first alternatives. If the search is interrupted early, the intermediate tree is significantly closer to the true global optimum.
2. Multi-Agent Coalition Structure Generation
Partitioning a set of agents into optimal coalitions is an NP-complete problem. In Anytime Optimal Coalition Structure Generation, Talal Rahwan et al. introduced a strategy that combines a best-first selection of promising sub-spaces with branch-and-bound pruning. This allowed them to provide tight theoretical quality guarantees throughout execution. The authors expanded this framework in Coalition Structure Generation in Multi-Agent Systems with Positive and Negative Externalities, using an anytime branch-and-bound strategy that pairs depth-first search with dynamic pruning to return valid partitions rapidly while iteratively refining the error bound.
3. Graphical Models and Probabilistic Reasoning
Beyond deterministic trees, interleaving is highly effective when combined with learning. In Stochastic Anytime Search for Bounding Marginal MAP, Radu Marinescu et al. interleaved greedy depth-first exploration with heuristic learning steps. The depth-first dives find initial solutions quickly, while the learning phase updates heuristic values based on that search experience, guiding subsequent best-first global exploration to systematically refine the upper bounds.
Summary
Interleaved best-first and depth-first search works because it treats optimization not as a single journey toward an answer, but as a dual-sided coordination problem. By utilizing best-first mechanisms to maintain global awareness and tighten theoretical bounds, alongside depth-first mechanisms to rapidly exploit local paths and secure feasible solutions, hybrid solvers achieve excellent anytime utility and robust convergence across both discrete and probabilistic domains.
Key Foundational Work
Depth-First Versus Best-First Search (1991) — contributed 2 concept elements to this direction.
Back to Backtracking: Controlling the ATMS (1986) — contributed 1 concept elements to this direction.