IDA * - один из лучших алгоритмов для решения кубика Рубика, потому что пространство состояний велико, и дубликатов не очень много, если вы правильно обрежете движение. Чтобы получить эффективный решатель, вам нужно обрезать ход и хорошую эвристику. Как правило, есть три движения на лицо - 90 градусов вперед / назад и 180 градусов. С 6 гранями есть 18 ходов.
Простое сокращение хода: если вы выполняете простое сокращение ваших ходов, сохраняя один ход истории, вы можете уменьшить коэффициент ветвления кубика Рубика из От 18 до 15. Поскольку любое одно движение может привести к одному лицу в любой конфигурации, вы никогда не должны перемещать одно и то же лицо дважды подряд. После первого хода будет 5 граней с 3 ходами каждый = 15 ходов на каждом шаге.
Усовершенствованная обрезка ходов: пусть три грани будут «первыми» гранями, а три - тремя из них "вторые" грани, где вторые грани находятся напротив первых граней. Здесь правило состоит в том, что после перемещения первой грани вы можете переместить любую другую грань - таким образом, будет 15 ходов. Но после перемещения второго лица вы не можете снова перемещать то же лицо или противоположное первое лицо. В этом случае коэффициент ветвления равен 12. Общий коэффициент ветвления составляет около 13.
Эвристика: Базы данных шаблонов (PDB) обеспечивают хорошую эвристику для кубика Рубика. Например, вы игнорируете края, а затем исчерпывающе решаете все углы, сохраняете результаты в таблице ha sh. (Используйте идеальную функцию ha sh, и тогда будет уникальное компактное отображение, которое очень эффективно использует память.) Имеется 88 миллионов комбинаций и менее 16 значений, которые можно сохранить в 44 МБ памяти. Когда вы хотите, чтобы heuristi c для состояния, вы просто используете функцию ha sh, чтобы найти конфигурацию угла в таблице, которая содержит общее количество ходов, необходимых для решения этой конфигурации. Это допустимая (и последовательная) эвристия c для проблемы. Вдобавок к этому вы можете захотеть сделать ребра, но 12-реберный PDB занимает 500 ГБ памяти для хранения и может не уместиться в памяти. Таким образом, вы можете сделать подмножества ребер. Вы также можете использовать симметрию куба и многие другие приемы, чтобы получить лучшие значения heuristi c. Но, с хорошей параллельной реализацией IDA * и некоторыми большими PDB, вы можете оптимально решать случайные экземпляры кубика Рубика.
Существует множество исследовательских работ по топи c - я предлагаю используя Google scholar для поиска их в Интернете.
Если вы хотите начать с чего-то более простого, вот как вы можете реализовать «более простую» эвристику:
Для каждого угол / ребро в кубе, подсчитайте, сколько шагов потребуется, чтобы добраться до цели / ориентации цели самостоятельно. Добавьте это ко всем кубам.
Поскольку каждый поворот грани куба сдвигает 4 угла и 4 ребра, возьмите число из первого шага и разделите его на 8. Это затем допустимый heuristi c для задачи.
Если вы проигнорируете ориентацию, то для каждого куба потребуется не более двух ходов, чтобы достичь своей целевой позиции, что означает ваш окончательный heuristi c будет меньше, чем 2. Принимая во внимание ориентацию, вы немного увеличите ее. Таким образом, этот подход не будет особенно эффективным на практике.