Acta Universitatis Sapientiae: Informatica (Dec 2014)

Remarks on the A** algorithm

  • Gregorics Tibor

DOI
https://doi.org/10.1515/ausi-2015-0003
Journal volume & issue
Vol. 6, no. 2
pp. 190 – 205

Abstract

Read online

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.

Keywords