Допустимость и согласованность: когда эвристике можно верить

Если ты различаешь допустимость и согласованность, знаешь, что ломается при нарушении каждой, и помнишь, что согласованность сильнее, листай до «Теперь сам».

Как думаешь, чем плоха завышенная оценка

Эвристика говорит: «отсюда до цели ещё километров десять». Прежде чем читать дальше, подумай, что случится, если на самом деле осталось два. A* сравнивает f = g + h у разных вершин - какую вершину он отложит и чем это грозит ответу?

На что это похоже

Прогноз времени в пути. Навигатор, который занижает («доедете за час», а выходит полтора), заставит тебя рассмотреть больше вариантов, но верный маршрут ты не потеряешь: любой недооценённый вариант рано или поздно будет проверен. Навигатор, который ЗАВЫШАЕТ («туда три часа», а на деле час), отговорит от правильной дороги вовсе - ты поедешь другой, потому что поверил прогнозу.

Механизм: два свойства и что они дают

ДОПУСТИМОСТЬ (не переоценивать):
    h(v) <= d(v, цель)   для каждой вершины
    ⇒ A* находит ОПТИМАЛЬНЫЙ путь (если разрешено переоткрывать вершины)

СОГЛАСОВАННОСТЬ (монотонность):
    h(u) <= w(u, v) + h(v)   для каждого ребра,   h(цель) = 0
    ⇒ перевешенные веса w' = w + h(v) − h(u) неотрицательны
    ⇒ A* = Дейкстра: извлечённая вершина окончательна, переоткрывать не нужно
    ⇒ f вдоль любого пути не убывает (отсюда и слово «монотонность»)

согласованность ⇒ допустимость;  обратное НЕВЕРНО

Почему согласованность влечёт допустимость: идём по кратчайшему пути от v к цели и складываем неравенства h(x) <= w(x, y) + h(y) вдоль него; промежуточные h сокращаются, остаётся h(v) <= d(v, цель) + h(цель) = d(v, цель). Это та же телескопическая сумма, что и в потенциалах.

Практические эвристики почти всегда согласованы: расстояние по прямой на карте, манхэттенское расстояние на сетке с единичными шагами, сумма расстояний фишек до своих мест в пятнашках. Обычно это и не проверяют отдельно - достаточно убедиться, что эвристика получена «расслаблением» задачи: если убрать часть ограничений (разрешить ходить сквозь стены, двигаться по прямой), точное решение упрощённой задачи и будет согласованной эвристикой для исходной.

Правило

Допустимая эвристика не переоценивает остаток (h(v) <= d(v, цель)) - с ней A* даёт оптимальный ответ, но может переоткрывать вершины. Согласованная дополнительно удовлетворяет h(u) <= w(u, v) + h(v) при h(цель) = 0 - с ней перевешенные веса неотрицательны, извлечённая вершина окончательна, и A* работает ровно как Дейкстра. Согласованность влечёт допустимость, обратное неверно. Эвристика, полученная точным решением УПРОЩЁННОЙ задачи, согласована автоматически.

Разбор: что бывает при переоценке

Граф: s→a = 1, a→t = 1, s→t = 3. Настоящий кратчайший путь: s → a → t длиной 2.

Возьмём эвристику, которая завышает: h(a) = 5 (а на самом деле от a до цели 1), h(t) = 0, h(s) = 0.

кладём s: f = 0 + 0 = 0
извлекаем s, релаксируем:
    a: g = 1, f = 1 + 5 = 6
    t: g = 3, f = 3 + 0 = 3
извлекаем t (f = 3 меньше, чем 6) → ЦЕЛЬ ИЗВЛЕЧЕНА, ответ 3

Алгоритм вернул 3, хотя правильный ответ 2: завышенная оценка отпугнула его от вершины a. Это и есть цена недопустимой эвристики - потеря оптимальности.

Обрати внимание, что алгоритм при этом работал БЫСТРЕЕ: он раскрыл меньше вершин. Именно на этом размене построен «взвешенный A*». Коэффициент ε > 1 попадает ровно в одно место - в формулу приоритета: f(v) = g(v) + ε·h(v), то есть эвристику умножают на него при каждом вычислении f, а сам граф и веса не трогают. Ответ при этом гарантированно не хуже оптимального более чем в ε раз, зато находится быстрее. В играх и планировании так делают сознательно: «маршрут на 10% длиннее, но найден за миллисекунду» - нормальный инженерный выбор, если он сделан осознанно.

