Раздвижная головоломка 5x5 Быстрое и малоходовое решение

Я пытаюсь найти способ программно решить скользящую головоломку из 24 частей за разумное количество времени и ходов. Вот пример решенного состояния в головоломке, которую я описываю:

5x5 Решенная скользящая головоломка

Я уже обнаружил, что алгоритм IDA* достаточно хорошо работает для решения головоломки из 15 элементов (сетка 4x4). Алгоритм IDA* способен найти наименьшее количество ходов для любой скользящей головоломки 4x4 за очень разумное время. Я запустил адаптацию этого кода для тестирования раздвижных головоломок 4x4 и смог значительно сократить время выполнения с помощью PyPy. К сожалению, когда этот код адаптирован для скользящих головоломок 5x5, он работает ужасно медленно. Я запускал его более часа и, в конце концов, просто сдался, увидев, как он закончился, тогда как на сетках 4x4 он работал всего несколько секунд. Я понимаю, что это связано с тем, что количество узлов, которые необходимо искать, увеличивается экспоненциально по мере увеличения сетки. Однако я не ищу оптимального решения скользящей головоломки 5x5, а только решение, близкое к оптимальному. Например, если бы оптимальное решение для данной головоломки составляло 120 ходов, то меня удовлетворило бы любое решение, которое меньше 150 ходов и может быть найдено за несколько минут.

Существуют ли какие-либо конкретные алгоритмы, которые могут это сделать?


python pypy algorithm sliding-tile-puzzle
person Bob Smith    schedule 17.03.2020    source источник
comment
Комментирую, так как я не знаю, сработает ли это, но вы можете попробовать IDA*, чтобы быстро исправить две верхние строки, а затем IDA* из любой полученной конфигурации решить три нижние, не перемещая верхнюю.   -  person David Eisenstat    schedule 19.03.2020

Ответы (3)


arrow_upward
5
arrow_downward

Было доказано, что нахождение наименьшего количества ходов n-головоломки является NP-полным, см. Дэниел Ратнер и Манфред Вармут, Головоломка (n2-1) и связанные с ней проблемы перемещения, Журнал символических вычислений (1990 г.). ) 10, 111-137.

Интересные факты рассмотрены в Graham Kendall, A Survey of NP-Complete Головоломки, 2008 г.:

  • Загадку 8 можно решить с помощью алгоритма A*;
  • Загадку 15 нельзя решить с помощью алгоритма A*, но алгоритм IDA* может;
  • Оптимальные решения 24-головоломки не могут быть сгенерированы за разумное время с использованием алгоритма IDA*.

Поэтому остановка вычислений для изменения методологии была правильным решением.

Кажется, существует доступный алгоритм за полиномиальное время, который может находить неоптимальные решения, см. Иан Парберри, Решение (n^2−1)-головоломки с 8/3n^3 ожидаемыми ходами, Алгоритмы 2015, 8(3), 459 -465. Это может быть то, что вы ищете.

person jlandercy    schedule 22.03.2020
comment
Знаем ли мы, что ее нельзя решить с помощью A*/IDA*, или возможно, что сработает лучшая эвристическая функция стоимости? - person Hans Olsson; 25.03.2020
comment
Я собираюсь присудить награду за этот ответ, а также принять его, потому что я думаю, что это в целом самый качественный ответ, однако я хотел бы, чтобы я мог присудить награду за несколько ответов, потому что я получил полезные советы от нескольких. Я попробовал алгоритм, упомянутый в этом ответе, и, хотя он работал довольно быстро, к сожалению, в среднем потребовалось больше ходов, чем я надеялся. В итоге я сделал что-то похожее на то, что предложил @Martijn Pieters, и вместо этого сократил доску до головоломки 4x4 довольно неэффективным способом, а затем просто запустил IDA * на оставшейся части. - person Bob Smith; 26.03.2020
comment
С этим решением я смог получить немного лучший средний случай и гораздо лучший лучший случай с точки зрения ходов. В целом, я хотел бы поблагодарить всех за их решения и предложения, поскольку все они были полезны по-своему и предоставили разные идеи. - person Bob Smith; 26.03.2020

arrow_upward
4
arrow_downward

IDA* прекрасно работает вплоть до головоломки 4x4, потому что это «всего» 16! (20 922 789 888 000) возможных состояний. В головоломке 5x5 их ​​25! (15 511 210 043 330 985 984 000 000) возможных состояний, что в 740 000 000 раз больше.

Вам нужно переключать стратегии. «Самый простой» метод решает головоломку в верхнем ряду, а затем сначала в левом столбце, несколько раз, пока не получится головоломка 3x3, которую можно легко решить с помощью существующих методов.

Решение головоломки включает в себя 3 разных этапа, между которыми вы чередуетесь:

  1. Решите верхний ряд (переместите фишки для столбцов 1 - N-2 на место, затем переместите фишку для столбца N-1 в столбец N, фишку для столбца N в столбец N, но на один ряд ниже, закончите ряд)
  2. Решите левый столбец (переместите детали для рядов 2 - N-2 на место, затем переместите деталь для ряда N-1 в ряд N, деталь для ряда N в ряд N, но на один столбец вправо, закончите столбец)
  3. (осталось 2 строки по 3 столбца): используйте A*, чтобы решить остаток.

Таким образом, фазы 1 и 2 чередуются, пока вы не сможете запустить фазу 3; после решения 5 верхних плиток (фаза 1) вы решаете 4 крайние левые плитки в других рядах (фаза 2), затем верхний ряд оставшейся части головоломки (4 плитки, фаза 1), затем левый столбец ( 3 плитки, фаза 2), затем решите фазу 3. Этапы 1 и 2 в основном идентичны, отличается только ориентация, а для фазы 2 первая плитка уже на месте.

Этапы 1 и 2 легко решаются с помощью справочных таблиц, поиск не требуется; вы перемещаете определенные плитки и не заботитесь ни о чем другом:

  • Найдите нужную плитку
  • Получите зазор рядом с плиткой (это зависит от направления движения, какая сторона лучше)
  • Переместите плитку на место; есть стандартные ходы, которые перемещают плитку в любом направлении (5 для вертикальных или горизонтальных ходов, 6 для диагональных).

Это не дает вам кратчайшего пути к решению, но без поиска состояния проблема строго ограничена и известен наихудший сценарий. Решение первой строки и столбца головоломки 5x5 занимает не более 427 ходов таким образом и 256 ходов для следующей строки и столбца.

Этот алгоритм был впервые описан Яном Парберри в статье под названием Настоящий алгоритм для (n2 − 1)-головоломки в 1995 году. Я думаю, что DSolving: новый и эффективный интеллектуальный алгоритм для крупномасштабных скользящих головоломок от GuiPing Wang и Жэнь Ли по-прежнему описывает более эффективный метод интерполяционной таблицы, но, поскольку документ еще не доступен бесплатно, я еще не изучал его.

person Martijn Pieters    schedule 22.03.2020

arrow_upward
1
arrow_downward

Изменение двух символов, которое может помочь, заключается в умножении эвристики на 2 (или на другую константу). Это уже недопустимо, но найденное решение будет в 2 раза меньше оптимального. Этот трюк называется взвешенный A*/статический взвешивание.

person David Eisenstat    schedule 24.03.2020