Навигатор

Прошлая глава кончилась тем, что провода проложены, а ездить мы не умеем. Ещё раньше, в главе 19, та же стена встала в метро: волна из Сокольников в Москва-Сити выбрала Большую кольцевую — десять рёбер вместо тринадцати, но по нашей оценке 33 минуты против 26 через центр. Обход в ширину считает рёбра, а пассажир считает минуты. Соберём навигатор, который считает минуты, и будем испытывать его поездками: каждая ломает текущую версию и заставляет придумать следующую, а последняя ответит на третий большой вопрос курса: как навигатор за секунду находит кратчайший путь среди миллионов дорог.

Поездка первая: Сокольники — Москва-Сити

Граф метро тот же, что в главе 19: станции — вершины, перегоны и переходы — рёбра. Но теперь у каждого ребра есть число — сколько минут оно стоит. Такой граф называют взвешенным, а длиной пути в нём — сумму весов рёбер. Минуты у нас оценочные: перегон — расстояние по прямой при средней скорости 41 км/ч плюс полминуты стоянки, переход — четыре минуты. В жизни расписание сложнее, но навигатору хватит и этого: веса разные. Функция load_metro(minutes=True) из модуля cs.graphs отдаёт словарь словарей: graph[станция][сосед] — минуты.

Как научить волну считать минуты? Есть способ в лоб, хоть и расточительный. Разрежем каждый перегон на кусочки по десятой доле минуты, поставив между ними фиктивные станции. Тогда все рёбра одинаковые, и обход в ширину найдёт самый быстрый путь: волна поползёт по десятым долям минуты. Только фиктивных станций — больше десяти тысяч, и почти всё время волна ползёт по ним от одной станции метро к другой.

Что, если не ползти, а прыгать? Когда волна приходит на станцию в момент $t$, можно сразу записать в календарь: «на соседнюю станцию волна придёт в момент $t + w$», где $w$ — вес перегона. Это календарь событий из главы 18: ближайшее событие достаём из кучи, обрабатываем и, может быть, кладём в кучу новые. На одну станцию волна может «прийти» несколько раз разными дорогами, и в календаре окажется несколько записей. Нужна только первая, самая ранняя; остальные выбрасываем, когда всплывут, — как устаревшие провода в алгоритме Прима из прошлой главы.

Амстердам, 1956. Двадцать минут на террасе

Вот рецепт Дейкстры словами. У каждой вершины есть оценка расстояния от старта: у самого старта 0, у остальных — бесконечность. Повторяем, пока есть что делать: берём ещё не готовую вершину с наименьшей оценкой и объявляем её готовой. Потом для каждого её соседа проверяем, не короче ли до него дорога через только что готовую вершину; если короче — уменьшаем оценку соседа. Эту проверку называют релаксацией ребра — оценка соседа «расслабляется», становится ближе к правде. Вершины готовы в порядке удаления от старта: волна расходится по минутам, как пожар по траве. Нажмите «Шаги» или двигайте ползунок под картинкой: зелёные вершины готовы, у жёлтых уже есть оценка, выделенные рёбра ведут к каждой вершине по лучшей известной дороге.

Сначала до вершины B нашлась дорога напрямую, 4 минуты, но, как только готова стала C, оценка B упала до 3: через C быстрее. В куче на время остались обе записи, (4, B) и (3, B), и устаревшая выброшена строкой continue. А до F волна дошла за 12 минут по пяти рёбрам, A — C — B — D — E — F, хотя есть дорога всего в три ребра, A — B — D — F: она стоит 15 минут.

Теперь то же на московском метро. Остановимся, как только готова цель: дальше волна нам не нужна. Чтобы восстановить маршрут, идём от цели назад по prev.

Двадцать шесть с половиной минут через центр, с одним переходом — с Библиотеки имени Ленина на Александровский сад. В главе 19 мы прокладывали этот маршрут вручную, теперь его нашёл алгоритм. Прежде чем добраться до цели, Дейкстра объявил готовыми 141 станцию из 312 — с этим числом мы и будем бороться в следующей поездке.

Почему волна не ошибается

Дейкстра объявляет вершину готовой и больше её не трогает. Откуда уверенность, что потом не найдётся дорога короче? Обозначим через $\delta(v)$ истинное кратчайшее расстояние от старта до $v$, а через $\mathrm{dist}[v]$ — оценку алгоритма. Оценка никогда не бывает меньше правды: каждая оценка — длина какого-то найденного пути.

