кандидат технических наук;
candidate of technical sciences;
Задача. Рассмотрен вопрос применимости алгоритма A* для решения задач поиска пути в контексте пространственного развития линейных объектов наземной транспортной инфраструктуры. Цель исследования. Определение наиболее предпочтительной конфигурации алгоритма поиска пути для решения задачи пространственного развития линейной транспортной инфраструктуры. Методы исследования. Алгоритм A*, широко используется для различных прикладных задач теории графов, в том числе трассирования и планирования пути. Новизна работы. С алгоритмом проведен ряд простых экспериментов с целью определения количественных показателей его асимптотической сложности, т.е. количества выполняемых операций и времени выполнения алгоритма. Серия экспериментов имеет различную конфигурацию, определяемую направленностью поиска (однонаправленный и двунаправленны), метрикой поиска (Евклидова метрика, Манхэттенское расстояние, расстояние Чебышева) и способом прохода ячеек (прямой и смешанный). Результаты исследования и выводы. В целом можно заключить, что двунаправленный поиск требует примерно на 19,17% меньше операций чем однонаправленный. Манхэттенская метрика и расстояние Чебышева показывают схожие результаты по длине пути и времени выполнения. Евклидова метрика позволяет найти более короткий путь, но может потребовать больше времени на выполнение.
Problem. The issue of applying A* algorithm for solving pathfinding problems in spatial development of linear objects of land transport infrastructure is considered. Study objective. Determining the most preferred configuration of pathfinding algorithm for solving the problem of spatial development of linear transport infrastructure. Research methods. A* algorithm is widely used for various graph theory applications, including tracing and path planning. The novelty of the work. A number of simple experiments were carried out with the algorithm in order to determine quantitative indicators of its asymptotic complexity, i.e. the number of operations performed and the algorithm time. The set of experiments has a different configuration, determined by the direction of the search (unidirectional and bidirectional), the search metric (Euclidean distance, Manhattan distance, Chebyshev distance) and the method of cell passing (direct and mixed). Research results and conclusions. In general, it can be concluded that bidirectional search requires about 19.17% fewer operations than unidirectional search. Manhattan distance and Chebyshev distance show similar results in terms of path length and execution time. Euclidean distance allows finding a shorter path, but it may take longer to complete.