Кузьмин Дмитрий Владимирович, кандидат технических наук, доцент, доцент кафедры «Логистика и управление транспортными системами»,
127994, г. Москва, ул. Образцова 9/9.
Dmitry V. Kuzmin, Candidate of Engineering, Associate Professor, Senior Lecturer, Department of Logistics and Transportation System Management,
9/9, Obraztsova st., Moscow, 127994.
Цель. Рассмотреть вопрос применимости алгоритма поиска пути в ширину для решения задач пространственного развития линейных объектов наземной транспортной инфраструктуры. Методы. В статье применяется алгоритм поиска пути в графе – Поиск в ширину (Breadth-First Search, BFS), широко используемый для различных прикладных задач теории графов, в том числе трассирования и планирования пути. С данным алгоритмом проведен ряд простых экспериментов с целью определения количественных показателей его асимптотической сложности, т.е. количества выполняемых операций и времени выполнения алгоритма. Серия экспериментов имеет различную конфигурацию, определяемую направленностью поиска (однонаправленный и двунаправленны) и способом прохода ячеек (прямой и смешанный). Выводы. Эксперименты с различной реализацией алгоритма показывают, что двунаправленный поиск может существенным образом сократить количество выполняемых операций и время поиска. Так количество операций при двунаправленном поиске меньше в 2,75 раза при прямом и в 2,78 раза при смешанном (прямом и диагональном) проходе ячеек. Более того, сделан вывод, что применение двунаправленной реализации алгоритма имеет свою область эффективного использования. Во-первых, двунаправленный поиск эффективен в графах с высокой степень ветвления. Сокращение количества операций при двунаправленном поиске в условиях лабиринта составляет 57,07%, а сокращение времени при этой же конфигурации эксперимента 76,92%, по сравнению с однонаправленной реализацией поиска. В среде, представляющей собой коридор и, следовательно, характеризующейся слабым ветвлением, разница в количестве выполняемых операций между двунаправленным и однонаправленным поиском составила 1,06%, а время выполнения осталось неизменным. Во-вторых, эффективность алгоритма существенно снижается при сложной структуре графа. В-третьих, для использования такой реализации необходимо иметь четкое понимание, что путь между стартовым и целевым узлом существует.
Aim. To examine the applicability of the breadth-first path searching algorithm for spatial development of linear land transportation infrastructure facilities. Methods. The paper uses Breadth-First Searching, a graph path searching algorithm that is widely used as part of various graph theory applications, including path tracing and path planning. A number of simple experiments were carried out with this algorithm in order to determine the quantitative indicators of its asymptotic complexity, i.e., the number of performed operations and the algorithm execution time. The series of experiments has a different structure that is defined by the search direction (unidirectional and bidirectional) and the method of cell scanning (direct and mixed). Conclusion. Experiments involving various implementations of the algorithm show that bidirectional search can significantly reduce the number of performed operations and the search time. Thus, the number of operations for bidirectional search is 2.75 times less for direct and 2.78 times less for mixed (direct and diagonal) cell scanning. Moreover, it is concluded that the bidirectional implementation of the algorithm has its own scope of efficient use. First, bidirectional search is effective in highly-branched graphs. The number of operations for bidirectional maze search decreases 57.07%, while the time of the same experiment decreases 76.92% as compared to the unidirectional search. In a corridor environment that, by definition, has weak branching, the difference in the number of performed operations between bidirectional and unidirectional search was 1.06%, while the execution time remained the same. Secondly, the efficiency of the algorithm is significantly reduced when the graph structure is complex. Thirdly, using this implementation requires confidence in the fact that a path between the starting and target nodes exists.
The authors declare that there are no conflicts of interest present.