Рассуждение того же рода, что в главе 23: жадный выбор — ближайшая из не готовых вершин — безопасен. Неотрицательность весов использована ровно в одном месте: $\delta(y) \le \delta(u)$, «дальше по пути дорога не становится короче». Запомните это место: в третьей поездке веса станут отрицательными.

Сколько стоит волна

Каждая вершина становится готовой один раз, каждое ребро релаксируется с каждого конца не больше одного раза, и каждая удачная релаксация кладёт в кучу одну запись. Записей поэтому не больше $2m$, и каждая операция с кучей стоит $O(\log n)$. Всего $O((n + m) \log n)$. В статье 1959 года кучи ещё не было — Уильямс опишет её только в 1964-м, — и ближайшую вершину Дейкстра искал перебором всех не готовых: $n$ раз по $n$ сравнений, $O(n^2)$. Для 64 голландских городов это мгновенно. Проверим город побольше — квадратный, с кварталами: перекрёстки — вершины, улицы между соседними перекрёстками — рёбра со случайным временем от 1 до 9 минут.

Вчетверо больше перекрёстков — перебор работает в шестнадцать раз дольше, а куча — раз в пять: сверх четырёх набегает из-за логарифма в оценке и из-за того, что большая таблица хуже помещается в кэш. На 160 000 перекрёстков куча тратит доли секунды, а перебору понадобилось бы порядка десяти минут. Здесь, в отличие от проверки if u in done в первой ячейке, устаревшие записи узнаются по-другому: d > dist[u] — в куче лежит оценка хуже той, что уже известна. Оба способа работают одинаково.

Поездка вторая: в сторону цели

Чтобы найти дорогу из Сокольников в Москва-Сити, Дейкстра объявил готовыми 141 станцию — почти половину метро, включая Преображенскую площадь и Бульвар Рокоссовского, которые лежат в противоположной стороне. Волна расходится во все стороны одинаково: где цель, она не знает. Человек с картой так не делает — он сразу смотрит туда, куда едет. Как научить этому алгоритм и не потерять гарантию кратчайшего пути?

Идея A* в одной строке. Дейкстра достаёт из кучи вершину с наименьшим пройденным расстоянием $g(v)$. A* достаёт вершину с наименьшей суммой $g(v) + h(v)$, где $h(v)$ — оценка того, сколько ещё осталось от $v$ до цели. Такую оценку называют эвристикой. Для карты естественная эвристика — расстояние до цели по прямой, делённое на скорость. Станции за спиной получают большую сумму и ждут, а волна вытягивается в сторону цели.

Но ошибаться оценке позволено только в одну сторону. Если $h$ завышает остаток, алгоритм может пройти мимо кратчайшего пути, решив, что тот хуже. Эвристику, которая никогда не завышает расстояние до цели, называют допустимой. Для метро это значит: делить расстояние по прямой надо на скорость, быстрее которой в нашей модели не ездит ни один поезд. Тогда до цели заведомо не доехать быстрее, чем за $h$.

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

Расстояние по прямой согласовано: по неравенству треугольника прямая от $u$ до цели не длиннее прямой от $u$ до $v$ плюс прямой от $v$ до цели, а проехать ребро $u \to v$ быстрее, чем по прямой с наибольшей скоростью, нельзя. Каждая согласованная эвристика допустима (сложите неравенства вдоль кратчайшего пути до цели); обратное верно не всегда, но A* с допустимой эвристикой тоже находит кратчайший путь — только иногда объявляет одну вершину готовой не один раз.

Осталось узнать наибольшую скорость. Посчитаем её по данным: для каждого ребра — сколько километров по прямой оно проходит за минуту. Получится около 39 км/ч — чуть меньше 41 км/ч из нашей модели, потому что в каждом перегоне есть полминуты стоянки. Быстрее всех выходят самые длинные перегоны: на них стоянка заметна меньше всего.

Ответы совпадают до десятой минуты, а работы в разы меньше: 56 станций вместо 141, 78 вместо 255, 5 вместо 33. Вернитесь к виджету метро и включите «A*»: бледное пятно готовых станций вытянется вдоль маршрута. А в виджете с клетками сдвиньте ползунок дальше единицы. Эвристика начинает завышать, поиск ещё быстрее летит к цели — но путь иногда выходит длиннее кратчайшего. Так поступают, когда скорость важнее точности: например, в компьютерных играх, где сотни персонажей ищут дорогу каждую секунду.

Поездка третья: деньги вместо минут

