Walking Distance
22 февраля 2012
Введение
Walking Distance – эвристика для решения головоломки "15" методом IDA*, разработанная программистом из Японии Ken'ichiro Takahashi. Эта эвристика позволяет определять сравнительно высокую оценку снизу длины оптимального решения. В случае головоломки 4 × 4, максимальное значение, достигаемое этой эвристикой, равно 70. Для сравнения, максимальное значение эвристики "Манхэттенское расстояние" равно 60.
Как оказалось, эвристика Walking Distance может быть применена к любой головоломке m × n. В результате модификации эвристики была получена новая оценка снизу для головоломки 5 × 5, равная 140 ходам в метрике STM. Именно это значение возвращает эвристика WD для следующей конфигурации (используется классическая целевая конфигурация):
| 24 | 23 | 22 | 21 |
| 20 | 19 | 18 | 17 | 16 |
| 15 | 14 | 13 | 12 | 11 |
| 10 | 9 | 8 | 7 | 6 |
| 5 | 4 | 3 | 2 | 1 |
Tomas Rokicki, программист из Пало-Альто (Калифорния), написал программу, выполняющую поиск оптимального решения приведённой конфигурации с использованием эвристики WD. После 10 дней работы программа завершила поиск на глубине 150, но так и не нашла решения. Таким образом, текущая оценка снизу числа Бога головоломки 5 × 5 в метрике STM равна 152 ходам. Дополнительную информацию можно найти в [2].
Приведённая конфигурация имеет решение, содержащее 156 ходов (STM). Это решение найдено с использованием промежуточной целевой конфигурации, и пока неизвестно, является ли оно оптимальным.
Эта страница содержит русскоязычный перевод оригинального описания эвристики Walking Distance.
На этой странице будет размещено более подробное описание эвристики для головоломки 4 × 4 (пока выложено описание на английском).
Литература / См. также
- Ken'ichiro Takahashi's Computer & Puzzle page
- Domain of the Cube Forum
- Herbert Kociemba's Fifteen Puzzle Optimal Solver
– действующая реализация IDA* с использованием (по выбору) MD, WD, PDB
| 