Поиск пути: алгоритмы и методы¶
Поиск пути — это задача нахождения последовательности рёбер (или вершин) в графе, соединяющей исходную и целевую точки, обычно при условии минимальной стоимости, длины или времени прохождения. Задача относится к классу комбинаторных оптимизационных задач и решается множеством алгоритмов, применяемых в навигации, робототехнике, транспортном планировании, компьютерных играх и сетевых протоколах.
¶Математическая постановка
Путь в графе — это последовательность рёбер, где конец каждого ребра совпадает с началом следующего. Если граф ориентированный, направление рёбер учитывается; если неориентированный, движение возможно в обе стороны. Задача обычно формулируется как минимизация функции стоимости: суммы весов пройденных рёбер. Вес может отражать расстояние, время, цену проезда или иной показатель.
Выделяют несколько классических вариантов задачи:
- Кратчайший путь — минимизация суммарного веса.
- Наименьшее число рёбер — частный случай, когда все веса равны единице.
- Задача коммивояжёра — поиск кратчайшего маршрута, проходящего через все заданные вершины.
- Поиск пути в среде с препятствиями — для роботов и игровых персонажей.
¶Основные алгоритмы
¶Алгоритм Дейкстры
Алгоритм Эдсгера Дейкстры (1956) находит кратчайший путь от одной вершины ко всем остальным в графе с неотрицательными весами. Принцип работы: последовательное «раскрытие» вершин с наименьшим известным расстоянием от источника. Сложность реализации с использованием приоритетной очереди — O((V + E) log V), где V — число вершин, E — число рёбер.
Алгоритм лежит в основе многих навигационных систем и сетевых протоколов (например, OSPF).
¶Алгоритм Беллмана — Форда
Обобщение алгоритма Дейкстры, допускающее отрицательные веса рёбер (но не отрицательные циклы). Применяется для вычисления кратчайших путей в графах с отрицательными весами, например при моделировании финансовых операций. Сложность — O(V·E), что делает его медленнее Дейкстры на плотных графах.
¶Алгоритм A*
Эвристический алгоритм, широко используемый в робототехнике и компьютерных играх. Расширяет поиск в направлении, наиболее близком к цели, используя эвристическую функцию оценки стоимости оставшегося пути. Если эвистическая функция не переоценивает стоимость (является допустимой), алгоритм гарантирует нахождение кратчайшего пути. A* работает быстрее Дейкстры на больших графах с известной геометрией.
¶Алгоритм Ли
Алгоритм волнового распространения (Ли, 1959) находит кратчайший путь в сетке, распространяя «волну» от стартовой точки во все допустимые направления. Прост в реализации, часто используется в задачах прохождения лабиринтов и планирования траекторий роботов.
¶Алгоритм Флойда — Уоршелла
Находит кратчайшие пути между всеми парами вершин графа. Сложность — O(V³), поэтому применяется на графах с небольшим числом вершин. Полезен для предварительного вычисления таблиц расстояний.
¶Поиск пути в пространствах с препятствиями
Для роботов и игровых персонажей пространство часто дискретизируется в виде сетки или полигонов. Классические подходы:
- Дискретизация пространства — разбиение области на ячейки, поиск пути в получившемся графе.
- Вороной диаграмма — построение графа по свободным коридорам между препятствиями.
- Пробные пути (RRT, PRM) — вероятностные алгоритмы, эффективные в пространствах с высокой размерностью.
¶Транспортное планирование
В логистике и городской навигации поиск пути решается на графах с миллионами рёбер. Коммерческие навигаторы используют гибридные алгоритмы: предварительное сжатие графа (сокращение вершин с одним входом и одним выходом), иерархические схемы (разбиение на регионы) и сокращение поискового пространства с помощью эвристик. Типичные системы — Яндекс.Навигатор, Google Maps, 2ГИС — учитывают не только расстояние, но и текущую пробочную обстановку, что превращает задачу в динамическую.
¶Применение
| Область | Задача |
|---|---|
| Навигация | Маршрутизация транспорта и пешеходов |
| Робототехника | Планирование траекторий манипуляторов и мобильных роботов |
| Компьютерные игры | ИИ-персонажи, поиск пути в лабиринтах |
| Телекоммуникации | Маршрутизация пакетов (BGP, OSPF) |
| Логистика | Оптимизация доставки, задача коммивояжёра |
| Биоинформатика | Выравнивание последовательностей (алгоритм Вагнера — Фишера) |
¶Сложность задачи
Поиск одного кратчайшего пути в графе с неотрицательными весами решается за полиномиальное время. Задачи, требующие оптимизации по всем парам вершин или прохождения через множество точек (коммивояжёр), относятся к классу NP-трудных задач, для которых полиномиальных алгоритмов неизвестно; на практике применяются эвристические и аппроксимационные методы.
Источники:
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ»
- Кнут Д. «Искусство программирования», том 4
- Сборник статей по графовым алгоритмам (Dijkstra E. W., 1959; Lee C. Y., 1959; Hart P. et al., 1968)
