Алгоритм Бога Рубика

   Матема?тика ку?бика Ру?бика — совокупность математических методов для изучения свойств кубика Рубика с абстрактно-математической точки зрения. Изучает алгоритмы сборки кубика, оценки алгоритмов его сборки и др. Основана на теории графов, теории групп, теории вычислимости, комбинаторике.

   Существует множество алгоритмов, предназначенных для перевода кубика Рубика из произвольной конфигурации в конечную конфигурацию (собранную, все грани одноцветны). В 2010 г. строго доказано, что для перевода кубика Рубика из произвольной конфигурации в собранную конфигурацию (часто этот процесс называют «сборкой» или «решением») достаточно не более чем 20 поворотов граней. Это число является диаметром графа Кэли группы кубика Рубика. Алгоритм, который решает головоломку за минимально возможное количество ходов, называют алгоритмом Бога.

Алгоритма Бога кубика Рубика

   История поиска алгоритма Бога кубика Рубика началась не позже 1980 года, когда открылся список рассылки для любителей кубика Рубика. С тех пор математики, программисты и просто любители стремились найти алгоритм Бога — алгоритм, который бы позволил на практике решать кубик Рубика за минимальное число ходов. С этой проблемой была связана проблема определения числа Бога — числа ходов, всегда достаточного для сборки головоломки.

   В июле 2010 года программист из Пало-Альто Томас Рокики, учитель математики из Дармштадта Герберт Коцемба, математик из Кентского университета Морли Дэвидсон и инженер компании Google Inc. Джон Детридж доказали, что каждая конфигурация кубика Рубика может быть решена не более чем в 20 ходов. При этом любой поворот грани считался одним ходом. Таким образом, число Бога в метрике FTM оказалось равно 20 ходам. Объём вычислений составил около 35 лет процессорного времени, пожертвованного компанией Google. Технические данные о производительности и количестве компьютеров не разглашаются; продолжительность вычислений составляла несколько недель.

Нижние оценки числа Бога

   Достаточно легко показать, что существуют разрешимые конфигурации, которые не могут быть решены менее чем в 17 ходов в метрике FTM или 19 ходов в метрике QTM.

Эту оценку можно улучшить, принимая во внимание дополнительные тождества, например, коммутативность поворотов двух противоположных граней (L R = R L, L2 R = R L2 и т. д.) Подобный подход позволяет получить нижнюю оценку для числа Бога, равную 18f или 21q.

   «Суперфлип» — первая обнаруженная конфигурация, находящаяся на расстоянии 20f* от начальной Эта оценка в течение многих лет оставалась наилучшей известной. Кроме того, она вытекает из неконструктивного доказательства, так как оно не указывает конкретный пример конфигурации, требующей для сборки 18f или 21q.

Одной из конфигураций, для которой не удавалось найти короткое решение, был так называемый «суперфлип» (англ.), или «12-флип». «Суперфлип» представляет собой конфигурацию, в которой все угловые и рёберные кубики находятся на своих местах, но каждый рёберный кубик ориентирован противоположно.

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

   В 1992 году Дик Т. Винтер нашёл решение суперфлипа в 20f. В 1995 году Майкл Рид доказал оптимальность этого решения, в результате чего нижняя оценка числа Бога стала равной 20 FTM. В том же году Майкл Рид обнаружил решение «суперфлипа» в 24q. Оптимальность этого решения была доказана Джерри Брайаном.

   В 1998 году Майкл Рид нашёл конфигурацию, оптимальное решение которой составляло 26q*. По состоянию на июль 2013 года, это число является наилучшей известной нижней оценкой числа Бога в метрике QTM.

Верхние оценки числа Бога

   Чтобы получить оценку сверху для числа Бога, достаточно указать любой алгоритм сборки головоломки, состоящий из конечного числа ходов.

   Первые оценки сверху для числа Бога были основаны на «человеческих» алгоритмах, состоящих из нескольких этапов. Сложение оценок сверху для каждого из этапов позволяло получить итоговую оценку порядка нескольких десятков или сотен ходов.

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

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

Выберите достойную оценку заметке:

Сейчас рейтинг заметки:2

5 последних заметок категории "Разное"

Представленное на фото здание удивляет своим необычным дизайнерским решением. Этот оранжевый кубик Рубик находится в городе Леоне...

Рейтинг:

«Кубик Рубика» празднует своё 40-летие. Трудно, наверное, найти человека, который хоть раз в жизни не держал в руках «Кубик Рубика». И, если это увлечение давно забыто, то сейчас самое время о нём вспомнить. Игрушка празднует своё 40-летие...

Рейтинг:

Гигантский кубик Рубика 17х17 собрали за семь с половиной часов

Рейтинг:

30 августа в Харькове прошел чемпионат по скоростной сборке кубика Рубика и других головоломок Kharkiv Cube Day 2014...

Рейтинг:

Состязания по скоростной сборке головоломки пройдут в актовом зале Национального университета Юридическая академия имени Ярослава Мудрого

Рейтинг:
Просмотров: 35907
  • Введите имя

    Оставьте комментарий

    Для комментария нажмите на картинку "кубик Рубика"!


Яндекс цитирования
Яндекс.Метрика
Hosting Ukraine