Оптимальные решения для кубика Рубика

Перемешанный кубик Рубика

Оптимальные решения кубика Рубика — это решения, которые в некотором смысле являются самыми короткими. Есть два распространенных способа измерения длины решения. Первый заключается в подсчете количества четвертей оборотов. Второй — подсчитать количество скручиваний внешнего слоя, называемых «поворотами лица». Движение для поворота внешнего слоя на две четверти (90°) оборота в одном и том же направлении будет засчитано как два движения в метрике четверти оборота (QTM), но как один поворот в метрике торца (FTM или HTM «Метрика полуповорота»). ", или OBTM "Метрика поворота внешнего блока").

Максимальное количество поворотов лица, необходимое для сборки любого экземпляра кубика Рубика, равно 20. а максимальное количество четвертей оборотов — 26. Эти числа также являются диаметрами соответствующих графов Кэли группы кубика Рубика . В STM (метрике поворотов среза) минимальное количество поворотов неизвестно.

Существует множество алгоритмов для сборки зашифрованного кубика Рубика . Алгоритм, который решает куб за минимальное количество ходов, известен как алгоритм Бога .

Переместить обозначение

Основная статья: Кубик Рубика § Обозначение Singmaster

Для обозначения последовательности ходов кубика Рубика 3×3×3 в этой статье используется «нотация Сингмастера». который был разработан Дэвидом Сингмастером .

Ниже приведены стандартные ходы, которые не перемещают центральные кубики любой грани в другое место:

Буквы L , R , F , B , U и D обозначают поворот на четверть оборота по часовой стрелке влево, вправо, вперед, назад, вверх и вниз соответственно. Половина оборота (т.е. 2 четверти оборота в одном направлении) обозначается добавлением цифры 2 . Поворот против часовой стрелки обозначается добавлением штриха ( ′ ).

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

Ниже приведены нестандартные ходы.

Нестандартные ходы обычно обозначаются строчными буквами, в отличие от стандартных ходов, описанных выше.

Перемещение центральных кубиков граней в другие места:

