Легче всего кодировать алгоритм для кубика Рубика?
Что было бы относительно простым алгоритмом для написания кода на Java для решения кубика Рубика. Эффективность также важна, но вторична.
7 ответов
Самый простой нетривиальный алгоритм, который я нашел, это:
http://www.chessandpoker.com/rubiks-cube-solution.html
Это не выглядит слишком сложно, чтобы закодировать. Ссылка, упомянутая в ответе Янника М., тоже выглядит неплохо, но решение " перекрестного" шага может показаться мне более сложным.
Существует множество реализаций решателя с открытым исходным кодом, на которые вы могли бы взглянуть. Вот реализация Python. Этот Java-апплет также включает решатель, и исходный код доступен. Есть также решатель Javascript, также с загружаемым исходным кодом.
Ответ Энтони Гатлина дает отличную оценку о пригодности Пролога для этой задачи. Вот подробная статья о том, как написать свой собственный решатель Пролога. Используемая им эвристика особенно интересна.
Выполняйте случайные операции, пока не получите правильное решение. Самый простой алгоритм и наименее эффективный.
Возможно, захотите проверить: http://peter.stillhq.com/jasmine/rubikscubesolution.html
Имеет графическое представление алгоритма для решения кубика Рубика 3x3x3
Я понимаю, что ваш вопрос связан с Java, но с практической точки зрения такие языки, как Prolog, гораздо лучше подходят для решения таких задач, как решение кубика Рубика. Я предполагаю, что это, вероятно, для класса, и у вас может не быть свободы выбора в выборе инструмента.
Для справки, вы, безусловно, можете посмотреть на эту реализацию Java. -> Использует двухфазный алгоритм для решения кубика Рубика. И попробовал этот код, и он работает также.
Вы можете сделать это, выполнив BFS(Breadth-First-Search). Я думаю, что реализация не так сложна (это один из самых простых алгоритмов в категории графов). Делая это со структурой данных, называемой очередью, вы действительно будете работать над созданием дерева BFS и находить так называемый кратчайший путь от заданного условия до состояния желания. Недостаток этого алгоритма состоит в том, что он недостаточно эффективен (без какой-либо модификации, даже для решения куба 2x2x2 необходимое количество времени составляет ~5 минут). Но вы всегда можете найти некоторые приемы, чтобы повысить скорость.
Если честно, это одно из домашних заданий курса под названием " Введение в алгоритм" из MIT. Вот ссылка на домашнее задание: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps6.pdf. У них есть несколько библиотек, которые помогут вам визуализировать это и избежать ненужных усилий.
Одним из решений является, я думаю, одновременно запустить все возможные маршруты. Это звучит глупо, но вот логика - более 99% возможных схваток будут решены менее чем за 20 ходов. Это означает, что, хотя вы перебираете огромное количество возможностей, вы все равно будете делать это в конце концов. По сути, это будет работать, если вы сделаете свой первый шаг в качестве зашифрованного куба. Тогда у вас будут новые кубы, хранящиеся в переменных для каждого возможного хода в этом первом кубе. Для каждого из этих новых кубов вы делаете то же самое. После каждого возможного перемещения проверьте, завершено ли оно, и если да, то это решение. Здесь, чтобы убедиться, что у вас есть решение, вам понадобится дополнительный бит данных в каждом кубе Рубика, сообщающий о шагах, проделанных для достижения этой стадии.