ДОСЛІДЖЕННЯ ЕФЕКТИВНОСТІ АЛГОРИТМІВ ПОШУКУ МАРШРУТУ НА ЛАБІРИНТАХ ТА ДВОВИМІРНИХ СІТКОВИХ СТРУКТУРАХ
##plugins.themes.bootstrap3.article.sidebar##
##plugins.themes.bootstrap3.article.main##
Анотація
У статті проведено порівняльний аналіз швидкодії алгоритму Дейкстри, алгоритму A*
та алгоритму пошуку точок переходу (Jump Point Search, JPS) на двовимірних сіткових
структурах. Для формування тестових середовищ реалізовано генерацію лабіринтів на основі
алгоритму бінарного дерева та рандомізованого алгоритму Прима, а також побудову мап із
різною щільністю перешкод шляхом модифікації згенерованих структур. Порівняння
алгоритмів здійснювалось за сумарним часом виконання в ході серії з 1000 ітерацій пошуку
між випадково обраними парами точок на сітках розміром 255×255 клітинок. Визначено
залежність ефективності алгоритмів від топології простору та щільності перешкод,
сформульовано рекомендації щодо вибору алгоритму залежно від характеристик середовища.
Отримані результати можуть бути використані під час проєктування навігаційних систем,
ігрових застосунків та робототехнічних комплексів.
##plugins.themes.bootstrap3.article.details##
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Посилання
Severance, C. R. Python for Everybody: Exploring Data Using Python 3. CreateSpace Independent
Publishing Platform, 2016. 244 p.
Miller, B. N., Ranum, D. L., and Anderson, J. Python Programming in Context. Jones & Bartlett Learning,
530 p.
Joshi, P. Artificial Intelligence with Python. Packt Publishing, 2017. 446 p.
Ni, Y.; Zhuo, Q.; Li, N.; Yu, K.; He, M.; Gao, X. Characteristics and Optimization Strategies of A*
Algorithm and Ant Colony Optimization in Global Path Planning Algorithm. Int. J. Pattern Recognit. 2023,
, 2351006.
Wang, P.; Liu, Y.; Yao, W.; Yu, Y. Improved A-star algorithm based on multivariate fusion heuristic
function for autonomous driving path planning. Proc. Inst. Mech. Eng. Part D-J. Automob. Eng. 2022, 237,
-1542.
Zhang, Y.; Li, L.; Lin, H.; Ma, Z.; Zhao, J. Development of Path Planning Approach Using Improved Astar Algorithm in AGV System. J. Internet Technol. 2019, 20, 915–924.
Iram, N.; Amna, K.; Khurshid, A.; Zulfiqar, H. A Path-Planning Performance Comparison of RRT*-AB
with MEA* in a 2-Dimensional Environment. Symmetry 2019, 11, 945.
Liu, L.; Lin, J.; Yao, J.; He, D.; Zheng, J.; Huang, J.; Shi, P. Path Planning for Smart Car Based on Dijkstra
Algorithm and Dynamic Window Approach. Wirel. Commun. Mob. Comput. 2021, 2021, 356–368.
Banerjee, N.; Chakraborty, S.; Raman, V.; Satti, S.R. Space Efficient Linear Time Algorithms for BFS,
DFS and Applications. Theor. Comput. Syst. 2018, 62, 1736–1762.
Lai, W.K.; Shieh, C.S.; Yang, C.P. A D2D Group Communication Scheme Using Bidirectional and
InCremental A-Star Search to Configure Paths. Mathematics 2022, 10, 3321.
Wang, H.; Qi, X.; Lou, S.; Jing, J.; He, H.; Liu, W. An Efficient and Robust Improved A* Algorithm for
Path Planning. Symmetry 2021, 13, 2213.
Chen Yifu, Lu Wei, Ding Haojie. Research on Optimization Strategy of Dijkstra Algorithm // Computer
Technology and Development. – 2006. – Vol. 16, No. 9. – pp. 73-75.
Zhang Yonglong. Optimization of Dijkstra Optimal Path Algorithm // Journal of Nanchang Institute of
Technology. – 2006. – Vol. 25, No. 3. – pp. 30-33.
Using Prim’s Algorithm to Generate Continuous Cave Maps // URL: