A*

От площади Республики до Зелёного базара по улицам 3,79 км, а по прямой — 2,90. Дейкстра этого не знает и растит волну одинаково во все стороны: пока она дойдёт до базара, она обойдёт полцентра, включая кварталы позади старта. A* знает, где финиш, и к пройденному расстоянию прибавляет подсказку — сколько ещё осталось хотя бы по прямой. Ниже два поиска идут шаг в шаг по настоящим улицам Алматы: слева Дейкстра, справа A*. Нажмите на любую из карт, чтобы перенести финиш, и переключайте подсказки.

Оба нашли один и тот же путь, но Дейкстра осмотрела 1422 перекрёстка, а A* — 209, в 6,8 раза меньше. И форма у волн разная: у Дейкстры пятно вокруг старта, у A* — веретено, вытянутое к финишу. Пунктир вокруг каждой волны — граница, за которую она не может выйти ни при каком устройстве улиц: круг у Дейкстры и эллипс у A*. Почему именно эллипс, станет ясно через раздел, и из этого же получится, во сколько раз A* должен выиграть.

Идея

Дейкстра достаёт из кучи вершину с наименьшим g(v) — длиной найденного пути от старта. A* достаёт вершину с наименьшим f(v) = g(v) + h(v), где h(v) — оценка того, сколько ещё идти от v до финиша. Вершины, которые уводят от финиша, получают большое h и ждут; вершины на пути к финишу выходят вперёд. Если оценка никогда не завышает, то в момент, когда из кучи достают финиш, путь к нему кратчайший.

Оценку называют эвристикой. Для карты она напрашивается сама: дорога не бывает короче прямой, поэтому расстояние по прямой до финиша — честная нижняя оценка. Ровно этот пример — города, дороги между ними и расстояние «по воздуху» — приводили авторы A* в статье 1968 года. При h = 0 получается обычная Дейкстра, так что A* — не другой алгоритм, а Дейкстра с подсказкой: код отличается одним слагаемым в ключе кучи.

Подсказка меняет только порядок, в котором вершины достают из кучи. Всё остальное — релаксация рёбер, куча, пропуск устаревших записей, остановка, когда достали финиш, — остаётся как было. Посмотрите на подпись под первой сценой: на каждом шаге A* сообщает g, h и f вершины, которую достал. Ключ f растёт медленно и ровно, хотя g и h по отдельности скачут.

Почему волна — эллипс

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

Теперь выигрыш можно сосчитать заранее. У эллипса полуоси D/2 и ½√(D² − |AB|²), у круга радиус D. Отношение площадей — 4/√(1 − 1/r²), где r = D/|AB| — во сколько раз путь по дорогам длиннее прямой. Для площади Республики и базара r = 3786/2904 ≈ 1,30: круг — 45,0 км², эллипс — 7,22 км², отношение 6,2. Перекрёстков в волнах 1422 и 209, отношение 6,8. Оценка сделана на одних площадях, без единого запуска поиска, и почти угадала.

Из формулы видно, когда A* выигрывает сильнее. Чем прямее дорога между стартом и финишем, тем ближе r к единице и тем уже эллипс: вдоль прямого шоссе он вытягивается в иглу. А если дорога петляет вдвое против прямой, эллипс почти круглый, и выигрыш падает до 4,6 раза. Есть и вывод похуже: площади и круга, и эллипса растут как D². Подсказка по прямой выигрывает постоянный множитель, но не меняет порядок роста. Это будет видно на замере.

Почему путь кратчайший

Подсказка не обязана быть расстоянием по прямой, она должна быть честной. А слово «честная» требует уточнения, и уточнений два.

Подсказку называют допустимой, если она нигде не завышает расстояния до финиша: h(v) ≤ d(v, B). И согласованной, если h(B) = 0 и для каждого ребра u → v длины w выполнено неравенство треугольника h(u) ≤ w + h(v). Согласованность сильнее: сложите неравенства вдоль кратчайшего пути от v до B — получится допустимость. Расстояние по прямой согласовано, если каждая дорога не короче отрезка между своими концами: это школьное |uB| ≤ |uv| + |vB|.

Тот же приём — прибавить к длине ребра разность «потенциалов» его концов — работает и в обратную сторону: алгоритм Джонсона подбирает потенциалы так, чтобы отрицательные рёбра стали неотрицательными.

Если подсказка допустима, но не согласована, w′ бывают отрицательными, и вершину могут достать раньше, чем к ней нашёлся кратчайший путь. Статья 1968 года на этот случай «переоткрывала» вершину — снова клала её в кучу, если путь к ней улучшился. Код этой статьи, как и код Дейкстры, вершины не переоткрывает и полагается на согласованность. Отличить одно свойство от другого на настоящих данных — первая задача в конце статьи.

