On the Value of Good Advice: The Complexity of A* Search with Accurate Heuristics

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


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.