Буквы M , S и E используются для обозначения токарной обработки среднего слоя. M (сокращение от «Средний» слой) представляет собой поворот слоя между гранями R и L на 1 четверть оборота по часовой стрелке (спереди назад), если смотреть лицом к грани L. S (сокращение от слоя «Standing») представляет собой поворот слоя между гранями F и B на 1 четверть оборота по часовой стрелке (сверху вниз), если смотреть лицом к грани F. E (сокращение от слоя «Экватор») представляет собой поворот слоя между гранями U и D на 1 четверть оборота по часовой стрелке (слева направо), если смотреть со стороны грани D. Как и в случае с обычными поворотами, цифра 2 означает половину оборота, а штрих (') указывает на поворот против часовой стрелки.

Вместо этого строчные буквы r , f и u также используются для обозначения слоев поворота рядом с R , F и U соответственно в том же направлении, что R , F и U. и Это более соответствует ожиданиям.

В многослойных кубах числа могут предшествовать именам граней, чтобы указать поворот n -го слоя от именованной грани. 2R , 2F и 2U затем используются для обозначения слоев поворота рядом с R , F и U соответственно в том же направлении, что R , F и U. и Использование этой записи для трехслойного куба более согласовано с многослойными кубами.

Вращение всего куба:

Буквы x , y и z используются для обозначения вращения куба. x означает вращение куба в R. направлении y означает вращение куба в U. направлении z означает вращение куба в F. направлении Эти вращения куба часто используются в алгоритмах, чтобы сделать их более плавными и быстрыми. Как и в случае с обычными поворотами, цифра 2 означает половину оборота, а штрих (') указывает на поворот против часовой стрелки. Обратите внимание, что эти пространственные вращения обычно обозначаются строчными буквами.

Нижние границы

Подсчитав аргументы, можно доказать, что существуют позиции, для решения которых требуется не менее 18 ходов. Чтобы показать это, сначала подсчитайте общее количество существующих позиций куба, а затем посчитайте количество позиций, которые можно достичь, используя не более 17 ходов, начиная с решенного куба. Оказывается, последнее число меньше.

Этот аргумент не улучшался в течение многих лет. Кроме того, это не конструктивное доказательство : оно не демонстрирует конкретную позицию, требующую такого количества ходов. Предполагалось , что так называемый суперфлип будет очень сложной позицией. Кубик Рубика находится в состоянии суперфлип, когда каждая угловая часть находится в правильном положении, но каждая краевая часть ориентирована неправильно. нашел решение для суперфлипа с 20 поворотами граней В 1992 году Дик Т. Уинтер , минимальность которого была показана в 1995 году Майклом Ридом , что дало новую нижнюю оценку диаметра группы кубов. Также в 1995 году решение для суперфлипа за 24 четверти оборота было найдено Майклом Ридом, а его минимальность доказана Джерри Брайаном . В 1998 году была найдена новая позиция, требующая для решения более 24 четвертей оборотов. Позиция, которая называлась «суперфлип, состоящий из четырех точек», требует 26 четвертьвитков.

Верхние границы

Первые верхние границы были основаны на «человеческих» алгоритмах. Объединив наихудшие сценарии для каждой части этих алгоритмов, было обнаружено, что типичная верхняя граница составляет около 100.

Возможно, первым конкретным значением верхней границы были 277 ходов, упомянутые Дэвидом Сингмастером в начале 1979 года. Он просто подсчитал максимальное количество ходов, требуемое его алгоритмом решения куба. Позже Сингмастер сообщил, что Элвин Берлекамп , Джон Конвей и Ричард К. Гай придумали другой алгоритм, который требовал максимум 160 ходов. Вскоре после этого кембриджские кубисты Конвея сообщили, что куб можно восстановить максимум за 94 хода.

Алгоритм Тистлетвейта

Прорыв, известный как «спуск через вложенные подгруппы», был открыт Морвен Тистлтуэйт ; Подробности алгоритма Тистлтуэйта были опубликованы в журнале Scientific American в 1981 году Дугласом Хофштадтером . Подходы к кубу, которые привели к созданию алгоритмов с очень небольшим количеством ходов, основаны на теории групп и обширных компьютерных поисках. Идея Тистлетуэйта заключалась в том, чтобы разделить проблему на подзадачи. Там, где алгоритмы до этого момента разделяли проблему, рассматривая части куба, которые должны оставаться фиксированными, он делил ее, ограничивая типы ходов, которые можно было выполнить. В частности, он разделил группу кубов на следующую цепочку подгрупп:

• $G_{0}=\langle L,R,F,B,U,D\rangle$
• $G_{1}=\langle L,R,F,B,U^{2},D^{2}\rangle$
• $G_{2}=\langle L,R,F^{2},B^{2},U^{2},D^{2}\rangle$
• $G_{3}=\langle L^{2},R^{2},F^{2},B^{2},U^{2},D^{2}\rangle$
• $G_{4}=\{1\}$

Затем он подготовил таблицы для каждого из правых смежных классов. $G_{i+1}\setminus G_{i}$. Для каждого элемента он нашел последовательность ходов, которая переводила его в следующую меньшую группу. После этих приготовлений он действовал следующим образом. Случайный куб находится в общей группе кубов. $G_{0}$. Затем он нашел этот элемент в правом смежном пространстве. $G_{1}\setminus G_{0}$. Он применил соответствующий процесс к кубу. Это привело его к кубу в $G_{1}$. Затем он нашел процесс, который переводит куб в $G_{2}$, рядом с $G_{3}$ и, наконец, чтобы $G_{4}$.

Промежуточное состояние кубика Рубика в алгоритме Коциембы. Любое состояние из G ₁ будет иметь символы «+» и «–», как показано.

Хотя вся группа кубов $G_{0}$ очень большой (~4,3×10 ¹⁹ ), правые смежные классы $G_{1}\setminus G_{0},G_{2}\setminus G_{1},G_{3}\setminus G_{2}$ и $G_{3}$ гораздо меньше. Комнатное пространство $G_{2}\setminus G_{1}$ является самым большим и содержит всего 1082565 элементов. Количество ходов, требуемое этим алгоритмом, представляет собой сумму наибольшего процесса на каждом шаге.

Первоначально Тистлетуэйт показал, что любую конфигурацию можно решить максимум за 85 ходов. В январе 1980 года он улучшил свою стратегию и теперь дает максимум 80 ходов. Позже в том же году он сократил это число до 63, а затем снова до 52. В результате тщательного поиска пространств смежных классов позже было обнаружено, что наихудшее возможное количество ходов для каждого этапа составляет 7, 10, 13 и 15, что дает в общей сложности не более 45 ходов. Алгоритм Тистлуэйта был реализован на различных компьютерных языках.

Алгоритм Коциембы

Алгоритм Тистлетвейта был улучшен Гербертом Коциембой в 1992 году. Он сократил количество промежуточных групп до двух:

• $G_{0}=\langle U,D,L,R,F,B\rangle$
• $G_{1}=\langle U,D,L^{2},R^{2},F^{2},B^{2}\rangle$
• $G_{2}=\{1\}$

Как и в случае с алгоритмом Тистлтуэйта , он будет искать правильное смежное пространство. $G_{1}\setminus G_{0}$ взять куб в группу $G_{1}$. Далее он искал оптимальное решение для группы. $G_{1}$. Поиски в $G_{1}\setminus G_{0}$ и $G_{1}$ оба были выполнены с использованием метода, эквивалентного итеративному углублению A* (IDA*). Поиск в $G_{1}\setminus G_{0}$ нужно максимум 12 ходов и поиск в $G_{1}$ не более 18 ходов, как показал Майкл Рид в 1995 году. Путем генерации неоптимальных решений, которые группируют куб $G_{1}$ и ищем короткие решения в $G_{1}$, обычно получаются гораздо более короткие общие решения. С помощью этого алгоритма решения обычно находятся менее чем за 21 ход, хотя нет никаких доказательств того, что он будет делать это всегда.

В 1995 году Майкл Рид доказал, что с помощью этих двух групп каждую позицию можно решить максимум за 29 поворотов лицом или за 42 четвертьповорота. Этот результат улучшил Сильвиу Раду в 2005 году до 40.

На первый взгляд этот алгоритм кажется практически неэффективным: если $G_{0}$содержит 18 возможных ходов (каждый ход, его простое число и поворот на 180 градусов), что оставляет $18^{12}$ (более 1 квадриллиона) состояний куба для поиска. Даже при использовании эвристике, компьютерного алгоритма, основанного на такого как IDA* , который может значительно сузить область поиска, поиск по такому количеству состояний, вероятно, непрактичен. Чтобы решить эту проблему, Коциемба разработал справочную таблицу, которая обеспечивает точную эвристику для $G_{0}$. Когда точное количество ходов, необходимое для достижения $G_{1}$доступен, поиск становится практически мгновенным: нужно всего лишь сгенерировать 18 состояний куба для каждого из 12 ходов и каждый раз выбирать то, которое имеет наименьшую эвристику. Это позволяет использовать вторую эвристику, которая для $G_{1}$, если быть менее точным и при этом позволить вычислить решение за разумное время на современном компьютере.

Алгоритм Корфа

Использование этих групповых решений в сочетании с компьютерным поиском обычно быстро дает очень короткие решения. Но эти решения не всегда имеют гарантию своей минимальности. Для поиска именно минимальных решений нужен был новый подход.

В 1997 году Ричард Корф анонсировал алгоритм, с помощью которого он оптимально решал случайные экземпляры куба. Из десяти случайных кубиков, которые он собрал, ни один не потребовал более 18 поворотов грани. Используемый им метод называется IDA* и описан в его статье «Поиск оптимальных решений кубика Рубика с использованием баз данных шаблонов». Корф описывает этот метод следующим образом

IDA* — это поиск в глубину, который ищет все более длинные решения в серии итераций, используя эвристику нижней границы для обрезки ветвей, когда нижняя граница их длины превышает текущую границу итераций.

Это работает примерно следующим образом. Сначала он определил ряд подзадач, которые достаточно малы, чтобы их можно было решить оптимально. Он использовал:

1. Куб ограничен только углами, не глядя на края.
2. Куб ограничен только шестью ребрами, не глядя ни на углы, ни на другие ребра.
3. Куб ограничен остальными 6 ребрами.

Очевидно, что количество ходов, необходимое для решения любой из этих подзадач, является нижней границей количества ходов, необходимых для решения всего куба.

Учитывая случайный куб C, он решается как итеративное углубление . Сначала генерируются все кубики, являющиеся результатом применения к ним 1 хода. То есть C*F, C*U,… Далее из этого списка генерируются все кубики, являющиеся результатом применения двух ходов. Потом три хода и так далее. Если в какой-то момент обнаруживается куб, которому требуется слишком много ходов, исходя из нижних границ, чтобы оставаться оптимальным, его можно исключить из списка.

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

Дальнейшие улучшения и поиск числа Бога

В 2006 году Сильвиу Раду еще больше усовершенствовал свои методы, доказав, что каждую позицию можно решить максимум за 27 поворотов лица или 35 поворотов на четверть. Дэниел Канкл и Джин Куперман в 2007 году использовали суперкомпьютер , чтобы показать, что все нерешенные кубики можно собрать не более чем за 26 ходов (в метрике поворота лицом). Вместо того, чтобы пытаться явно решить каждый из миллиардов вариантов, компьютер был запрограммирован так, чтобы привести куб в одно из 15 752 состояний, каждое из которых можно было решить за несколько дополнительных ходов. Было доказано, что все они разрешимы за 29 ходов, причем большинство из них разрешимы за 26 ходов. Те, которые изначально не могли быть решены за 26 ходов, затем были решены явно и показано, что их тоже можно решить за 26 ходов.

Томас Рокицки в вычислительном доказательстве 2008 года сообщил, что все нерешенные кубы можно собрать за 25 ходов или меньше. Позже это число было сокращено до 23 ходов. В августе 2008 года Рокицки объявил, что у него есть доказательство для 22 ходов.

Наконец, в 2010 году Томас Рокицки, Герберт Косиемба, Морли Дэвидсон и Джон Детридж представили окончательное компьютерное доказательство того, что все положения куба можно решить максимум за 20 поворотов грани. В 2009 году Томас Рокицки доказал, что 29 ходов в четвертьоборотной метрике достаточно, чтобы собрать любой зашифрованный кубик. А в 2014 году Томас Рокицки и Морли Дэвидсон доказали, что максимальное количество четвертьоборотов, необходимое для сборки куба, — 26.

Метрики торца и четверти оборота различаются характером своих антиподов. Антипод — это перемешанный куб, максимально далекий от решения, требующий максимального количества ходов для решения. В полуповоротной метрике с максимальным количеством 20 таких позиций сотни миллионов. В метрике четвертьоборота известна только одна позиция (и два ее вращения), требующая максимум 26 ходов. Несмотря на значительные усилия, никаких дополнительных положений дистанции четверти оборота 26 обнаружено не было. Известно, что даже на расстоянии 25 существуют только две позиции (и их вращения). На расстоянии 24 существует около 150 000 позиций.

Дальнейшее чтение

• Сингмастер, Дэвид (1981). Заметки о волшебном кубике Рубика . Издательство Энслоу.

Внешние ссылки

• Как собрать кубик Рубика — статья в Wikibooks, в которой дается обзор нескольких алгоритмов, которые достаточно просты, чтобы их мог запомнить человек. Однако такие алгоритмы обычно не дают оптимального решения, использующего только минимально возможное количество ходов.