Навигатор научился минутам. Теперь пусть на рёбрах будут деньги: курьер платит за платную дорогу, а на некоторых участках ему, наоборот, доплачивают — скажем, за попутную посылку. Доплата — это отрицательный вес. Курьеру из A в D можно ехать через C, заплатив 2 и ещё 2, а можно через B: заплатить 5, но на отрезке B — D получить 4. Что скажет Дейкстра?

Дейкстра объявил D готовой с ценой 4: на тот момент это была ближайшая не готовая вершина. Потом готовой стала B, и выяснилось, что через неё до D всего 1, но готовую вершину Дейкстра больше не трогает. Сломалось место доказательства, которое мы просили запомнить: «дальше по пути дорога не становится короче». С отрицательным ребром становится.

Вторая функция ничего не выбирает. Она прогоняет релаксацию по всем рёбрам подряд, круг за кругом, $n - 1$ раз. Этот алгоритм носит имена Ричарда Беллмана, автора названия «динамическое программирование» из главы 22, и Лестера Форда-младшего; они опубликовали его в 1958 и 1956 годах, а примерно тогда же его нашли Альфонсо Шимбел и Эдвард Мур. И это действительно динамика: после $k$ кругов каждая оценка не хуже лучшего пути, в котором не больше $k$ рёбер.

Платим за это скоростью: $n - 1$ кругов по $m$ рёбер — $O(nm)$, а не $O(m \log n)$. Для метро это четверть миллиона релаксаций, мгновенно; для дорог страны — безнадёжно. Поэтому Беллмана — Форда берут, только когда без отрицательных весов не обойтись, — например, когда на рёбрах курсы валют.

Деньги по кругу

Если же цикл отрицательной длины есть, кратчайшего пути нет вовсе: пройдя по такому циклу ещё раз, путь можно сделать ещё короче, и так без конца. Такой цикл называют отрицательным. Зато его легко заметить: если и в $n$-м круге какая-то оценка уменьшилась, цикл есть — без него всё успокоилось бы за $n - 1$ круг.

Пригодиться отрицательный цикл может на валютном рынке. Пусть за евро дают 0,96637 швейцарского франка, за франк — 167,54 иены, а за иену — 0,0061825 евро. Обменяем тысячу евро по кругу: если вернётся больше тысячи, мы нашли арбитраж — прибыль без риска, на одной несогласованности курсов. Обмен по кругу выгоден, когда произведение курсов больше единицы. Логарифм превращает произведение в сумму: $r_1 r_2 r_3 > 1$ тогда и только тогда, когда $\log r_1 + \log r_2 + \log r_3 > 0$, то есть когда $(-\log r_1) + (-\log r_2) + (-\log r_3) < 0$. Напишем на каждом ребре $-\log(\text{курс})$ — и выгодный круг обмена станет отрицательным циклом.

Тысяча евро за три обмена превратилась в 1000,98. Стартуем мы «отовсюду сразу», с нулями у всех вершин, — это всё равно что добавить фиктивную вершину-старт с рёбрами веса 0 ко всем валютам: тогда достижим любой цикл. А чтобы попасть в цикл, приходится отступить по prev на $n$ шагов. Вершина, которая изменилась в последнем круге, сама может висеть на хвосте, ведущем из цикла, а цепочка prev длиннее $n$ обязана повторить вершину, то есть зайти в цикл. Учтите и другое: Беллман — Форд находит какой-нибудь отрицательный цикл, не обязательно самый выгодный. Найти самый выгодный круг без повторов — задача из тех, которые в главе 57 назовут NP-трудными.

Таблица условная: курсы похожи на рыночные, но в них нарочно спрятан перекос — евро меняется на франки чуть дороже, чем следует из остальных курсов. На бирже такие перекосы держатся доли секунды: их ищут программы, и первые же сделки выравнивают курсы. А комиссия за обмен съедает прибыль ещё раньше — сдвиньте ползунок в виджете. Сегодняшние курсы и их историю можно посмотреть в конвертере валют на этом сайте; проверьте, удастся ли найти в них круг.

Все пары сразу

Иногда нужны расстояния между всеми станциями сразу: найти две самые далёкие или узнать, сколько в среднем едет пассажир. Можно запустить Дейкстру из каждой станции. А можно короче — тремя вложенными циклами Роберта Флойда и Стивена Уоршелла (1962). Это снова динамика из главы 22. Пусть $d_k[i][j]$ — кратчайший путь из $i$ в $j$, который пересаживается только на станциях из первых $k$. Добавляя станцию $k$, мы либо обходимся без неё, либо едем через неё: $d[i][j] = \min(d[i][j],\; d[i][k] + d[k][j])$. После всех $k$ таблица готова. Отрицательные рёбра разрешены, отрицательные циклы — нет: они проявятся отрицательным числом на диагонали.

