Abstract
Motivated by an anomaly in branch-and-bound (BnB) search, we analyze its average-case complexity. We first delineate exponential vs polynomial average-case complexities of BnB. When best-first BnB is of linear complexity, we show that depth-first BnB has polynomial complexity. For problems on which best-first BnB has exponential complexity, we obtain an expression for the heuristic branching factor. Next, we apply our analysis to explain an anomaly in lookahead search on sliding-tile puzzles, and to predict the existence of an average-case complexity transition of BnB on the Asymmetric Traveling Salesman Problem. Finally, by formulating IDA* as costbounded BnB, we show its average-case optimality, which also implies that RBFS is optimal on average.
Introduction
Branch-and-Bound (BnB) is a fundamental algorithm for discrete optimization. While its worst-case performance is typically exponential, its practical behavior can be highly variable. A notable anomaly occurs in sliding-tile puzzles: depth-first search often generates fewer nodes on larger puzzles than on smaller ones when searching to the same depth. This paper provides a rigorous average-case analysis to explain such phenomena, identifying a sharp phase transition in search complexity.
The $B \cdot p_0$ Threshold
The core of the analysis uses a uniform random tree model with branching factor $B$ and edge costs drawn from a discrete distribution. A critical parameter is $p_0$, the probability that an edge has zero cost (meaning the child node has the same heuristic value as its parent). The product $B \cdot p_0$ represents the expected number of "same-cost" children.
The authors prove that the boundary $B \cdot p_0 = 1$ separates two distinct complexity regimes. When $B \cdot p_0 < 1$, the search cost grows exponentially with depth. Conversely, when $B \cdot p_0 > 1$, the search enters an "easy region" where the complexity becomes polynomial.
Explaining the Sliding-Tile Puzzle Anomaly
This theoretical framework directly explains the counterintuitive behavior observed in sliding-tile puzzles. In these puzzles, as the size increases (from the 8-puzzle to the 99-puzzle), the branching factor $B$ increases while the probability $p_0$ of a zero-cost move remains relatively stable (around 0.5). This shift pushes larger puzzles deeper into the polynomial "easy" region.
As shown in the figure, for a fixed lookahead depth $d$, the number of nodes generated for the 99-puzzle grows much more slowly than for the 8-puzzle, confirming the transition from exponential to polynomial growth as $B$ increases. This explains why searching a larger state space can actually be computationally cheaper for a fixed horizon.
Applications and Optimality
The analysis also predicts a complexity transition in the Asymmetric Traveling Salesman Problem (ATSP). By varying the range of city distances $k$, the probability $p_0$ changes, moving the problem across the $B \cdot p_0 = 1$ threshold. When $k$ is small, $p_0$ is high, making the problem easy; as $k$ increases, $p_0$ drops, and the problem becomes exponentially harder.
Furthermore, the paper establishes the average-case optimality of linear-space algorithms like Iterative-Deepening-A (IDA) and Recursive Best-First Search (RBFS). By formulating IDA* as a cost-bounded BnB, the authors show that no other linear-space algorithm can outperform them on average within the uniform random tree model.
Conclusion
By moving beyond worst-case bounds, this work provides a more nuanced understanding of heuristic search. The identification of the $B \cdot p_0$ threshold offers a practical metric—local consistency—to estimate search difficulty and explains why increasing problem size can sometimes lead to more efficient search. These results provide a theoretical foundation for the performance of modern search algorithms on large-scale optimization problems.
Summary updated