Двунаправленный поиск

От площади Республики до Зелёного базара по улицам 3,79 км. Чтобы это узнать, Дейкстра осматривает 1422 перекрёстка: всё, что ближе к старту, чем базар. Пустим вместо одной волны две — одну от площади, другую от базара. Каждой достаточно дойти до середины пути, и вместе они осматривают 769 перекрёстков. Ниже обе волны на настоящих улицах Алматы. Перенесите финиш касанием карты, а потом переключите остановку на «Стоп при встрече» и нажмите «Найти ловушку»: правило, которое кажется очевидным, отвечает неверно, и сцена найдёт место, где это видно.

Оранжевая волна растёт от A, синяя — от B. Пунктирные круги того же цвета — радиусы волн: дальше по прямой ни одна волна не забралась, потому что дорога не бывает короче прямой. Серый пунктир — круг, в который пришлось бы уложить одну волну. Отношение площадей — и есть выигрыш, но не весь: где он больше, а где меньше, разберём ниже.

Идея

Кратчайший путь из A в B длины D можно разрезать посередине. Волна от A, дошедшая до радиуса D/2, и волна от B, дошедшая до D/2, вместе покрывают весь путь. Два круга радиуса D/2 по площади вдвое меньше одного круга радиуса D, и перекрёстков в них во столько же раз меньше. Найденный путь склеен из куска одной волны, одной улицы между волнами и куска другой волны.

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

1. Какую волну двигать. Обе волны — обычная Дейкстра со своей кучей. На каждом шаге достаём вершину из той кучи, где ключ меньше: тогда радиусы растут поровну. Можно чередовать волны по очереди или двигать ту, у которой меньше куча, — на правильность это не влияет, только на скорость.
2. По каким рёбрам идёт вторая волна. Волна от B ищет пути в B, а не из него, поэтому идёт по рёбрам против их направления. На карте с двусторонними улицами этого не видно, а в графе с односторонними улицами и в сети рейсов это обязательно.
3. Когда остановиться. Храним μ — длину лучшего пути из A в B, найденного до сих пор. Каждый раз, когда волна просматривает ребро (u, v), а у v уже есть метка другой волны, получен путь A … u → v … B, и μ, если он короче, уменьшаем. Останавливаемся, когда сумма радиусов — наименьших ключей двух куч — дорастает до μ.

Третье решение кажется лишним: зачем μ и суммы, если можно остановиться там, где волны встретились, и ответить путём через место встречи? Это первое, что приходит в голову, и это неверно.

Ловушка: место встречи

Пусть поиск останавливается, как только какой-нибудь перекрёсток достали из куч обе волны, и отвечает путём через него. Ниже такой поиск по шагам на одном квартале у площади Республики: старт A — угол Желтоксан и Тимирязева, финиш B — на Сатпаева, к востоку от площади. Оранжевые числа — расстояния от A, синие — от B; жирные — окончательные. Под картой — радиусы волн и μ.

Квартал можно обойти с двух сторон. Северная сторона — по Желтоксан до Сатпаева и дальше по Сатпаева — 1106 м. Южная — по Тимирязева и вверх к Сатпаева — 1194 м. На южной стороне волны шли быстрее: длинный кусок Тимирязева без единого перекрёстка волна от A проходит одним ребром. Поэтому первым перекрёстком, который достали обе волны, оказался юго-восточный угол квартала, и путь через него на 88 м длиннее кратчайшего.

Северный путь волны тоже нашли, и гораздо раньше. Пройдите по шагам до момента, когда μ становится равным 1106: это 25-й осмотренный перекрёсток. Волна от A достаёт угол Желтоксан и Сатпаева и видит по соседству перекрёсток на Сатпаева, до которого уже дотянулась волна от B. Путь найден, и он кратчайший. Но ни один из двух концов этой короткой улицы так и не достанется обеим волнам: кратчайший путь сшит по улице, концы которой принадлежат разным волнам. Правило «стоп при встрече» на такие улицы не смотрит.

Это не редкость. На 40 случайных маршрутах по Алматы из листинга ниже правило «стоп при встрече» дало путь длиннее кратчайшего 13 раз. Там ошибки маленькие, до 0,7 %, а в квартале выше — 8 %. Ошибка случается там, где есть два обхода почти одной длины, а в городе, расчерченном на кварталы, их много.

Почему верная остановка верна

Обозначим δ(x, y) длину кратчайшего пути, r_A и r_B — наименьшие ключи в кучах волн. Сначала одно свойство обычной Дейкстры, которое здесь работает за двоих.

