Back to Search
Start Over
ERA*: Enhanced Relaxed A* algorithm for solving the shortest path problem in regular grid maps.
- Source :
-
Information Sciences . Feb2024, Vol. 657, pN.PAG-N.PAG. 1p. - Publication Year :
- 2024
-
Abstract
- This paper introduces a novel algorithm for solving the point-to-point shortest path problem in a static regular 8-neighbor connectivity (G8) grid. This algorithm can be seen as a generalization of Hadlock algorithm to G8 grids, and is shown to be theoretically equivalent to the relaxed A ⁎ (R A ⁎) algorithm in terms of the provided solution's path length, but with substantial time and memory savings, due to a completely different computation strategy, based on defining a set of lookup matrices. Through an experimental study on grid maps of various types and sizes (1290 runs on 43 maps), it is proven to be 2.25 times faster than R A ⁎ and 17 times faster than the original A ⁎ , in average. Moreover, it is more memory-efficient, since it does not need to store a G score matrix. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRIDS (Cartography)
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 00200255
- Volume :
- 657
- Database :
- Academic Search Index
- Journal :
- Information Sciences
- Publication Type :
- Periodical
- Accession number :
- 174470893
- Full Text :
- https://doi.org/10.1016/j.ins.2023.120000