Towards Finding Optimal Solutions with Non-Admissible Heuristics: A New Technique
Abstract
A problem with A * is that it fails to guarantee optimal solutions when its heuristic, h, overestimates. Since optimal solutions are often desired and an underestimating h is not always available, we seek to remedy this. From a nonadmissible h an admissible one is generated using h's statistical properties. The new heuristic, hm, is obtained by inverting h with respect to its own least upper bound function. The set of nodes expanded when A * uses g + hm as an evaluator is compared with the set of nodes expanded using other approaches which have been suggested in the literature. A considerable potential savings in node expansion when using hm is indicated. In 8-puzzle experiments A * using g +hm expands one fifth as many nodes as does the best alternative approach. 1.
Cite
Text
Davis et al. "Towards Finding Optimal Solutions with Non-Admissible Heuristics: A New Technique." International Joint Conference on Artificial Intelligence, 1989.Markdown
[Davis et al. "Towards Finding Optimal Solutions with Non-Admissible Heuristics: A New Technique." International Joint Conference on Artificial Intelligence, 1989.](https://mlanthology.org/ijcai/1989/davis1989ijcai-finding/)BibTeX
@inproceedings{davis1989ijcai-finding,
title = {{Towards Finding Optimal Solutions with Non-Admissible Heuristics: A New Technique}},
author = {Davis, Henry W. and Bramanti-Gregor, Anna and Chen, Xiaoteng},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1989},
pages = {303-308},
url = {https://mlanthology.org/ijcai/1989/davis1989ijcai-finding/}
}