Hang Dinh, Alexander Russell, Yuan Su
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.
Subjects: 15.7 Search; 9.2 Computational Complexity
Submitted: Apr 17, 2007