<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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.</p></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.

Remarks on the A** algorithm

Eötvös Loránd University, Faculty of Informatics Budapest

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Remarks on the A** algorithm"}

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...

Remarks on the A** algorithm

Data publikacji: 27 sty 2015

Zakres stron: 190 - 205

Otrzymano: 07 paź 2014

DOI: https://doi.org/10.1515/ausi-2015-0003

© 2015

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.