8-puzzle — это то, что вы пишете первым делом, когда узнаёте про эвристический поиск. Достаточно маленький, чтобы почти любой подход работал, достаточно большой, чтобы плохие подходы заметно проигрывали хорошим. Эта статья проходит стандартное решение сверху донизу.
Состояние
Представьте доску как массив из девяти целых, индексированных 0..8 в строковом порядке:
позиции: индексы:
1 2 3 0 1 2
4 5 6 ↔ 3 4 5
7 8 _ 6 7 8
Пустая клетка — это какой-то sentinel; обычно 0. Целевое состояние — [1, 2, 3, 4, 5, 6, 7, 8, 0].
Ходы
Из позиции с пустой клеткой в индексе e можно поменять пустую с её ортогональными соседями: e-3 (выше), если не в верхней строке; e+3 (ниже), если не в нижней; e-1 (слева), если не в крайнем левом столбце; e+1 (справа), если не в крайнем правом.
Функция neighbors(state) возвращает до четырёх состояний, достижимых за один ход.
Эвристика: манхэттенское расстояние
Для каждой плитки (игнорируя пустую) посчитайте расстояние по строкам плюс расстояние по столбцам от её текущей позиции до целевой. Сложите по плиткам. Эта сумма — нижняя оценка на число оставшихся ходов, потому что каждая плитка должна пройти как минимум столько.
В псевдокоде:
h(state) = sum по плиткам t:
abs(row(current) - row(goal)) + abs(col(current) - col(goal))
Манхэттенское расстояние допустимо (никогда не переоценивает) и консистентно (удовлетворяет неравенству треугольника). Оба свойства важны для A*.
A* в двенадцати строках
A* поддерживает приоритетную очередь состояний, упорядоченную по f = g + h, где g — глубина (сделано ходов), а h — эвристическая оценка оставшихся ходов. На каждой итерации: достать состояние с минимальным f, развернуть, вставить соседей с обновлённым f.
open = priority_queue()
open.push(start, f=h(start))
came_from = {}; g = {start: 0}
while open is not empty:
state = open.pop()
if state == goal: return reconstruct_path(came_from, state)
for n in neighbors(state):
tentative_g = g[state] + 1
if n not in g or tentative_g < g[n]:
g[n] = tentative_g
came_from[n] = state
open.push(n, f=tentative_g + h(n))
Это весь солвер. Реализуйте h, реализуйте neighbors, и вы решаете любой 8-puzzle.
Производительность
A* с манхэттенским расстоянием решает любую 8-puzzle за несколько сотен микросекунд, разворачивая от нескольких сотен до нескольких тысяч состояний на самых сложных инстансах. Пространство состояний достаточно мало, что A* доминирует над IDA* на этом размере — A* правильный выбор для 3×3, IDA* перехватывает на 4×4 и больше.
Типичные ошибки
Три вещи, которые вы сделаете неправильно с первой попытки:
Хеширование состояния. Кортежи Python хешируются красиво; массивы int в Java — нет. Какой бы язык вы ни использовали, состояние должно быть хешируемым, чтобы closed/open множества работали. Распространённый трюк — кодировать состояние из 9 плиток в одно 32-битное целое (по 4 бита на клетку, так как клетки от 0 до 8).
Забыть про проверку чётности. Если вы генерируете случайную 8-puzzle перемешиванием, в половине случаев пазл нерешаем, и A* исследует весь полупространство в 181 440 состояний, ища несуществующий путь. Добавьте быструю проверку чётности перед A* или генерируйте, идя назад от цели.
Считать пустую плиткой в эвристике. Манхэттенское расстояние суммируется по реальным плиткам только. Включение пустой раздувает эвристику и ломает допустимость (можно «починить» пустую бесплатно одним ходом).
За пределами манхэттенского
На 8-puzzle можно лучше манхэттенского, но не намного:
- Linear conflict — если две плитки в одной строке обе принадлежат своей целевой строке, но в неправильном порядке, им понадобится как минимум два дополнительных хода, чтобы разойтись. Добавьте 2 на конфликт. Улучшает Manhattan на 5–15%.
- Базы шаблонов — предварительный расчёт оптимальной стоимости по подмножествам плиток. Огромная стоимость памяти ради микро-ускорения на 8-puzzle. Стоит того для 15-puzzle солверов, не здесь.
Для 8-puzzle обычный Manhattan + linear conflict — практичный оптимум.
Что строить дальше
Если вы написали 8-puzzle солвер, естественные расширения:
- Солвер 15-головоломки с IDA* + walking distance. Те же базовые идеи, более глубокий поиск. (Гид здесь.)
- Солвер общей N-головоломки с базами шаблонов. Проект на выходные.
- Тест решаемости — функция в 30 строк, возвращающая true, если доска достижима из цели. Полезно для разработки приложений. (На основе теоремы о чётности.)
8-puzzle мал. Техники, которые вы освоите на нём, масштабируются всю дорогу вверх.