Как навигатор объезжает пробки: алгоритмы на графах
Навигатор за долю секунды перебирает миллионы вариантов проезда и выдаёт лучший — да ещё и с учётом пробок прямо сейчас. Разбираем, как обычная карта города превращается в граф и почему алгоритм Дейкстры лежит в основе этой магии.
Ты вбиваешь адрес, тыкаешь «Поехали» — и через секунду на экране уже горит синяя линия маршрута, аккуратно обходящая красное пятно пробки. А ведь между тобой и пунктом назначения миллионы возможных путей. Как навигатор успевает перебрать их все и выбрать лучший быстрее, чем ты пристегнёшь ремень?
Город — это граф
Первое, что делает навигатор, — превращает карту в то, что математики называют графом. Звучит страшно, но идея простая. Граф — это набор точек (их зовут вершинами) и линий между ними (их зовут рёбрами). Перекрёстки и развязки становятся вершинами, а отрезки дорог между ними — рёбрами.
Представь схему метро. Станции — это вершины, перегоны между ними — рёбра. Тебе ведь не важно, как именно изгибается тоннель под землёй: важно лишь, какая станция с какой соединена и сколько ехать. Навигатор смотрит на город ровно так же — как на сеть соединённых точек.
Но у дорог есть нюанс, которого нет у простой схемы: проехать по улице в одну сторону можно, а в обратную — нет. Поэтому навигатор использует ориентированный граф, где у рёбер есть направление. Стрелка ведёт туда, куда реально разрешено ехать.
Главный секрет — это вес
Если бы навигатору нужен был просто путь «из точки А в точку Б», задача была бы скучной: подойдёт любая дорога. Но нам нужен лучший путь. И вот тут появляется ключевая деталь — вес ребра.
Каждому отрезку дороги приписывается число — его «стоимость». Это может быть длина в метрах, но гораздо чаще — время в пути. Узкий переулок в 200 метров со светофором и пешеходным переходом может «весить» больше, чем километр свободной магистрали. Навигатор ищет не самый короткий маршрут по карте, а самый дешёвый по сумме весов.
Граф — это не про расстояние на карте. Это про стоимость пути. Поменяй смысл весов — и тот же алгоритм найдёт то самый быстрый, то самый дешёвый по бензину, то самый короткий маршрут.
Именно через вес в игру вступают пробки. Когда на улице затор, навигатор просто увеличивает вес соответствующего ребра: «по этой дороге теперь ехать не 2 минуты, а 12». И при следующем пересчёте маршрут сам собой утекает в обход — не потому что кто-то запретил ехать прямо, а потому что прямой путь стал слишком «дорогим».
Алгоритм Дейкстры: волна по городу
Как же из этого графа достать лучший путь? Самый знаменитый способ придумал нидерландский программист Эдсгер Дейкстра ещё в 1956 году — и его алгоритм работает в навигаторах до сих пор.
Вообрази, что ты бросил камень в пруд в точке старта. От него во все стороны расходится волна. Алгоритм Дейкстры — это такая же волна, только умная. Она расползается по графу от твоего текущего места, и для каждого перекрёстка запоминает: за какое наименьшее время сюда вообще можно добраться.
Работает это так, шаг за шагом:
- В начале известно одно: до точки старта ехать ноль секунд. До всех остальных — пока «бесконечность», то есть неизвестно.
- Алгоритм выбирает ближайший по времени ещё не обработанный перекрёсток и смотрит на всех его соседей.
- Для каждого соседа он проверяет: «А не быстрее ли добраться до тебя через меня?» Если да — обновляет рекорд.
- Перекрёсток помечается обработанным, и волна катится дальше — снова к ближайшему.
Гениальность в одной детали: волна всегда первой добирается до точки именно по кратчайшему пути. Поэтому как только она дошла до твоего пункта назначения, можно останавливаться — лучший маршрут найден, искать дальше бессмысленно.
A*: алгоритм с интуицией
У честной волны Дейкстры есть слабость: она расходится во все стороны одинаково. Если тебе нужно проехать через весь город с запада на восток, алгоритм добросовестно изучит и кучу улиц на севере, и на юге — хотя интуитивно ясно, что ехать надо примерно туда, к цели.
Чтобы не тратить силы впустую, придумали алгоритм A* (читается «А звёздочка»). Это усовершенствованная Дейкстра, у которой добавили интуицию — её называют эвристикой. К честной стоимости «сколько уже проехал» A* добавляет прикидку «сколько примерно осталось до цели по прямой».
Это как искать выход из тёмного леса: можно методично прочёсывать всё подряд, а можно идти преимущественно туда, откуда тянет светом. A* не гарантированно бежит к цели напролом, но сильно реже отвлекается на заведомо тупиковые направления. В итоге он находит тот же кратчайший путь, но проверяет в разы меньше перекрёстков — а значит, работает быстрее.
Почему маршрут вдруг меняется в пути
Теперь самое интересное про пробки. Дорожная ситуация живая: затор может рассосаться, а на свободной трассе может случиться авария. Поэтому навигатору мало один раз построить маршрут — он держит руку на пульсе.
Данные о скорости потока приходят от миллионов других машин с тем же приложением: каждая, сама того не зная, как сенсор сообщает, с какой скоростью движется. Из этого сервис в реальном времени пересчитывает веса рёбер по всему городу. Если на твоём пути впереди вырос затор, вес тех рёбер подскакивает — и алгоритм заново прикидывает: а нет ли теперь обходного пути, который суммарно дешевле?
Если есть — навигатор спокойно говорит «перестраиваю маршрут». Под капотом он просто ещё раз прогнал ту же Дейкстру или A* по обновлённому графу. Так что в следующий раз, когда навигатор уведёт тебя в неожиданный объезд, ты будешь знать: это не каприз. Это математическая волна, которая только что пробежала по графу твоего города и нашла путь подешевле.