Иерархии сжатия
Также: Contraction hierarchies · CH · сжатие вершин · node contraction
Как навигатор отвечает за доли миллисекунды: один раз заранее он «сжимает» перекрёстки от неважных к важным, заменяя пути через них ярлыками, а потом ищет путь двумя волнами, которые только поднимаются по ярусам. На улицах Алматы такой поиск осматривает 119 перекрёстков вместо 4263 у Дейкстры и отвечает так же точно.
Дейкстра, чтобы проложить случайный маршрут по Алматы, осматривает в среднем 4263 перекрёстка из 7909. Навигатору, у которого под рукой дороги целого континента, так нельзя: миллионы перекрёстков на каждый запрос. Поэтому настоящие навигаторы один раз, заранее, перерабатывают граф, а потом отвечают за доли миллисекунды. Ниже одна из таких переработок, иерархия сжатия, строится прямо в вашем браузере по настоящим улицам Алматы. Перекрёстки исчезают по одному, от самых неважных, а пути через них заменяются ярлыками. Двигайте ползунок: под конец от города остаётся скелет главных улиц. Потом переключитесь на «Запрос» и выберите A и B, а «Ярусы» покажут, как поиск поднимается по иерархии.
На «Ярусах» каждый перекрёсток поднят на высоту своего яруса: чем позже его сжали, тем выше. Волны от A и от B идут только вверх, к более важным перекрёсткам, и встречаются на вершине. Ни одна из них не спускается в кварталы: путь по кварталам у финиша спрятан в ярлыках, а ярлыки при ответе разворачиваются обратно в улицы.
Идея
Упорядочим перекрёстки по важности и будем выбрасывать их из графа по одному, от неважных к важным. Выбрасывая перекрёсток v, посмотрим на каждую пару его соседей u и w: если кратчайший путь между ними шёл через v, добавим между u и w ярлык — ребро длиной u–v–w. Расстояния между оставшимися перекрёстками от этого не меняются. Когда выброшено всё, в графе с ярлыками между любыми двумя точками есть кратчайший путь, который сначала только поднимается к более важным перекрёсткам, а потом только спускается. Поэтому запрос — это две волны Дейкстры вверх: от старта и от финиша.
Слово «важность» здесь не про размер улицы. Алгоритм ничего не знает о проспектах — он смотрит только на граф и считает: если сжать перекрёсток сейчас, сколько ярлыков придётся добавить? Перекрёсток в тупике можно выбросить даром, перекрёсток в середине прямой улицы — за один ярлык, а узел, через который идут пути во все стороны, — только ценой многих ярлыков. Такие и остаются на верхних ярусах. Главные дороги алгоритм находит сам, по тому, как устроены кратчайшие пути.
Сжатие по шагам
Возьмём 21 перекрёсток центральной сетки вокруг угла Шевченко и Чайковского и сожмём их тем же алгоритмом, что строит иерархию для всего города. Для каждой пары соседей сжимаемого перекрёстка ищется свидетель — путь в обход, не длиннее пути через перекрёсток. Нашёлся — ярлык не нужен. Не нашёлся — ставим ярлык.
Свидетель часто оказывается просто соседним кварталом: от E до J можно доехать через F за 334 м, а можно в обход через I — за 333 м, и ярлык не нужен. В сетке кварталов почти всегда есть второй путь той же длины, и сжатие обходится без ярлыков. Ярлыки нужны там, где обхода нет: на краю сетки, в тупиках, на длинных улицах без пересечений.
Порядок выбирается на ходу. У каждого перекрёстка есть приоритет: сколько ярлыков даст его сжатие минус сколько рёбер уйдёт вместе с ним — разница рёбер, — плюс сколько его соседей уже сжато. Второе слагаемое не даёт сжимать подряд перекрёстки одного района: иерархия выходит ровнее, когда сжатия разбросаны по всему графу. Приоритеты хранятся в куче, но пересчитывать их после каждого сжатия у всех слишком дорого. Поэтому пересчёт ленивый: достаём из кучи перекрёсток с наименьшим приоритетом, пересчитываем его, и если он всё ещё не больше следующего в куче — сжимаем, а если вырос — кладём обратно. В сцене такие возвраты тоже видны.
Поиск свидетеля — обычная Дейкстра от соседа u в графе без v, но с двумя ограничениями. Она останавливается, когда расстояние превысило длину пути через v: дальше свидетеля не будет. И она сдаётся, осмотрев 50 перекрёстков. Если из-за этого лимита свидетеля не нашли, ставим лишний ярлык. Лишний ярлык ничего не ломает — это ребро с длиной настоящего пути, — он лишь немного утяжеляет граф. А пропущенный ярлык сломал бы всё, поэтому ошибаться разрешено только в эту сторону.
Порядок решает всё
Сжимать можно в любом порядке: иерархия будет верной при любом. Но размер её зависит от порядка очень сильно. Ниже кусок города вокруг площади Республики сжат тремя способами: по разнице рёбер, как выше; по числу улиц у перекрёстка в начале; и в случайном порядке. Цвет ярлыка — ярус перекрёстка, который он обходит.
Случайный порядок на куске в два километра даёт вчетверо больше ярлыков и почти вчетверо больше ярусов, а запрос осматривает в два с половиной раза больше перекрёстков. С ростом куска разрыв растёт — переключите на три километра. Причина понятна: если рано сжать перекрёсток, через который идут пути во все стороны, его соседей придётся попарно соединить ярлыками. Они станут связаны ещё теснее, и сжатие любого из них потребует ещё больше ярлыков. Хороший порядок откладывает такие узлы на самый верх, где их мало и где они уже никому не мешают.
Почему ответ точный
Обозначим через G* исходный граф вместе со всеми ярлыками, а через ранг — номер перекрёстка в порядке сжатия: чем позже сжат, тем ранг выше. Нужны три утверждения: сжатие не меняет расстояний, в G* есть кратчайший путь «вверх, потом вниз», и запрос его находит.
Сжатие одной вершины v не меняет расстояний между оставшимися вершинами.
Ярлык — ребро с длиной настоящего пути u–v–w, поэтому короче расстояния не станут. Длиннее тоже: возьмём кратчайший путь между оставшимися вершинами, проходивший через v. Все длины положительны, так что v на нём одна, и путь входит в неё из соседа u, а выходит в соседа w. Кусок u–v–w — кратчайший путь между u и w, а пару (u, w) сжатие проверило: либо добавило ярлык той же длины, либо нашло свидетеля — путь без v не длиннее. Заменим кусок ярлыком или свидетелем, и получим путь той же длины без v.
Для любых связанных вершин s и t в G* есть кратчайший путь, ранги вершин которого сначала только растут, а потом только убывают.
Назовём долиной внутреннюю вершину пути, чей ранг меньше рангов обоих соседей по пути. Путь без долин устроен как раз «вверх, потом вниз»: на нём нет вершины, где ранги поворачивают снизу вверх.
Пусть кратчайший путь P содержит долину v с соседями u и w. Рёбра (u, v) и (v, w) есть в G*, и оба появились не позже сжатия v: ярлыки добавляются только между ещё не сжатыми вершинами, а после сжатия у v новых рёбер нет. Когда v сжимали, u и w ещё были в графе — их ранги выше. Значит, пару (u, w) проверили: в графе тогда был либо ярлык u–w той же длины, что u–v–w, либо свидетель не длиннее. Оба лежат в G*, и все их внутренние вершины тогда ещё не были сжаты, то есть их ранги выше ранга v. Заменим u–v–w на ярлык или свидетеля: путь останется кратчайшим.
Осталось убедиться, что замены когда-нибудь кончатся. Дадим вершине ранга r вес (n + 1)−r, где n — число вершин, и назовём весом пути сумму весов его внутренних вершин. Замена убирает вершину веса (n + 1)−r и добавляет не больше n − 1 вершин, каждая весом не больше (n + 1)−r−1, — в сумме меньше убранного. Вес пути строго уменьшается. Кратчайших путей конечное число (они простые: длины положительны), значит, замены кончаются — на пути без долин.
Запрос — две Дейкстры по рёбрам, ведущим вверх, от s и от t; волна заканчивается, когда её наименьший ключ не меньше лучшего найденного пути best; best обновляется, когда волна достаёт вершину с меткой другой волны, — находит δ(s, t).
best всегда — длина настоящего пути, поэтому best ≥ δ(s, t). Возьмём кратчайший путь «вверх, потом вниз» из теоремы, его верхнюю вершину x, длину подъёма от s до x — a, от t до x — b; a + b = δ(s, t). Дейкстра от s по рёбрам вверх находит до x путь не длиннее a, но и не короче: иначе вместе с подъёмом от t получился бы путь короче δ. Значит, x достаётся волной от s с ключом ровно a, и то же для волны от t с ключом b.
Пусть в конце best > δ. Тогда волна от s закончилась, когда её наименьший ключ стал не меньше best > δ ≥ a, — а Дейкстра достаёт вершины в порядке ключей, так что x к этому моменту уже достана. То же с волной от t. Когда x достала вторая из волн, у x уже была метка первой, и best стало не больше a + b = δ. Противоречие.
Обратите внимание на правило остановки: каждая волна заканчивается сама, когда её ключ дорос до best. Правило двунаправленной Дейкстры — остановиться, когда сумма двух наименьших ключей дорастает до best, — здесь не годится. Его доказательство опиралось на то, что волна осмотрела всё в своём радиусе. Волна вверх этого не делает: ей разрешены только рёбра вверх, и вершина в двух шагах от старта может лежать для неё сколь угодно далеко или вовсе недоступна. Листинг ниже проверяет это на тех же 40 маршрутах: с таким правилом запрос ответил бы неверно 19 раз из 40.
Код
Предподсчёт и запрос на всём городе. Оставшийся граф хранится словарями «сосед → длина», чтобы ярлыки добавлялись и рёбра удалялись за O(1). Для каждого перекрёстка запоминаются рёбра к соседям, которые остались в графе в момент его сжатия: это и есть рёбра вверх. Ярлыку запоминается перекрёсток, который он обходит, — по этим записям функция unpack рекурсивно разворачивает ярлык в улицы.
hierarchy: 12545 shortcuts, 22934 upward edges, 50 levels Republic Square -> Green Bazaar: 3786 m (Dijkstra: 3786 m) settled: Dijkstra 1422, hierarchy 114 route: 7 edges of the hierarchy, 4 of them shortcuts, 39 street pieces 40 random routes, all distances equal: Dijkstra settles 4263 on average, the hierarchy 119 the stop of bidirectional Dijkstra would answer wrongly on 19 of 40
Маршрут от площади Республики до Зелёного базара в иерархии — всего 7 рёбер, 4 из них ярлыки, и разворачиваются они в 39 настоящих участков улиц. Улицы считаются двусторонними, как во всех статьях каталога об улицах Алматы. С односторонними нужны два графа рёбер вверх: волна от старта идёт по рёбрам вверх в их направлении, а волна от финиша — по рёбрам, ведущим к нему сверху, задом наперёд, как во двунаправленном поиске.
Сколько это стоит
Гарантий для худшего случая у иерархий сжатия нет: в худшем случае запрос — та же Дейкстра, только по графу с ярлыками, а ярлыков может оказаться много. Хорошая работа на дорогах установлена опытом, поэтому честно о скорости говорят только замеры.
Предподсчёт. На Алматы — 12 545 ярлыков к 10 389 улицам, то есть граф вырастает чуть больше чем вдвое, и 50 ярусов. Строится иерархия за доли секунды: в браузере сцена выше показывает время на вашей машине, на Python листинг тратит на это около 0,7 с. В статье 2008 года создатели метода строили иерархию для дорожного графа из 18 миллионов перекрёстков и 42 миллионов направленных участков, и их основной вариант тратил на предподсчёт около десяти минут: 545 с на выбор порядка и 57 с на само сжатие.
Запрос. Сравним все способы из соседних статей на одних и тех же 40 случайных маршрутах. Числа — средние по маршрутам, из листингов этих статей.
| Способ | Осмотрено перекрёстков | Предподсчёт |
|---|---|---|
| Дейкстра | 4263 | нет |
| две волны Дейкстры | 2614 | нет |
| A* с подсказкой по прямой | 1009 | нет |
| иерархия сжатия | 119 | 12 545 ярлыков |
В 36 раз меньше Дейкстры и в 8,5 раз меньше A*. Но главное видно на графике: время запроса почти не растёт с расстоянием. Дейкстра, как и положено волне на плоскости, растёт как квадрат расстояния, а иерархия после четырёх-пяти километров выходит на полку: дальние маршруты всё равно поднимаются на верхние ярусы, а их немного.
На восьми километрах иерархия быстрее Дейкстры в 17 раз на Python и в 15 раз на Go, а на маршрутах в полкилометра выигрыш на Python пропадает: там и Дейкстре работы мало. На больших графах разница огромна. На том же графе из 18 миллионов перекрёстков запрос по иерархии в статье 2008 года осматривал в среднем 459 вершин и занимал 0,22 мс. Дейкстра до случайного финиша осматривает в среднем половину графа — миллионы вершин.
Почему на дорогах ярлыков так мало, объяснили в 2010 году Иттай Авраам, Амос Фиат, Эндрю Голдберг и Ренато Вернек. Они ввели размерность шоссе: насколько мало перекрёстков достаточно, чтобы «перехватить» все длинные кратчайшие пути в окрестности. Они доказали, что при малой размерности шоссе есть порядок сжатия, при котором запросы осматривают мало вершин. Что у настоящих дорог размерность шоссе мала, подтверждают опыты, но не доказательство.
Где иерархия не помогает
- Веса меняются. Иерархия построена под конкретные длины. Пробка на проспекте делает неверными ярлыки, которые его обходят или по нему идут, и строить всё заново долго. Поэтому маршрутизатор OSRM для данных, которые часто обновляются, например для пробок, советует другой метод — многоуровневую Дейкстру, а иерархию сжатия оставляет для случаев, где важнее всего скорость запроса. Есть и вариант самих иерархий: Юлиан Диббельт, Бен Штрассер и Доротея Вагнер в 2014–2016 годах разделили предподсчёт на долгую часть, которая зависит только от устройства дорог, и короткую, которая пересчитывает длины, — настраиваемые иерархии сжатия (CCH).
- Сети без иерархии. В дорожной сети у большинства перекрёстков есть обходы, и сжатие обходится малой кровью. В «тесных» сетях, где всё связано со всем через узлы-хабы, вроде сети рейсов из статьи о двунаправленном поиске, сжатие быстро порождает густое ядро из ярлыков, предподсчёт идёт в десятки раз дольше, а выигрыш запроса тает. Там лучше работают другие приёмы.
- Повороты и время. Запрет левого поворота или его цена — это свойство пары улиц, а не перекрёстка, и для них граф перестраивают так, чтобы вершинами стали участки улиц. Время в пути, которое зависит от часа, — отдельная большая история: для неё есть зависимые от времени иерархии, где ярлык хранит не число, а функцию времени.
Запрос можно ускорить ещё. Волна вверх иногда достаёт вершину по пути, который явно не кратчайший: в неё ведёт ребро сверху от уже достанной вершины, и через него короче. Такую вершину можно «остановить» — не продолжать поиск из неё, и ответ от этого не испортится. Приём называется stall-on-demand и был в иерархиях с самого начала.
Где работает
- OSRM — открытый маршрутизатор по данным OpenStreetMap. Команда
osrm-contractстроит иерархию сжатия. Документация советует её там, где важнее всего скорость запроса, особенно для больших таблиц расстояний, а для живых пробок и вообще по умолчанию — многоуровневую Дейкстру. - GraphHopper — другой открытый маршрутизатор. Его документация называет режим speed, то есть иерархии сжатия, самым быстрым из трёх; режим hybrid — это A* с ориентирами из статьи о A*, он медленнее, зато позволяет больше.
- Как основа других методов. Иерархия задаёт порядок «важности», и на нём держатся настраиваемые иерархии и таблицы расстояний «многие ко многим», которые нужны логистике: развести сотни курьеров по тысячам адресов.
История
К середине 2000-х исследователи маршрутов научились отвечать на запросы по дорогам континента за миллисекунды, но ценой сложных многоуровневых построений. Петер Сандерс и Доминик Шультес в 2005 году предложили иерархии шоссе — уровни дорог, найденные по самому графу, — а через год в соревновании DIMACS по кратчайшим путям такие методы показали, насколько далеко можно уйти от Дейкстры.
В 2008 году Роберт Гайсбергер в дипломной работе под руководством Сандерса и Шультеса довёл идею до предела простоты: никаких уровней, просто порядок перекрёстков, по одному сжатию за шаг. В том же году вышла статья Гайсбергера, Сандерса, Шультеса и Даниэля Деллинга «Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks» — «быстрее и проще», и это не преувеличение: сам запрос — двунаправленная Дейкстра с одним условием на рёбра. Простота и сделала метод основой для десятка следующих: мобильных иерархий для слабых устройств, зависимых от времени, настраиваемых.
Задачи
В задаче иерархия уже построена — на улицах Алматы тем же предподсчётом, что в листинге, — и нужно отвечать на тысячи запросов. Главная ловушка — правило остановки: то, что верно для двух волн Дейкстры, здесь отвечает неверно.
Запросы по ярусамДанные: Дороги Алматы © участники OpenStreetMap, ODbL