The Analysis of Efficiency Dependence of the Shortest Path Finding Algorithms A* and HPA* on the Grid Size
2012
Imants Zarembo, Oleg Uzhga-Rebrov

Many pathfinding problems in real-world applications require real-time computation of the shortest path between two points in a grid-based environment. It is not a trivial task. While some shortest path finding algorithms may perform admissibly in one condition, they may prove inadmissible in other conditions. HPA* pathfinding algorithm is faster and more memory efficient than the A*algorithm in relatively large twodimensional grids, but this advantage may not apply to very small or very large grids. The paper deals with the efficiency of A* and HPA*in two-dimensional grids of different sizes. For the sake of completeness of the analysis, HPA* efficiency is measured taking into consideration the number of hierarchy levels and different cluster sizes. Both algorithms have been implemented and tests conducted. Experimental evidence is proposed to demonstrate the algorithm efficiency in various conditions.


Atslēgas vārdi
A*, HPA*, shortest path problems

Zarembo, I., Uzhga-Rebrov, O. The Analysis of Efficiency Dependence of the Shortest Path Finding Algorithms A* and HPA* on the Grid Size. Information Technology and Management Science. Nr.15, 2012, 26.-31.lpp. ISSN 2255-9086. e-ISSN 2255-9094.

Publikācijas valoda
English (en)
RTU Zinātniskā bibliotēka.
E-pasts: uzzinas@rtu.lv; Tālr: +371 28399196