Разбор: допустимая, но не согласованная

Такие эвристики встречаются редко, но пример полезен: он показывает, что бывает, если написать A* «как Дейкстру», с множеством закрытых вершин, и дать ему только допустимую оценку.

Граф: s→a = 1, s→b = 3, a→b = 1, b→t = 3. Настоящий кратчайший путь - s→a→b→t весом 1 + 1 + 3 = 5; прямой путь s→b→t весит 6.

Эвристика: h(s) = 0, h(a) = 4, h(b) = 0, h(t) = 0. Она ДОПУСТИМА - настоящие расстояния до цели равны 5, 4, 3 и 0, и ни одно значение их не превышает. Но не согласована: для ребра a→b требуется h(a) <= w(a, b) + h(b) = 1 + 0 = 1, а у нас h(a) = 4.

раскрываем s:  a получает g=1, f = 1 + 4 = 5
               b получает g=3, f = 3 + 0 = 3
раскрываем b (f=3, минимум!):  закрыли b; b→t даёт g=6, f=6
раскрываем a (f=5):  a→b даёт g=2 < 3 - УЛУЧШЕНИЕ,
                     но b уже в закрытых, и улучшение отбрасывается
раскрываем t (f=6):  ответ 6

Ответ 6 вместо 5 - и заметь, никакой недопустимости в эвристике нет, сломало всё именно рассогласование. Виновата заниженная оценка у b: она пустила b вперёд с плохим g, а к моменту, когда нашёлся путь получше, вершина была уже закрыта.

Формально то же видно через перевес: вес ребра a→b становится w + h(b) − h(a) = 1 + 0 − 4 = −3 - отрицательный, а на отрицательных весах Дейкстра окончательности не гарантирует. Лечение - разрешить ПЕРЕОТКРЫТИЕ: если вершина закрыта, а потом нашёлся путь к ней дешевле, её кладут в очередь снова. В примере b вернётся в очередь с g = 2, f = 2, и ответ станет верным - 5. Оптимальность при допустимой эвристике так сохраняется всегда, но работы становится больше: вершину можно раскрывать много раз, и в специально построенных примерах число раскрытий растёт экспоненциально.

Вывод простой: если эвристика согласована, можно писать A* «как Дейкстру», с множеством закрытых вершин, и оценка остаётся O((V + E)·log V). Если только допустима - обязательно разрешай переоткрытие и не рассчитывай на ту же оценку.

Что ломается без этого

Первое: взять эвристику «примерно похожую на расстояние» без проверки на переоценку - и получить неоптимальные маршруты, которые почти всегда выглядят правдоподобно. Второе: забыть h(цель) = 0 - тогда даже правильная в остальном эвристика сдвигает приоритеты и может отправить алгоритм не туда. Третье: использовать множество закрытых вершин с допустимой, но НЕсогласованной эвристикой - ответ станет неоптимальным; либо проверяй согласованность, либо разрешай переоткрытия. Четвёртое: считать эвристику дорого (например, запускать ради неё вложенный поиск) - выигрыш съедается вычислением подсказки. Пятое: применять эвристику от координат в графе, где веса не связаны с расстоянием (например, вес - это цена, а не километры): тогда «расстояние по прямой» легко переоценит остаток и сломает оптимальность.

Зачем это в работе

Проверка «не переоцениваю ли я» - главный вопрос при вводе любой эвристики, и он же самый пропускаемый. Практичный рецепт: получай эвристику РАССЛАБЛЕНИЕМ задачи - разреши ходить сквозь препятствия, игнорируй пробки, позволь фишкам головоломки прыгать друг через друга. Точное решение упрощённой задачи никогда не переоценивает решение исходной (она ведь строго проще) и обычно оказывается ещё и согласованным. На дорожных графах так строят эвристики по ориентирам: заранее считают расстояния от нескольких «маяков» и берут оценку из неравенства треугольника - она гораздо точнее расстояния по прямой и остаётся допустимой. А знание, что переоценка даёт скорость ценой оптимальности, позволяет делать этот размен управляемо: умножил эвристику на 1.2 - получил гарантию «не хуже оптимального на 20%».

Теперь сам

Сетка, ходить можно по четырём направлениям, шаг стоит 1. Проверь на допустимость и согласованность две эвристики: (а) манхэттенское расстояние до цели; (б) манхэттенское расстояние, умноженное на 2.