5x5 Sliding Puzzle Решение для быстрого и легкого перемещения

Question

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

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

Есть ли какие-либо специфические c алгоритмы, которые могут выполнить sh это?

Answer 1

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

Интересные факты, рассмотренные в Грэм Кендалл , Обзор NP-Complete загадок , 2008:

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

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

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

Answer 2

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

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

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

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

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

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

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

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

Этот алгоритм был впервые описан Ian Parberry в статье под названием Алгоритм в реальном времени для (n2 - 1) -пазла в 1995 г. Я думаю , что DSolving: новый и эффективный интеллектуальный алгоритм для крупномасштабные скользящие пазлы от GuiPing Wang и Ren Li описывают еще более эффективный метод таблицы поиска, но поскольку статья еще не доступна бесплатно, я еще не изучал ее.

Answer 3

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