Манхэттенская эвристика — самая используемая эвристика в эвристическом поиске за всё время. Неформально введена в 1960-х для 15-головоломки, формализована в работе про A* 1968 года, всё ещё первое, что преподаёт каждый учебник по ИИ. Эта статья — о том, почему она работает, что делает хорошо, и где перестаёт хватать.
Определение
Для N×N слайд-пазла, для каждой плитки (игнорируя пустую), сосчитайте:
distance = | row_current − row_goal | + | col_current − col_goal |
Сложите по всем плиткам. Эта сумма — манхэттенское расстояние текущей доски до цели.
Почему «манхэттенское»? Улицы Манхэттена — регулярная сетка. Чтобы попасть с одного угла на другой, идёте столько-то кварталов на восток-запад плюс столько-то на север-юг. Срезать по диагонали нельзя. Общее число пройденных кварталов — это манхэттенское расстояние, оно же taxicab distance или L¹-норма.
Для плитки та же логика: она может двигаться горизонтально или вертикально на одну клетку за ход, но не по диагонали. Минимальное число ходов, чтобы попасть из текущей позиции в нужную, — это расстояние по строкам плюс расстояние по столбцам.
Допустимость
A* требует, чтобы эвристика была допустимой: никогда не переоценивала реальное число оставшихся ходов. Если эвристика переоценивает, A* может отсечь оптимальный путь и вернуть субоптимальное решение.
Манхэттенское расстояние допустимо потому что:
- Каждая отдельная плитка должна пройти как минимум свою строчную+столбцовую дистанцию, поскольку ходы — это единичные шаги по строке или столбцу.
- Сумма по всем плиткам не превысит реального числа ходов, потому что каждый ход продвигает ровно одну плитку ровно на одну клетку. (Двигает ещё и пустую, но её мы не считаем.)
- На самом деле реальное расстояние как минимум манхэттенское, потому что плитки часто приходится двигать в сторону, чтобы другие могли пройти — но никогда не меньше.
Итак, Manhattan ≤ реальное. Допустима.
Консистентность
Более сильное свойство: консистентность, иногда называемая монотонностью эвристики. Эвристика консистентна, если для каждого состояния s и каждого его наследника s' через ход m:
h(s) ≤ cost(m) + h(s')
По-русски: значение эвристики не может упасть больше чем на единицу за один ход.
Манхэттенское расстояние консистентно потому что одиночный ход меняет манхэттенское расстояние ровно на +1 или −1. (Одна плитка двигается на одну клетку, поэтому её вклад в эвристику меняется на ±1; вклады остальных не меняются.)
Консистентность важна, потому что гарантирует: A* никогда не переоткрывает уже закрытое состояние. Реализации не нужно обрабатывать случай неконсистентности — это упрощает код и доказательства.
Почему так хорошо работает на практике
Три конкретные свойства:
Дёшево вычисляется. O(N²) на доску — сумма по плиткам, каждый вклад за константное время. h(s) считается за микросекунды на любом современном компьютере.
Достаточно плотна, чтобы глубоко обрезать. Для 15-головоломок Manhattan в среднем 75–90% от реального расстояния. A* с такой плотной эвристикой исследует крошечную долю пространства состояний.
Хорошо комбинируется с linear conflict. Добавление 2 ходов на «linear conflict» (две плитки в одной строке, обе принадлежащие этой строке, но в неправильном порядке) даёт строго более плотную эвристику при маргинальной вычислительной цене.
Где не хватает
Манхэттенское расстояние обращается с плитками так, будто они могут свободно проходить друг через друга. Не могут. Глубочайшая слепая зона:
Конфликты в столбце или строке. Если плитки 2 и 3 обе в строке 1, но в неправильном порядке, Manhattan даёт им прямолинейные расстояния и ничего не замечает. В реальности одну надо поднять из строки, пропустить другую, и поднятую вернуть. Это как минимум 2 лишних хода, которых Manhattan не видит. Linear conflict это латает.
Структура «walking». Manhattan игнорирует, как плитки соотносятся друг с другом внутри строки или столбца, когда все они принадлежат этой строке или столбцу. Строка из четырёх плиток в неправильной перестановке требует нескольких «свопов-строки» — структуры, которую ловит walking distance.
Взаимодействия непересекающихся подмножеств. Для любого непересекающегося разбиения плиток оптимальная стоимость перестановки каждой части на места — более плотная нижняя оценка, чем Manhattan (что есть разбиение в синглетоны). Аддитивные базы шаблонов это эксплуатируют.
Прогрессия: Manhattan → Manhattan + linear conflict → walking distance → базы шаблонов. Каждый — строгое улучшение.
Почему большим доскам нужно больше
Manhattan в среднем 75–90% от реального для 15-puzzle. Для 24-puzzle — около 65%. Для 35-puzzle — около 55%.
Причина: с ростом доски конфликты плиток и «walking-структура» становятся важнее относительно прямолинейных расстояний. Manhattan, игнорируя обе, недооценивает сильнее на больших досках.
Поэтому базы шаблонов по сути обязательны для решения 24-puzzle и 35-puzzle. Manhattan нормально для 15-puzzle и 8-puzzle, но теряет слишком много информации на больших размерах.
Геометрическая интуиция
Хороший способ думать о манхэттенском расстоянии: представьте плоскость с одной плиткой. Множество точек, в которые плитка может дойти за k ходов, — это ромб стороны k: точки на манхэттенском расстоянии ≤ k. (Евклидов аналог был бы кругом радиуса k.)
Манхэттенское расстояние — естественная геометрия сетки-движения. Когда модель движения ограничена шагами по сетке, манхэттенское расстояние — это геометрия; евклидово — иррелевантно.
Что это значит для разработчиков приложений
Если пишете кнопку подсказки для слайд-пазл-приложения и хотите, чтобы работала в миллисекундах:
- 3×3 — Manhattan + linear conflict достаточно. A* исследует десятки состояний; завершается за микросекунды.
- 4×4 — Manhattan + linear conflict достаточно быстро для подсказки (один ход, не полное оптимальное решение). Для полного оптимального — walking distance правильный выбор.
- 5×5+ — Базы шаблонов. Manhattan не достаточно, чтобы уложиться в бюджет времени кнопки подсказки.
Slide Puzzle использует Manhattan + linear conflict для кнопки подсказки на 3×3 и 4×4, walking distance для калибровки сложности 4×4, и базу шаблонов 5+5+5+9 для калибровки 5×5 и 6×6. Манхэттенская эвристика — основание всех.
Финальная интуиция
Манхэттенская эвристика — то, что вообще делает слайд-пазлы поисковыми. Без неё A* и IDA* выродятся в BFS — а BFS не завершается на 15-головоломке за время жизни Вселенной.
Эта эвристика — одна строка кода, превращающая нерешаемую задачу в миллисекундное вычисление. Стоит понимать хорошо.