EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A new modification to the A* path-finding algorithm to improve its space and time performance

Aaron Rasheed Rababaah

Computer and Telecommunication Engineering · 2024

DOI: 10.54517/cte2504 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Computer and Telecommunication Engineering, 2024. Verfasst von Aaron Rasheed Rababaah. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We propose a new modification to the A* algorithm named AA* that significantly improves space and time complexities. In AA*’s forward pass, the node sets (open and closed) are not used, and only the local node neighborhood is saved to take the next move decision. AA* needs a backward pass to bridge and correct gaps and bad decisions made in the forward pass. The work of the backward pass is far less than that of the forward pass, as most of the task has been done. It is shown via empirical experimental work that our proposed AA* algorithm is superior to the classical A* algorithm in the typical three metrics: running time, number of probed nodes, and length of path. Furthermore, our experimental work showed that AA* is suboptimal in terms of length of path compared to the original Dijkstra’s algorithm with an accuracy of 96.95%.

Zitieren

APA

Rababaah, A. R. (2024). A new modification to the A* path-finding algorithm to improve its space and time performance. Computer and Telecommunication Engineering. https://doi.org/10.54517/cte2504

Vancouver

Rababaah AR. A new modification to the A* path-finding algorithm to improve its space and time performance. Computer and Telecommunication Engineering. 2024. doi:10.54517/cte2504

BibTeX
@article{Rababaah2024,
  author = {Rababaah, Aaron Rasheed},
  title = {A new modification to the A* path-finding algorithm to improve its space and time performance},
  journal = {Computer and Telecommunication Engineering},
  year = {2024},
  doi = {10.54517/cte2504}
}
Kostenlos starten →