Тридцать миллионов проверок — две-три секунды. Две самые далёкие станции в нашей модели разделяют 97 минут, а в среднем между двумя случайными станциями 36 минут. Время Флойда — Уоршелла $O(n^3)$, и это много: Дейкстра из каждой вершины даёт то же за $O(n (n + m) \log n)$, и на разреженных графах вроде метро это быстрее. Зато в трёх строках цикла трудно ошибиться, и они без изменений работают с отрицательными рёбрами.

Поездка четвёртая: миллионы дорог

В нашем графе метро 312 станций. Дорожная сеть Западной Европы, на которой исследователи испытывают алгоритмы маршрутов, — около 18 миллионов перекрёстков и 42 миллионов отрезков дорог. Наша куча прошла 160 000 перекрёстков примерно за треть секунды; на Европе, если прикинуть грубо, тот же код думал бы полминуты над каждым маршрутом. A* с прямой помогает, но на дорогах слабее, чем кажется: прямая не знает, что между вами и целью река с одним мостом. Как же телефон отвечает раньше, чем вы уберёте палец с экрана?

Выручает предподсчёт: один раз, заранее, тратим много времени, чтобы потом каждый запрос был быстрым. Один предподсчёт мы уже сделали: после двух-трёх секунд Флойда — Уоршелла любой маршрут по метро — одно обращение к таблице. Но для 18 миллионов перекрёстков таблица всех пар — это $3 \cdot 10^{14}$ чисел, больше петабайта. Нужен предподсчёт поскромнее, и придумано их несколько.

Ориентиры. Выберем несколько вершин на краях карты и заранее посчитаем расстояния от каждой до всех остальных. Неравенство треугольника даёт оценку: если от ориентира $L$ до цели 50 минут, а до вершины $v$ — 20, то от $v$ до цели не меньше 30, иначе от $L$ до цели можно было бы доехать быстрее 50. В общем виде $d(v, t) \ge |d(L, t) - d(L, v)|$, и максимум по ориентирам — допустимая эвристика для A*. Она меряет дорогами, а не прямой, поэтому знает про реки и мосты. Этот метод (Эндрю Голдберг и Крис Харрельсон, 2005) называют ALT — по первым буквам слов A*, landmarks и triangle inequality.

Пять волн заранее — и вместо 141 станции поиск смотрит 20, вместо 255 — 19. Прямая из прошлой поездки давала 56 и 78: расстояния по рельсам подсказывают гораздо лучше.

Иерархии. Человек, который едет из Москвы в Казань, не перебирает дворы Нижнего Новгорода: он выезжает на трассу и съезжает с неё у цели. Метод сжатия иерархий (contraction hierarchies; Роберт Гайсбергер, Петер Сандерс и соавторы, 2008) делает это строго. Перекрёстки упорядочивают по «важности» и выбрасывают по одному, начиная с самых неважных. Выбрасывая перекрёсток, между его соседями добавляют ребро-сокращение, если кратчайший путь между ними шёл через него, — так расстояния между оставшимися не меняются. Запрос — две волны Дейкстры, от старта и от цели, которые поднимаются только к более важным перекрёсткам и встречаются наверху, «на трассе». Каждая волна видит сотни вершин вместо миллионов, а ответ точный.

Самые быстрые из известных методов отвечают на запрос по дорожной сети целого континента за несколько сотен наносекунд, а свежие пробки учитывают меньше чем за секунду (это данные обзора Ханны Баст и соавторов 2016 года). Пробки меняют веса рёбер каждую минуту, поэтому предподсчёт делят на две части: долгую, которая зависит только от карты дорог, и быструю, которая пересчитывает веса. Какие именно методы стоят в конкретном навигаторе, компании обычно не рассказывают, но все эти принципы описаны в открытых статьях.

Задачи

Четыре задачи — четыре версии навигатора. В каждой есть большой тест с секундомером и край, о который легко споткнуться.

Куда дальше

Навигатор готов, но отвечает он на вопрос одного пассажира. У диспетчера вопрос другой: по сети дорог идут тысячи грузовиков, у каждой дороги свой предел — сколько машин в час она пропускает, — и спрашивают уже не «как проехать», а «сколько всего проедет и где узкое место». Сколько груза пропустит сеть дорог целиком? В 1950-х годах над этим сидели военные аналитики с картой железных дорог, и ответ оказался связан с другим вопросом: как эту сеть разрезать. Об этом — следующая глава.