Walking Distance

22 февраля 2012

Введение

Walking Distance – эвристика для решения головоломки "15" методом IDA*, разработанная программистом из Японии Ken'ichiro Takahashi. Эта эвристика позволяет определять сравнительно высокую оценку снизу длины оптимального решения. В случае головоломки 4 × 4, максимальное значение, достигаемое этой эвристикой, равно 70. Для сравнения, максимальное значение эвристики "Манхэттенское расстояние" равно 60.

Как оказалось, эвристика Walking Distance может быть применена к любой головоломке m × n. В результате модификации эвристики была получена новая оценка снизу для головоломки 5 × 5, равная 140 ходам в метрике STM. Именно это значение возвращает эвристика WD для следующей конфигурации (используется классическая целевая конфигурация):

24232221
2019181716
1514131211
109876
54321

Tomas Rokicki, программист из Пало-Альто (Калифорния), написал программу, выполняющую поиск оптимального решения приведённой конфигурации с использованием эвристики WD. После 10 дней работы программа завершила поиск на глубине 150, но так и не нашла решения. Таким образом, текущая оценка снизу числа Бога головоломки 5 × 5 в метрике STM равна 152 ходам. Дополнительную информацию можно найти в [2].

Приведённая конфигурация имеет решение, содержащее 156 ходов (STM). Это решение найдено с использованием промежуточной целевой конфигурации, и пока неизвестно, является ли оно оптимальным.

Перевод

Эта страница содержит русскоязычный перевод оригинального описания эвристики Walking Distance.

WD : 4 × 4

На этой странице будет размещено более подробное описание эвристики для головоломки 4 × 4 (пока выложено описание на английском).

Литература / См. также

  1. Ken'ichiro Takahashi's Computer & Puzzle page
  2. Domain of the Cube Forum
  3. Herbert Kociemba's Fifteen Puzzle Optimal Solver
    – действующая реализация IDA* с использованием (по выбору) MD, WD, PDB