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

Читать онлайн

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

Ключевые фразы: алгоритмы поиска пути, ТРАССИРОВАНИЕ, пространственное развитие транспортной инфраструктуры, транспортные системы, теория графов
Автор (ы): Кузьмин Дмитрий Владимирович
Журнал: НАДЕЖНОСТЬ

Предпросмотр статьи

Идентификаторы и классификаторы

SCI
Физика
УДК
656.022. Служба движения. Линии. Маршруты. Трассы
Префикс DOI
0.21683/1729-2646-2025-25-3-60-67
Для цитирования:
КУЗЬМИН Д. В. ИСПОЛЬЗОВАНИЕ АЛГОРИТМА ПОИСКА В ШИРИНУ ПРИ РЕШЕНИИ ЗАДАЧ ПРОСТРАНСТВЕННОГО РАЗВИТИЯ ИНФРАСТРУКТУРЫ НАЗЕМНОГО ТРАНСПОРТА // НАДЕЖНОСТЬ. 2025. ТОМ 25, № 3
Текстовый фрагмент статьи