Емельянов Сергей Геннадьевич, доктор технических наук, профессор, ректор
ул. 50 лет Октября, д. 94, г. Курск 305040
Sergei G. Emelianov, Dr. of Sci. (Engineering), Professor, Rector
Kursk
Бобырь Максим Владимирович, доктор технических наук, профессор кафедры вычислительной техники
ул. 50 лет Октября, д. 94, г. Курск 305040
Maxim V. Bobyr, Dr. of Sci. (Engineering), Associate Professor of the Computer Engineering Department
Kursk
Крюков Александр Георгиевич, аспирант
ул. 50 лет Октября, д. 94, г. Курск 305040
Aleksander G. Kryukov, Post-Graduate Student
Kursk
Цель исследования. Представленное в данной статье исследование нацелено на повышение быстродействия поиска пути для маршрута передвижения роботов. Научной новизной является полученная закономерность отношения времени и размеров поля.
Методы. Для нахождения пути в лабиринте использовались алгоритмы поиска в глубину и поиска в ширину, основой которых является цикличное прохождение смежных не посещенных ранее вершин графа. Быстродействие оценивается в скорости выполнения программного кода на подготовленных образцах. Научная новизна была получена за счет исследования влияния размеров карты на быстродействие алгоритмов поиска в глубину и ширину.
Результаты. Разработана программная реализация алгоритмов поиска в ширину и в глубину. В статье подробнее представлено описание алгоритма поиска в ширину в виде псевдо- и программного кодов, которые основываются на цикле while, где осуществляется обработка очереди проверяемых вершин графа. На основе оценки быстродействия найденного пути сделан вывод, что поиск в ширину не является быстрейшим. На основе оценки влияния различных факторов на скорость работы алгоритма сделан вывод, что увеличение размеров поля, уменьшение количества препятствий и расстояния между стартовой и финальной точками увеличивает время выполнения алгоритма.
Заключение. Был представлен алгоритм поиска в ширину и его программная реализация. В ходе экспериментальных исследований было установлено, что данный алгоритм по времени не является быстрейшим, но во всех тестах находил кратчайший путь. Также была получена закономерность ta = f(w, h) для подготовленных образцов искомого поля, которая выражается в зависимости времени выполнения алгоритма от длины и ширины поля. И можем заключить, что он применим для поиска пути передвижения роботов так как всегда находит кратчайший путь.
Purpose of research. The research presented in this article is aimed at improving the speed of finding a path for the movement route of robots. The scientific novelty is the obtained correlation of time and field size.
Methods. To find the path in the maze, the depth-first search and breadth-first search algorithms were used, the basis of which is the cyclic processing of adjacent previously unvisited graph vertices. Performance is estimated in terms of the speed of program code execution on prepared samples. Scientific novelty was obtained by studying the influence of map sizes on the performance of depth-first and breadth-first search algorithms.
Results. A software implementation of breadth-first and depth-first search algorithms has been developed. The article provides a more detailed description of the breadth-first search algorithm in the form of pseudo and program codes, which are based on the while loop, where the queue of checked graph vertices is processed. Based on the evaluation of the speed of the found path, it was concluded that the breadth-first search is not the fastest. Based on the assessment of the influence of various factors on the speed of the algorithm, it was concluded that an increase in the size of the field, a decrease in the number of obstacles and a distance between the starting and final points increases the execution time of the algorithm.
Conclusion. The breadth-first search algorithm and its software implementation were presented. In the course of experimental studies, it was found that this algorithm is not the fastest in time, but in all tests, it found the shortest path. The correlation ta = f(w, h) was also obtained for the prepared samples of the desired field, which is expressed as the dependence of the algorithm execution time on the length and width of the field. And we can conclude that it is applicable for finding the movement path of robots, since it always finds the shortest path.
The authors declare that there are no conflicts of interest present.