Remarks on the A** algorithm
Abstract
The A** algorithm is a famous heuristic path-finding algorithm. In this paper its different definitions will be analyzed firstly. Then its memory complexity is going to be investigated. On the one hand, the well-known concept of better-information will be extended to compare the different heuristics in the A** algorithm. On the other hand, a new proof will be given to show that there is no deterministic graph-search algorithm having better memory complexity than A**∗. At last the time complexity of A** will be discussed.
DOI: https://doi.org/10.1515/ausi-2015-0003 | Journal eISSN: 2066-7760
Language: English
Page range: 190 - 205
Submitted on: Oct 7, 2014
Published on: Jan 27, 2015
Published by: Sapientia Hungarian University of Transylvania
In partnership with: Paradigm Publishing Services
Publication frequency: 2 times per year
Keywords:
Related subjects:
© 2015 Tibor Gregorics, published by Sapientia Hungarian University of Transylvania
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.