On the Value of Good Advice: The Complexity of A* Search with Accurate Heuristics
Abstract
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.
Cite
Text
Dinh et al. "On the Value of Good Advice: The Complexity of A* Search with Accurate Heuristics." AAAI Conference on Artificial Intelligence, 2007.Markdown
[Dinh et al. "On the Value of Good Advice: The Complexity of A* Search with Accurate Heuristics." AAAI Conference on Artificial Intelligence, 2007.](https://mlanthology.org/aaai/2007/dinh2007aaai-value/)BibTeX
@inproceedings{dinh2007aaai-value,
title = {{On the Value of Good Advice: The Complexity of A* Search with Accurate Heuristics}},
author = {Dinh, Hang T. and Russell, Alexander and Su, Yuan},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2007},
pages = {1140-1145},
url = {https://mlanthology.org/aaai/2007/dinh2007aaai-value/}
}