On the value of good advice: the complexity of A* search with accurate heuristics
Hang Dinh, Alexander C. Russell, Yuan Su · 2007
We study the behavior of the classical A ∗ search algorithm when coupled with a heuristic that provides estimates, accurate to within a small multiplicative factor, of the distance to a solution. We prove general upper bounds on the complexity of A ∗ search, for both admissible and unconstrained heuristic functions, that depend only on the distribution of solution objective values. We go on to provide nearly matching lower bounds that are attained even by non-adversarially chosen solution sets induced by a simple stochastic model.