Complexity Analysis of Admissible Heuristic Search

Abstract

We analyze the asymptotic time complexity of admis-sible heuristic search algorithms such as A*, IDA*, and depth-first branch-and-bound. Previous analyses relied on an abstract analytical model, and character-ize the heuristic function in terms of its accuracy, but do not apply to real problems. In contrast, our anal-ysis allows us to accurately predict the performance of these algorithms on problems such as the sliding-tile puzzles and l~ubik’s Cube. The heuristic function is characterized simply by the distribution of heuris-tic values in the problem space. Contrary to conven-tional wisdom, our analysis shows that the asymptotic heuristic branching factor is the same as the brute-force branching factor, and that the effect of a heuris-tic function is to reduce the effective depth of search, rather than the effective branching factor.