Cost-error relationships in A* tree-searching
Henry W. Davis · Journal of the ACM · 1990
Pearl has shown that, in admissible A* tree-searching, the expected number of nodes expanded is bounded above and below by exponential functions of heuristic error. An additional assumption required for the validity of Pearl's argument is given. The assumption's significance and interpretation are discussed.