Математика кубик-рубика
Вы знали что казалось бы такая простая игрушка как кубик-рубика. Несет в себе целые области математики?
Для полного оптимального решения кубик-рубика понадобилось теория графов, топология, теория групп, вычислительные методы конечных интегралов, комбинаторика и.т.д. А также 35.лет процессорного комютерного времени!
И всё это чтоб найти тот самый оптимальный алгоритм.
То есть способ собрать кубик-рубика, с любого состояния за минимальное количество ходов. Этот алгоритм назвали алгоритмом бога.
Этот термин может также быть использован в отношении других перестановочных головоломок. Под алгоритмом Бога головоломки подразумевается любой алгоритм, который позволяет получить решение головоломки, содержащее минимально возможное число ходов (оптимальное решение), начиная с любой заданной конфигурации.
Давайте попробуем разобраться с математической кубик-рубика :
И так если вы когда-то собирали кубик-рубика вы должны знать, что без использования алгоритмов это невозможно! Так число возможных состояний кубика рубика равное
43 252 003 274 489 856 000, то есть более 43 квинтиллионов комбинаций.
То есть если вы хочете совершенно случайно собрать кубик-рубика, из более менее запутанаго состояния, то вы обречены на неудачу.
Группа кубик-рубика
Поскольку центральный цвет на любой грани у нас не перемещается, то получается что на каждой грани перемещаться только 8 кубиков с цевтовыми этикетками . А значит каждая грань имеет группу S(8), а поскольку у кубик-рубика 6.граней. То он имеет группу S(8*6) = S(48). Другими словами у нас есть 48.ячеек куда мы можем расположить 6-цветов примерно 43.квинтиллионов, используя шесть поворотов граней кубик-рубика {F,B,U,D,L,R}
Где каждый поворот может рассматриваться как элемент симметрической группы множества S(48) этикеток кубика Рубика, не являющихся центрами граней. Более конкретно, можно пометить все 48 этикеток числами от 1 до 48 и сопоставить каждому из ходов
{F,B,U,D,L,R}
элемент симметрической группы S(48).
Полная группа кубик-рубика G определяется как подгруппа S(48),
G = {F,B,U,D,L,R}
|G| = 43 252 003 274 489 856 000 - конфигураций
Каждая из 4.325 ^ 19 конфигураций может быть решена не более чем за 20 ходов (если считать за ход любой поворот грани). Ну то есть самое быстрое решение на сегодня, это решение за 20.ходов.
Буквы {L,R,F,B,U,D} обозначают поворот на 90° по часовой стрелке левой (left), правой (right), передней (front), задней (back), верхней (up) и нижней (down) граней соответственно. Повороты на 180° обозначаются добавлением справа к букве цифры 2 или добавлением в верхнем индексе цифры 2 справа от буквы. Поворот на 90° против часовой стрелки обозначается добавлением штриха ( ′ ) или добавлением в верхнем индексе -1 справа от буквы.
Алгоритмы решения кубик-рубика это определённая последовательность этих шести портов, относительно каждой грани, и каждого состояния кубик-рубика,которые за определённое количество ходов“поворотов" приводять кубик-рубика в собранное состояние.
Ну например мы смотрим на кубик-рубика ,а потом делаем повороты RB2 L' B R'2, и потом опять смотрим что получается, и сново делаем повороты RB' L и.т.д… И так пока не собирается кубик-рубика
Существует множество алгоритмов :
Алгоритм Корфа,
Алгоритм Тистлетуэйта,
и.т.д..
Один самых популярных алгоритмов, можете почитать тут : https://speedcubing.com.ua/howto/3x3
Алгоритм Бога
Алгоритм Бога начали искать не позже 1980 года, когда открылся список рассылки для любителей кубика Рубика[6]. С тех пор математики, программисты и любители стремились найти алгоритм Бога, чтобы на практике за минимальное число ходов собирать кубик Рубика. С этой проблемой была связана проблема определения числа Бога — числа ходов, всегда достаточного для сборки головоломки.
В 2010 году программист из Пало-Альто Томас Рокики, учитель математики из Дармштадта Герберт Коцемба, математик из Кентского университета Морли Дэвидсон и инженер компании Google Inc. Джон Детридж доказали, что кубик Рубика из любого разобранного состояния можно собрать за 20 ходов. При этом любой поворот грани считался одним ходом. Объём вычислений составил 35 лет процессорного времени, пожертвованного компанией Google[1][14][15]. Технические данные о производительности и количестве компьютеров не разглашаются. Продолжительность вычислений составляла несколько недель[16][17][18].
В 2014 году Томас Рокики и Морли Дэвидсон доказали, что кубик Рубика можно собрать не более чем в 26 ходов без использования поворотов на 180°. Объём вычислений составил 29 лет процессорного времени в суперкомпьютерном центре Огайо[3].
P. S может вы попробуйте найти ещё более мощный алгоритм?