По шагам: уровень игры

В играх A* обычно ищет путь по клеткам. Ниже уровень из листинга этой статьи: стены, болото, где шаг стоит 5, и трава, где шаг стоит 1. Подсказка — манхэттенское расстояние до B, то есть число шагов по горизонтали и вертикали, будь поле пустым. Она согласована: шаг меняет её ровно на единицу, а стоит не меньше единицы. Числа в клетках — f; под полем — содержимое кучи по возрастанию f.

A* достаёт 77 клеток, Дейкстра на том же поле — 159, путь у обоих стоит 31. Пройдите поиск по шагам с начала. Сперва A* идёт прямо на B и упирается в стену «чаши», открытой в сторону старта. Пока f клеток внутри чаши меньше, чем у клеток на обходе, он заполняет её целиком и только потом выходит в обход. Это главная слабость подсказки, которая не знает о стенах: вогнутое препятствие на пути к цели. Чем глубже чаша, тем больше лишней работы. Выберите «Лабиринт» — там стены отбирают у A* почти весь выигрыш: 123 клетки против 136 у Дейкстры.

Включите «Манхэттен × 3»: подсказка завышает, A* летит к цели почти не оглядываясь и на «Болоте» прокладывает путь прямо через топь. Он стоит 41 вместо 31. Об этом — в разделе о хороших и плохих подсказках.

Код

Тот же уровень в программе. Куча хранит пары (f, клетка), словарь g — лучшую известную цену пути, множество settled — клетки, которые уже достали. Программа печатает поле: запятые — где побывал поиск, звёздочки — найденный путь.

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

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

  hint                  settled  route, m
  zero (Dijkstra)          1422      3786
  straight line             209      3786
  straight line x1.5         50      3796
  straight line x2           38      3794
  manhattan                 123      3792
  8 landmarks                93      3786
  exact distance             40      3786

Последняя строка — подсказка, которая знает точное расстояние до финиша: для неё программа заранее пустила Дейкстру от базара. С ней A* достаёт 40 перекрёстков — ровно те, через которые проходит путь, и ни одного лишнего. Это предел того, что может дать подсказка, и всё между 1422 и 40 — вопрос о том, насколько хорошо подсказка знает город.

Хорошие и плохие подсказки

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

По прямой: в среднем 1080 перекрёстков против 4038 у Дейкстры, в 3,7 раза меньше, и ни одного неверного маршрута. Это граница, ниже которой без знания города не опуститься.

Манхэттен. Центр Алматы расчерчен почти по сторонам света, и сумма шагов по горизонтали и вертикали кажется естественнее прямой. Подсказка действительно сильнее — 443 перекрёстка, — но она не меньше прямой, а на косых улицах больше настоящего расстояния. Если финиш — Зелёный базар, она завышает у 4515 перекрёстков из 7909. Итог: 38 маршрутов из 40 длиннее кратчайших, худший — на 10,9 %. Быстрота куплена неправильными ответами, и заранее не узнать, где именно.

По прямой с весом. Иногда неправильность можно купить сознательно, с гарантией. Ира Поль в 1970 году изучал, что будет, если придать подсказке больший вес: f = g + w · h при w > 1. Поиск жаднее тянется к цели и достаёт меньше вершин, а ошибка ограничена.

На 40 маршрутах вес 1,5 даёт 156 перекрёстков вместо 1080 и худшую ошибку 10,3 % при гарантии 50 %, вес 2 — 110 перекрёстков и 21,1 % при гарантии 100 %. Почти все маршруты чуть длиннее кратчайших, но зато известно, насколько хуже они быть не могут. Так поступают, когда ответ нужен быстро, а лишние проценты не страшны: в играх, в роботах, в планировщиках.

Ориентиры. Подсказка по прямой знает геометрию, но не знает дорог. Знание дорог можно приготовить заранее. Выберем несколько перекрёстков-ориентиров L и один раз посчитаем Дейкстрой расстояния от каждого из них до всех перекрёстков. По неравенству треугольника d(L, B) ≤ d(L, v) + d(v, B) и d(L, v) ≤ d(L, B) + d(B, v), поэтому d(v, B) ≥ |d(L, B) − d(L, v)|. Это нижняя оценка, и она согласована: на ребре длины c расстояние от ориентира меняется не больше чем на c. Максимум таких оценок по всем ориентирам — тоже согласованная подсказка. Её особенно хорошо видно, когда ориентир стоит «позади» финиша: тогда оценка почти точна. В 2005 году Эндрю Голдберг и Крис Харрельсон назвали этот приём ALT — A*, ориентиры (landmarks) и неравенство треугольника. Восемь ориентиров по краям Алматы дают 342 перекрёстка в среднем — втрое меньше, чем прямая, и все маршруты кратчайшие. Цена — восемь массивов расстояний на весь город и восемь запусков Дейкстры заранее.

