Как находят кратчайший маршрут для курьера

Курьер забирает у тебя заказ и едет дальше — а в этот момент его телефон уже знает, к кому ехать следующим и какой дорогой. Кто решил, что именно так быстрее? Никакой живой диспетчер не успел бы перебрать все варианты. За кулисами работает математика, придуманная задолго до появления смартфонов.

Город — это граф

Чтобы компьютер мог искать маршрут, реальный город нужно превратить в то, что он понимает. И тут используется простая, но мощная идея — граф. Это всего лишь набор точек (их называют вершинами) и линий между ними (их называют рёбрами).

Перекрёстки, дома, пункты выдачи — это вершины. Улицы, которые их соединяют, — это рёбра. И у каждого ребра есть вес: число, которое говорит, насколько дорого по нему ехать. Весом может быть длина улицы в метрах, время в пути с учётом пробок или даже количество светофоров.

Кратчайший маршрут — это не обязательно самый короткий по расстоянию. Чаще это путь с наименьшей суммой весов: иногда быстрее объехать пробку по длинной дороге, чем стоять на короткой.

Как только город стал графом, задача "куда ехать" превращается в чёткий математический вопрос: найти путь между двумя вершинами, у которого сумма весов рёбер минимальна.

Алгоритм, который растекается как вода

Самый знаменитый способ найти такой путь придумал нидерландский учёный Эдсгер Дейкстра ещё в 1956 году — за полчаса, сидя в кафе, без ручки и бумаги. Его алгоритм носит его имя и до сих пор работает внутри навигаторов.

Представь, что ты налил воду в точку старта на карте, и она растекается по всем дорогам с одинаковой скоростью. Сначала вода доберётся до ближайших перекрёстков, потом до тех, что подальше, и так далее. Как только вода дошла до нужного адреса — путь, по которому она бежала, и есть кратчайший. Алгоритм Дейкстры делает ровно это, только вместо воды он по шагам подсчитывает расстояние до каждой вершины.

Работает он так:

• в начале расстояние до старта равно нулю, а до всех остальных точек — "бесконечность" (мы пока не знаем дороги);
• алгоритм каждый раз берёт ещё не обработанную точку с наименьшим известным расстоянием;
• смотрит на её соседей и проверяет: а нельзя ли добраться до них короче, если идти через текущую точку?
• если нашёлся путь покороче — он его запоминает и движется дальше.

Гениальность в том, что точку, до которой расстояние уже точно минимально, алгоритм больше никогда не трогает. Поэтому он не перебирает все маршруты подряд, а уверенно идёт к ответу.

А если адресов не один, а десять?

Найти путь из точки А в точку Б — это полдела. Настоящая головная боль начинается, когда у курьера десять заказов и нужно решить, в каком порядке их объехать, чтобы общий путь был минимальным.

Эта задача такая знаменитая, что у неё есть собственное имя — задача коммивояжёра (по-старому так называли странствующего торговца, который объезжал города и продавал товар). И вот тут начинается самое интересное.

Казалось бы, можно просто перебрать все варианты порядка и выбрать лучший. Но посчитай сам: для 5 адресов вариантов 120, для 10 — уже больше трёх миллионов, а для 20 адресов число вариантов превышает количество секунд, прошедших с Большого взрыва. Даже самый мощный суперкомпьютер захлебнётся.

Это пример задачи, для которой никто в мире пока не знает быстрого способа найти идеальный ответ. И, возможно, его и не существует.

Хитрость: идеал не нужен

Раз идеальное решение искать слишком долго, инженеры пошли на умный компромисс. Сервисы доставки используют приближённые алгоритмы — они находят не самый-самый лучший маршрут, а очень хороший, который отличается от идеала на считаные проценты, зато считается за доли секунды.

Один из простых приёмов — жадный алгоритм: едем всегда к ближайшему ещё не посещённому адресу. Это не всегда даёт лучший результат, но работает мгновенно и обычно неплохо. А поверх него запускают улучшайзеры, которые берут готовый маршрут и пробуют менять местами пары точек: вдруг станет короче?

В реальных сервисах вроде доставки еды всё ещё сложнее. Алгоритм учитывает пробки в реальном времени, разрешённые повороты, односторонние улицы, время приготовления заказа в ресторане и даже то, что один курьер может везти сразу несколько заказов в одну сторону. Это уже не школьная задачка, а целая инженерная система — но в её сердце по-прежнему бьются те же графы и тот самый алгоритм, придуманный в кафе за полчаса.

Так что в следующий раз, когда увидишь на экране, как точка курьера ползёт к твоему дому, знай: за этой линией стоит математика, которая каждую секунду решает задачу, над которой бьются лучшие умы планеты.