Решение кубика Рубика программно
Я пытаюсь разработать программу для решения кубика Рубика в C. Я использовал для этого технику обратного слежения. Это очень долгий процесс, и он требует много итераций, поэтому я не могу его решить.
Пожалуйста, дайте мне советы о том, как решить эту проблему более эффективно - например, о других методах или о том, как откатиться назад. В Google я нашел много ярлыков для решения этой проблемы, но я не хочу решать это с помощью ярлыков.
5 ответов
Почему бы не использовать ориентированное на человека решение и запрограммировать это.
Вам нужно какое-то сопоставление с образцом, но это будет не так сложно. (Кроме того, есть программы, решающие 1000x1000x1000).
Основная идея состоит в том, чтобы работать поэтапно:
- Первый слой
- Второй слой
- Третий слой
Для каждого слоя вы реализуете пару алгоритмов, которые превращают шаблон X в шаблон X'. Каждый шаг в фазе должен приблизить куб к решению. Вы можете сделать это, добавив значение к каждому шаблону (где более высокие значения задаются для более неразрешенных кубов). Вы также можете добавить сложность (например, количество ходов), чтобы вы могли выбрать алгоритм, основанный на получении наилучшего значения за сложность (или достичь наилучшего результата с наименьшим количеством поворотов).
Самое интересное в этом подходе состоит в том, что вы можете добавлять новые алгоритмы, если хотите, и проверять, как часто они используются. Таким образом, вы можете проверить полезность каждого алгоритма.
Если вы действительно хотите заработать эти geekpoints, создайте отдельный язык для описания алгоритмов и шаблонов, которые они решают.
Есть много алгоритмов для решения проблемы Рубика, но вы можете обратиться к этому оптимальному http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik%27s_Cube
Я не уверен, что понимаю вашу проблему и что вы подразумеваете под ярлыками. Если вы используете какой-то метод динамического программирования для решения кубика рубика, вам нужно убедиться, что вы смотрите на достаточно большие шаги вперед, чтобы найти решение. Я считаю, что если вы поддерживаете только 2 типа движений (вращение вправо, вращение вверх), вам нужно посмотреть на 12 шагов (не уверен), прежде чем принимать решение по каждому шагу, чтобы обеспечить решение.
Если вы делаете что-то подобное и обнаружили, что у вас недостаточно места в памяти, имейте в виду, что вам нужно только сохранить путь, который вы проходите, чтобы принять решение о правильном решении (а не обо всем дереве).
Я успешно использовал этот подход для решения кубика Рубика в Java, поэтому у C не должно быть никаких проблем (в части использования памяти).
Кубик Рубика имеет размер пространства состояний порядка 265. Алгоритм обратного отслеживания, который просматривает пространство состояний вслепую, может потребоваться исследовать большую часть пространства состояний, прежде чем он найдет решение, поэтому ясно, что простой алгоритм обратного отслеживания не будет работать очень хорошо. Но тогда эта проблема уже решалась много раз. Смотрите, например, http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf
Если вас не волнует количество задействованных ходов, вот способ разделить пространство состояний так, чтобы ваш метод bruteforces работал.
Нахождение решения Rubix Cube для чайников
- Сначала перебейте все грани рубикса, НО углы на места
- затем найдите ходы, которые позволяют инвариантности этого аспекта (например, (fgf-1.g-1)^3). Два хода на самом деле достаточно. Чтобы найти их, рассмотрим перестановку для угловых и неугловых субкубов, а затем итерируем ppcm длины угловых циклов, чтобы получить и инвариантную по углам)
- Используйте алгоритм обратного отслеживания, чтобы расположить углы (но они все еще требуют поворота, чтобы выровнять цвета)
- Найдите магические движения, которые заставляют куб на одном отрезке вращаться вместе. Там нет движения, которое