УДК 004.021

Сравнительный анализ алгоритмов поиска оптимального пути

Сравнительный анализ алгоритмов поиска оптимального пути
©Султанова А. Б., ORCID: 0000-0003-3230-6349, кан. тех. наук, Азербайджанский государственный университет нефти и промышленности, Институт систем управления НАН Азербайджана, г. Баку, Азербайджан, saxira@mail.ru

Аннотация. В данной статье рассмотрены широко используемые алгоритмы поиска оптимальных путей. В настоящее время существует довольно широкий список алгоритмов поиска кратчайшего пути, которые активно применяются в мобильной робототехнике для поиска оптимального маршрута. Предлагается двухуровневая система, осуществляющая планирование движения. Произведен сравнительный анализ различных методов поиска пути: их длины, сложности, числа точек поворота. Целью статьи является исследование и сравнительный анализ алгоритмов из области искусственного интеллекта для поиска кратчайшего пути в лабиринте и шестиугольная сетке. Изучаемые алгоритмы: A* (звезда), алгоритм Дейкстры, алгоритм BFS (Breadth first search), DFS (Depth First Search) и Greedy. Алгоритмы сравниваются по двум критериям: длина найденного пути и время нахождения пути. Результаты, представленные аналитически и графически, показывают применение пять алгоритмов для лабиринтов с различным размером и количеством препятствий.

Ключевые слова: интеллектуальный робот, интеллектуальный интерфейс, система управления поведением, неопределенные среды, поиск пути, алгоритм Дейкстры, алгоритм A*, алгоритм BFS, алгоритм DFS, алгоритм Greedy.

Comparative Analysis of Optimal Path Search Algorithms
©Sultanova A., ORCID: 0000-0003-3230-6349, Ph.D., Azerbaijan State University of Oil and Industry, Institute of Control Systems of Azerbaijan NAS, Baku, Azerbaijan, saxira@mail.ru

Abstract. This article discusses widely used algorithms for finding optimal paths. Currently, there is a fairly wide list of algorithms for the problem of finding the shortest path, and is actively used in mobile robotics to find the optimal route. The article offers a two-level system that performs traffic planning. Comparative analysis of various search methods was carried out: their length, complexity, and a number of turning points. The purpose of the article is to study and compare algorithms from the field of artificial intelligence for finding the shortest path in a maze and a hexagonal grid. Algorithms under study: A* (star), Dijkstra algorithm, BFS, DFS, and Greedy algorithm. Algorithms are compared based on two criteria: the length of the found path and the time it takes to find the path. The results, presented analytically and graphically, show the application of five algorithms for mazes with different size and number of obstacles.

Keywords: intelligent robot, intelligent interface, behavior management system, undefined environments, path search, A* algorithm, Dijkstra algorithm, BFS algorithm, DFS algorithm, algorithm Greedy.

Ссылка для цитирования:

Султанова А. Б. Сравнительный анализ алгоритмов поиска оптимального пути // Бюллетень науки и практики. 2020. Т. 6. №12. С. 248-255. https://doi.org/10.33619/2414-2948/61/25

Cite as (APA):

Sultanova, A. (2020). Comparative Analysis of Optimal Path Search Algorithms. Bulletin of Science and Practice, 6(12), 248-255. (in Russian). https://doi.org/10.33619/2414-2948/61/25