Am Average-Case with Applications: Summary of
Weixiong Zhang, Richard E. Korf · 1992
Abstract # of nodes generated Motivated by an anomaly in branch-and-bound (BnB) search, we analyze its average-case com-plexity. We first delineate exponential vs poly-nomial 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 expo-nentia.1 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 a.verage-case complexity transition of BnB on the Asymmetric Traveling Salesman Problem. Finally, by formulating IDA * as cost-bounded BnB, we show its aaverage-case optima.l-ity, which also implies tl1a.t RBFS is optimal on avera.ge.