Оптимальные решения для кубика Рубика - Optimal solutions for Rubiks Cube - Wikipedia

Кубик Рубика взбитый

Оптимальные решения для Кубик Рубика обратитесь к наиболее коротким решениям. Есть два распространенных способа измерения длины раствора. Первый - подсчитать количество четвертей оборота. Второй - подсчитать количество поворотов внешнего слоя, называемых «поворотами лица». Перемещение внешнего слоя на два четверти (90 °) оборота в одном направлении будет засчитываться как два хода в метрике четверть оборота (QTM), но как один оборот в метрике торца (FTM или HTM «Половинная метрика»). "или OBTM" Метрика поворота внешнего блока ").^[1]

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

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

Обозначение перемещения

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

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

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

Буквы X, Y и Z используются для обозначения вращения куба. X означает поворот куба вперед на 90 градусов. Y означает поворот куба влево на 90 градусов. Z означает поворот куба по часовой стрелке на 90 градусов. Эти вращения куба используются в алгоритмах, чтобы сделать их более плавными и быстрыми. Как и в случае с обычными поворотами, 2 обозначает половину оборота, а штрих (') обозначает четверть оборота в противоположном направлении. Обратите внимание, что эти буквы обычно строчные.

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

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

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

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

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

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

Алгоритм Thistlethwaite

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

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

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

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

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

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

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

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

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

Как и с Алгоритм Тистлтуэйта, он будет искать в правильном смежном пространстве ${ Displaystyle G_ {1} setminus G_ {0}}$ взять куб в группу ${ displaystyle G_ {1}}$. Затем он искал оптимальное решение для группы ${ displaystyle G_ {1}}$. Поиски в ${ Displaystyle G_ {1} setminus G_ {0}}$ и ${ displaystyle G_ {1}}$ оба были выполнены методом, эквивалентным ИДА*. Поиск в ${ Displaystyle G_ {1} setminus G_ {0}}$ нужно не более 12 ходов и поиск в ${ displaystyle G_ {1}}$ не более 18 ходов, как показал Майкл Рид в 1995 году. Кроме того, генерируя неоптимальные решения, объединяющие куб ${ displaystyle G_ {1}}$ и ищем короткие решения в ${ displaystyle G_ {1}}$, обычно получаются гораздо более короткие общие решения. При использовании этого алгоритма решения обычно составляют менее 21 хода, хотя нет никаких доказательств того, что так будет всегда.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

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

• Singmaster, Дэвид (1981). Заметки о волшебном кубе Рубика. Enslow Publishers.CS1 maint: ref = harv (связь)

внешняя ссылка

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