High-Performance Aast Search Using Rapidly Growing Heuristics
Proceedings of the Twelfth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 198-202.
Abstract
In high-performance A* searching to solve satisficing problems, there is a critical need to design heuristics which cause low time-complexity. In order for humans or machines to do this effectively, there must be an understanding of the domainindependent properties that such heuristics have . We show that, contrary to common belief, accuracy is not critical; the key issue is whether or not heuristic values are concentrated closely near a rapidly growing "central function." As an application, we show that, by "multiplying" heuristics, it is possible to reduce exponential average timecomplexity to polynomial. This is contrary to conclusions drawn from previous studies. Experimental and theoretical examples are given.
@inproceedings{ijcai1991p30,
title = {High-Performance Aast Search Using Rapidly Growing Heuristics},
author = {Chenoweth, Stephen V. and Davis, Henry W.},
booktitle = {Proceedings of the Twelfth International Joint Conference on
Artificial Intelligence, {IJCAI-91}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {John Mylopoulos and Ray Reiter},
pages = {198--202},
year = {1991},
month = {8},
note = {Automated Reasoning},
url = {https://ijcai.org/proceedings/1991/30},
}
TY - CPAPER TI - High-Performance Aast Search Using Rapidly Growing Heuristics AU - Chenoweth, Stephen V. AU - Davis, Henry W. T2 - Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, IJCAI-91 PB - International Joint Conferences on Artificial Intelligence PY - 1991 SP - 198 EP - 202 UR - https://ijcai.org/proceedings/1991/30 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
