An Average-Case Analysis of Branch-and-Bound with Applications: Summary of Results

Weixiong Zhang, Richard E. Korf

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 haa 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 aaverage-case optimality, which also implies that RBFS is optimal on average.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.