Переключите сцену и график на «Секунды», где складываются минуты в пути при условных скоростях улиц. Подсказка по прямой здесь делит расстояние на скорость самой быстрой дороги, 80 км/ч, — иначе она могла бы завысить. Но почти все улицы медленнее, и подсказка становится слабой: 2372 перекрёстка из 4030, выигрыш всего в 1,7 раза. Ориентиры посчитаны в секундах и знают, где медленно, — 372 перекрёстка, в 10,8 раза меньше Дейкстры. Навигатору нужно именно время, и поэтому геометрическая подсказка в навигаторах уступает подсказкам, построенным по самому графу.

Сколько это стоит

В худшем случае A* не лучше Дейкстры: подсказка может ничего не подсказывать (h = 0), и тогда это просто Дейкстра — O((V + E) log V) времени. С согласованной подсказкой каждую вершину достают не больше одного раза, так что хуже Дейкстры он тоже не становится, если не считать времени на вычисление самой подсказки. Памяти нужно O(V): расстояния и куча для всех вершин, до которых дошла волна.

На практике всё решает подсказка, и выигрыш — постоянный множитель: эллипс меньше круга во столько-то раз, но оба растут как квадрат расстояния. Замер на тех же улицах: старт в центре города, финиши на расстоянии от 1 до 8 км по дорогам, по шесть на каждое расстояние.

Дейкстра растёт с наклоном около 2: финиш вдвое дальше — работы вчетверо больше, как у площади круга. У A* наклон меньше и разброс больше: форма эллипса зависит от того, насколько петляет конкретный маршрут. По времени A* выигрывает чаще всего в 3–6 раз, а на самом коротком маршруте, в километр, на Go даже проигрывает: выигрыш меньше, чем по числу вершин, потому что на каждого соседа A* ещё считает подсказку с квадратным корнем, а на коротких маршрутах вершин так мало, что выигрывать почти нечего.

Память становится главной бедой там, где вершин не тысячи, а триллионы, — в головоломках и планировании. A* хранит всё, до чего дошёл, и на пятнашках 4 × 4 это сотни тысяч позиций даже для средних задач. Ричард Корф в 1985 году предложил IDA*: поиск в глубину, который отсекает ветки, где g + h больше порога, и поднимает порог, пока не найдёт решение. Памяти ему нужно на одну ветку, а находит он то же, что A*. Обе идеи пригодятся во второй задаче.

Где работает

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

Маршрутизаторы. Подсказка по прямой для дорожной сети в минутах слаба, это видно в сцене. В GraphHopper есть режим hybrid — A* с ориентирами, тот самый ALT; в примере его настроек 16 ориентиров. Он медленнее иерархий сжатия, но позволяет менять веса дорог от запроса к запросу. Самые быстрые навигаторы сочетают предподсчёт и поиск: волна — всё та же Дейкстра или A*, но на заранее переработанном графе. Ещё один способ сузить волну — пустить две навстречу: двунаправленный поиск.

Головоломки и планирование. Пятнашки, кубик Рубика, планы действий робота — графы, которые никто не хранит целиком: соседей вычисляют на ходу, как в пространстве состояний поиска в ширину. Здесь A* и IDA* с хорошими подсказками — основной инструмент поиска оптимальных решений.

Робот, которому нужна была дорога

В 1966–1972 годах в исследовательском институте SRI строили Shakey — первого мобильного робота, который рассуждал о собственных действиях и сам их планировал. Ему нужно было прокладывать путь в обход препятствий, и в 1968 году Питер Харт, Нильс Нильсон и Бертрам Рафаэль напечатали статью «A Formal Basis for the Heuristic Determination of Minimum Cost Paths». В пересказах этой истории Нильсон сначала предлагал вести поиск только по подсказке — оценке расстояния до цели, Рафаэль предложил складывать её с уже пройденным путём, а Харт придумал понятия, которые сейчас называют допустимостью и согласованностью, и доказал, что при них алгоритм находит кратчайший путь и не делает лишней работы.

В самой статье слово «допустимый» относится не к подсказке, а к алгоритму: допустимым назван алгоритм, который гарантированно находит оптимальный путь, а A* доказан допустимым, если подсказка — нижняя оценка. Согласованность там названа «предположением о согласованности» и записана как неравенство треугольника. Откуда звёздочка в названии, толком не записано. В 2020 году Джим Дэвис и Джефф Хахтел расспросили авторов, и по воспоминаниям Рафаэля имя было «быстрым, простым и довольно произвольным»: прежний вариант Нильсона назывался алгоритмом A.

Задачи

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