Доказательство заодно объясняет ловушку. Ребро, на котором сшит кратчайший путь, найдено вовремя, но его концы принадлежат разным волнам, и место «встречи» тут ни при чём. Из теоремы следует и мягкая версия правила: можно остановиться, когда какую-то вершину w обработали обе волны, если отвечать не путём через w, а числом μ. В этот момент r_A + r_B ≥ δ(A, w) + δ(w, B) ≥ μ, то есть верное правило уже сработало бы. В квартале выше оно срабатывает на 53-м осмотренном перекрёстке, а встреча случается на 72-м: верная остановка ещё и раньше.

Код

Две волны живут в одной функции: массивы расстояний, куч и отметок «обработано» — пары, индекс 0 у волны от старта, 1 — у волны от финиша. Функция top выбрасывает из кучи устаревшие записи и возвращает наименьший ключ: из него сравниваются радиусы. Флаг naive включает ошибочное правило из ловушки, чтобы сравнить оба на одних и тех же маршрутах.

Zheltoksan/Timiryazev -> Satpayev
  one wave         1106 m, settled   148
  two waves        1106 m, settled    53
  first meeting    1194 m, settled    72
Republic Square -> Green Bazaar
  one wave         3786 m, settled  1422
  two waves        3786 m, settled   769
  first meeting    3786 m, settled   778

Чтобы восстановить сам маршрут, храните родителя у каждой метки обеих волн и запоминайте ребро, на котором последний раз уменьшилось μ. От его концов идите по родителям: к A — по родителям первой волны, к B — второй. В момент остановки эти цепочки ведут по кратчайшему пути: любой другой путь по родителям был бы не длиннее μ, а короче μ путей нет.

Сколько экономится

Оценка в худшем случае та же, что у Дейкстры: каждая волна обрабатывает вершину не больше одного раза, так что O((V + E) log V) времени и O(V) памяти, только массивов вдвое больше. Бывает и проигрыш. Если старт в редкой сети, а финиш в густой, круг радиуса D/2 вокруг финиша может оказаться тяжелее круга радиуса D вокруг старта; на улицах Алматы так бывает нечасто, но бывает. Весь выигрыш — в устройстве графа, и считать его удобно через «шар»: сколько вершин лежит не дальше r от данной.

Плоские сети. На карте шар — это круг, и вершин в нём пропорционально площади, то есть r². Одна волна осматривает шар радиуса D, две — два шара радиуса D/2: 2 · (D/2)² = D²/2, вдвое меньше. На 40 случайных маршрутах по Алматы из листинга одна волна осматривает в среднем 4263 перекрёстка, две — 2614: в 1,6 раза меньше, а не в 2. Причин две. Город кончается: большой круг вокруг старта у окраины наполовину пуст, и одна волна платит меньше, чем πD², а маленькие круги двух волн почти всегда целиком лежат в городе. И город неоднороден: волна, которая идёт через плотный центр, тяжелее волны в частном секторе, а радиусы мы выравниваем по длине, а не по работе.

Время выигрывает ещё меньше. У двух волн две кучи, два набора массивов и проверка μ на каждом ребре, и на коротких маршрутах это съедает весь выигрыш. Замер ниже: старт в центре города, по шесть финишей на каждом расстоянии.

На коротких маршрутах две волны медленнее одной, на длинных — быстрее, и разрыв растёт с расстоянием: площадь круга растёт как D², а лишняя работа на каждый перекрёсток постоянна. В Go две волны догоняют одну уже к полутора километрам и на восьми выигрывают в 2,1 раза; в Python, где каждая лишняя операция дороже, — к двум километрам, и на восьми выигрыш — в 1,5 раза. Для навигатора, который считает маршруты через весь город и дальше, это честные полтора-два раза. Настоящую скорость дают не две волны сами по себе, а предподсчёт, в котором две волны — составная часть: об этом иерархии сжатия.

Тесный мир: корень вместо половины

Совсем другое дело — сети, где шар растёт не как квадрат, а как степень: в каждом следующем слое в b раз больше вершин, чем в предыдущем. Одна волна до глубины d осматривает около b^d вершин, две волны до глубины d/2 — около 2b^d/2. Это уже не половина, а корень. Так устроены сети знакомств, ссылок в интернете и авиарейсов: из любого места до любого — несколько шагов, а каждый шаг умножает охват.

