A Result on the Computational Complexity of Heuristic Estimates for the A* Algorithm
Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Planning and Search. Pages 777-778.
Abstract
The performance of a new heuristic search algorithm is analyzed in this paper . The algorithm uses a formal representation {semantic representation) that contains enough information to compute the heuristic evaluation function h(n), as defined in the context of A*, wi thout requiring a human expert to provide it. The heuristic is computed by solving less constrained subproblems {auxiliary problems) of the given problem. The new algorithm is shown to be less efficient than the Dijkstra algorithm, according to the complexity measure "number of node expansions." This proves that it is not efficient to compute heuristics for A* by solving auxiliary problems with backtracking.
@inproceedings{ijcai1983p188,
title = {A Result on the Computational Complexity of Heuristic Estimates for the A* Algorithm},
author = {Valtorta, Marco},
booktitle = {Proceedings of the Eighth International Joint Conference on
Artificial Intelligence, {IJCAI-83}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Alan Bundy},
pages = {777--778},
year = {1983},
note = {Planning and Search},
url = {https://ijcai.org/proceedings/1983/188},
}
TY - CPAPER TI - A Result on the Computational Complexity of Heuristic Estimates for the A* Algorithm AU - Valtorta, Marco T2 - Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83 PB - International Joint Conferences on Artificial Intelligence PY - 1983 SP - 777 EP - 778 UR - https://ijcai.org/proceedings/1983/188 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
