Использование алгоритма поиска в ширину при решении задач пространственного развития инфраструктуры наземного транспорта

Цель. Рассмотреть вопрос применимости алгоритма поиска пути в ширину для решения задач пространственного развития линейных объектов наземной транспортной инфраструктуры. Методы. В статье применяется алгоритм поиска пути в графе – Поиск в ширину (Breadth-First Search, BFS), широко используемый для различных прикладных задач теории графов, в том числе трассирования и планирования пути. С данным алгоритмом проведен ряд простых экспериментов с целью определения количественных показателей его асимптотической сложности, т.е. количества выполняемых операций и времени выполнения алгоритма. Серия экспериментов имеет различную конфигурацию, определяемую направленностью поиска (однонаправленный и двунаправленны) и способом прохода ячеек (прямой и смешанный). Выводы. Эксперименты с различной реализацией алгоритма показывают, что двунаправленный поиск может существенным образом сократить количество выполняемых операций и время поиска. Так количество операций при двунаправленном поиске меньше в 2,75 раза при прямом и в 2,78 раза при смешанном (прямом и диагональном) проходе ячеек. Более того, сделан вывод, что применение двунаправленной реализации алгоритма имеет свою область эффективного использования. Во-первых, двунаправленный поиск эффективен в графах с высокой степень ветвления. Сокращение количества операций при двунаправленном поиске в условиях лабиринта составляет 57,07%, а сокращение времени при этой же конфигурации эксперимента 76,92%, по сравнению с однонаправленной реализацией поиска. В среде, представляющей собой коридор и, следовательно, характеризующейся слабым ветвлением, разница в количестве выполняемых операций между двунаправленным и однонаправленным поиском составила 1,06%, а время выполнения осталось неизменным. Во-вторых, эффективность алгоритма существенно снижается при сложной структуре графа. В-третьих, для использования такой реализации необходимо иметь четкое понимание, что путь между стартовым и целевым узлом существует.

1. Automatic Pipeline Route Design with Multi-Criteria Evaluation Based on Least-Cost Path Analysis and LineBased Cartographic Simplification: A Case Study of the Mus Project in Turkey. URL: https://www.mdpi.com/22209964/8/4/173 (дата обращения: 23.05.2025).

2. Kang J.Y., Lee B. Optimisation of pipeline route in the presence of obstacles based on a least cost path algorithm and laplacian smoothing // International Journal of Naval Architecture and Ocean Engineering. 2017. Vol. 9.

3. Scaparra M.P., Church R.L., Medrano F.A. Corridor location: the multi-gateway shortest path model // Journal of Geographical Systems. 2014. Vol. 16. No. 3. Pp. 287-309.

4. Yu C., Lee J., Munro-Stasiuk M. Extensions to leastcost path algorithms for roadway planning // International Journal of Geographical Information Science – GIS. 2003. Vol. 17.

5. Jamali A.A., Esmailian A., Mokhtarisabet S. et al. Path selection by topographic analysis: vector re-classification versus raster fuzzification as spatial multi-criteria using cost-path // Spatial Information Research. 2023. Т. 31.

6. Stefano B., Davide G., Francesco O. Routing of power lines through least-cost path analysis and multicriteria evaluation to minimise environmental impacts // Environmental Impact Assessment Review. 2011. Vol. 31. No. 3. Pp. 234-239.

7. Monteiro C., Ramírez-Rosado I., Miranda V. et al. GIS Spatial Analysis Applied to Electric Line Routing Optimization // Power Delivery, IEEE Transactions on. 2005. Vol. 20. Pp. 934-942.

8. Antikainen H. Comparison of Different Strategies for Determining Raster-Based Least-Cost Paths with a Minimum Amount of Distortion // Transactions in GIS. 2013. Vol. 17.

9. C. Dana T. Propagating radial waves of travel cost in a grid // International Journal of Geographical Information Science. 2010. Vol. 24(9). Pp. 1391-1413.

10. Ahuja R., Mehlhorn K., Orlin J. et al. Faster Algorithms for the Shortest Path Problem // J. ACM. 1990. Vol. 37. Pp. 213-223.

11. Wayahdi M., Ginting S., Syahputra D. Greedy, A-Star, and Dijkstra’s Algorithms in Finding Shortest Path // International Journal of Advances in Data and Information Systems. 2021. Vol. 2. Pp. 45-52.

12. Moore E.F. The Shortest Path through a Maze // In Proc. International Symposium on the Theory of Switching, Part II. Harvard University Press, 1959.

13. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik. 1959. Vol. 1. No. 1. Pp. 269-271.

14. Cormen T.H., Leiserson C.E., Rivest R.L. et al. Introduction to Algorithms. MIT Press and McGraw-Hill, 2001. 1216 p.

15. Sedgewick R., Wayne K. Algorithms. AddisonWesley Professional, 2011. 971 p.