Ниже сеть рейсов всего мира: 3468 аэропортов и 84 869 перелётов из базы позывных Virtual Radar Server. Взяты аэропорты, из которых можно улететь в любой другой и вернуться. Ищем маршрут с наименьшим числом перелётов — это поиск в ширину. Волна от B летит по рейсам задом наперёд: она ищет, откуда можно прилететь в B.

Из Алматы в Квинстаун три перелёта. Одна волна, чтобы это выяснить, отмечает 3030 аэропортов из 3468: за три шага она обходит почти весь мир. Две волны отмечают 185. Из 300 случайных пар аэропортов одна волна отмечает в среднем 1667, две — 143, в 11,7 раза меньше. И это на сети всего из трёх с половиной тысяч вершин; чем больше сеть, тем больше разница между b^d и 2b^d/2. Обратите внимание и на исключение: для прямого рейса в Астану обеим волнам нужно по 57 отметок — одного слоя от A уже хватает, и второй волне нечего экономить.

В невзвешенном графе остановку можно упростить. Если расширять волны целыми слоями и сначала ту, у которой слой меньше, то первое же касание — ребро из новой вершины одной волны в отмеченную вершину другой — даёт кратчайший путь. Пока касаний не было, отмеченные множества не пересекались: значит, ни одна вершина не лежит ближе k_A к A и одновременно ближе k_B к B, где k_A, k_B — глубины слоёв, и путь короче k_A + k_B + 1 невозможен. А касание при расширении слоя k_A даёт путь ровно такой длины. Расширять вершины поштучно, вперемешку из двух очередей, и останавливаться на первом касании уже нельзя: тогда на дальнем конце может оказаться вершина следующего слоя.

Две волны A*

A* сужает одну волну подсказкой о расстоянии до финиша, двунаправленный поиск заменяет одну волну двумя. Хочется сложить оба выигрыша: волне от A дать подсказку «по прямой до B», волне от B — «по прямой до A», а остальное оставить как было. Ниже это сделано на маршруте от площади Республики до MEGA Alma-Ata. Переключайте варианты.

«Свои подсказки» осматривают всего 559 перекрёстков — вдвое меньше одной волны A* — и находят путь на 320 м длиннее кратчайшего. Что сломалось: ключ в куче A* — не радиус, а оценка длины всего пути через вершину, от A до B. Сумма двух таких ключей примерно вдвое больше длины пути, и правило «сумма ключей ≥ μ» срабатывает, как только найден хоть какой-нибудь путь. Это та же остановка при встрече, только замаскированная.

Глубже причина в том, что две волны меряют разными линейками. A* — это Дейкстра на графе, где длина каждого ребра (u, v) заменена на приведённую: w − h(u) + h(v) (это доказано в статье о A*). У волны от A подсказка h_B, у волны от B, которая идёт по рёбрам в обратную сторону, — h_A, и одно и то же ребро в двух волнах получает разную приведённую длину. Доказательство верной остановки опиралось на то, что обе волны считают в одних и тех же единицах. Есть два способа это вернуть.

Остановка Поля. Оставить волнам их подсказки, а останавливаться, когда наименьший ключ одной из куч дорос до μ. Каждая волна A* сама по себе — честный поиск: пока в её куче есть ключ меньше μ, путь короче μ ещё может найтись, а когда нет — не может. Это верно, но медленно: поиск ждёт, пока одна из волн одна проделает почти всю работу. На маршруте сцены — 2379 перекрёстков, вдвое больше, чем у одной волны A*.

Средние подсказки. Дать обеим волнам одну линейку. Возьмём потенциал

$$p(v) = \frac{h_B(v) - h_A(v)}{2}$$

и будем класть в кучу волны от A ключ d_A(v) + p(v), а в кучу волны от B — d_B(v) − p(v). Такие подсказки называют согласованными между собой: их сумма постоянна (здесь — ноль).

Сложить два выигрыша не выходит и здесь. Каждая волна получает только половину своей подсказки и половину чужой со знаком минус, поэтому её тянет к цели слабее, чем одиночную волну A*. На маршруте сцены — 1001 перекрёсток против 1063 у одной волны A*. Листинг сравнивает все варианты на тех же 40 случайных маршрутах, что и первый листинг.

                               settled  longer  worst  met at best at
one wave, Dijkstra                4263       0   0.0%
one wave, A*                      1009       0   0.0%
two waves, Dijkstra               2614       0   0.0%     92%     94%
two waves, A*, own hints           570      21  10.6%    100%    100%
two waves, A*, Pohl's stop        1986       0   0.0%     30%     34%
two waves, A*, averaged hints      853       0   0.0%     88%     92%

Свои подсказки ошиблись на 21 маршруте из 40, до 10,6 %. Остановка Поля верна, но осматривает вдвое больше одной волны A*. Средние подсказки верны и выигрывают у одной волны A* около 15 %. Это скромно, и это честный результат. Эндрю Голдберг и Крис Харрельсон в 2005 году сравнили такие варианты на больших дорожных сетях: подсказка по прямой у них почти ничего не давала ни одной волне, ни двум, а с подсказками по ориентирам (тот самый ALT из статьи о A*) две волны со средними потенциалами обгоняли одну — на далёких маршрутах больше чем вдвое, на ближних меньше чем в полтора раза.

Последние два столбца — ответ на старый спор. «Met at» — какая доля работы пройдена, когда волны впервые соприкоснулись и появилось первое μ. «Best at» — когда μ стало окончательным. У остановки Поля волны встречаются, проделав 30 % работы, лучший путь находится к 34 %, а остальные две трети работы уходят на то, чтобы убедиться, что короче нет. Айра Поль в 1971 году соединил две волны с подсказками и получил, что такой поиск хуже одиночного. Объяснял он это картинкой с двумя ракетами, которые летят навстречу и расходятся, не встретившись; Нильс Нильсон перепечатал её в учебнике 1980 года, и объяснение прижилось. В 1997 году Херманн Кайндль и Герхард Кайнц показали, что оно неверно: волны встречаются рано, а основная работа тратится уже после встречи — на поиск лучшего пути и на доказательство, что лучше нет. В их опытах на пятнашках первый путь находился в среднем после 7 % всей работы, оптимальный — после 22 %, а остальное уходило на проверку. Таблица выше показывает то же самое на улицах Алматы.

Где работает

• Навигаторы. Две волны редко ходят по сырому графу дорог, но внутри быстрых методов они почти всегда. Запрос в иерархиях сжатия — это две волны Дейкстры, от старта и от финиша, которые поднимаются только к более важным перекрёсткам и встречаются наверху. Лучший путь там тоже запоминают в μ, а останавливаются по-своему — об этом в статье об иерархиях.
• Сети ссылок. Сайт «Шесть рукопожатий Википедии» (Six Degrees of Wikipedia) находит кратчайшие цепочки ссылок между двумя статьями двунаправленным поиском в ширину — с этих слов начинается файл с поиском в его исходном коде. Волны расширяются целыми слоями, и каждый раз та, у которой в следующем слое меньше ссылок. Вторая волна идёт по ссылкам задом наперёд, поэтому сайт хранит для каждой статьи и исходящие, и входящие ссылки.
• Головоломки и перебор. Когда пространство состояний растёт экспоненциально, две волны глубины d/2 вместо одной глубины d превращают невозможный перебор в возможный. Тот же приём без графа — встреча посередине: перебрать половинки задачи отдельно и сопоставить.

История

В 1966 году Т. Николсон напечатал в журнале The Computer Journal статью «Finding the shortest route between two points in a network». Его метод вёл маршруты сразу от начала и от конца и каждый раз продлевал те, что прошли меньше всего, — те же две волны с выбором по радиусу. И уже там сказано главное: когда найден первый полный маршрут, работа не кончена — нужно ещё убедиться, что он кратчайший.

В 1969 году Айра Поль защитил диссертацию о двунаправленном и эвристическом поиске, а в 1971 году напечатал статью «Bi-directional search». Доказательство того, что двунаправленная Дейкстра с запоминанием μ находит кратчайший путь, обзоры приписывают ему. Там же он попробовал добавить волнам подсказки — и получил тот самый неудачный результат, который потом четверть века объясняли ракетами.

Средние потенциалы предложили в 1994 году Т. Икэда и соавторы — на конференции по навигации автомобилей. В 2005 году Голдберг и Харрельсон разделили способы соединить A* с двумя волнами на симметричные (у каждой волны своя подсказка и остановка Поля) и согласованные (общая линейка), и по числу осмотренных вершин лучше всех у них оказался согласованный вариант с ориентирами. А в 2024 году Бернхард Хойплер, Рихард Гладик, Вацлав Рожонь, Роберт Тарьян и Якуб Тетек доказали, что аккуратно устроенный двунаправленный поиск оптимален на каждом отдельном графе: в их модели никакой верный алгоритм не может просмотреть на нём меньше рёбер больше чем в постоянное число раз.

Задачи

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