Легко показать, что существуют разрешимые конфигурации[19], которые не могут быть решены менее чем в 17 ходов в метрике FTM или 19 ходов в метрике QTM.
«Суперфлип» — первая обнаруженная конфигурация, находящаяся на расстоянии 20f* от начальной
Эта оценка долго оставалась наилучшей известной. Она вытекает из неконструктивного доказательства, так как оно не указывает конкретный пример конфигурации, требующей для сборки 18f или 21q.
Одной из конфигураций, для которой не удавалось найти короткое решение, был так называемый «суперфлип» или «12-флип». В «Суперфлипе» все угловые и рёберные кубики находятся на своих местах, но каждый рёберный кубик ориентирован противоположно[22]. Вершина, отвечающая суперфлипу в графе кубика Рубика, — локальный максимум: любой ход из этой конфигурации уменьшает расстояние до начальной конфигурации. Это позволило предположить, что суперфлип находится на максимальном расстоянии от начальной конфигурации. То есть суперфлип — это глобальный максимум[23][24][25].
В 1992 году Дик Т. Винтер нашёл решение суперфлипа в 20f[26]. В 1995 году Майкл Рид доказал оптимальность этого решения[27], в результате чего нижняя оценка числа Бога стала равной 20 FTM. В 1995 году Майкл Рид обнаружил решение «суперфлипа» в 24q[28]. Оптимальность этого решения доказал Джерри Брайан[29]. В 1998 году Майкл Рид нашёл конфигурацию, оптимальное решение которой составляло 26q*[30].
Вероятно, первую конкретную оценку сверху дал Дэвид Сингмастер в 1979 году. Его алгоритм сборки позволял собирать головоломку не более чем за 277 ходов[16][31]. Позднее Сингмастер сообщил, что Элвин Берлекэмп[en], Джон Конвей и Ричард Гай разработали алгоритм сборки, требующий не более 160 ходов. Вскоре группа «Conway’s Cambridge Cubists», составлявшая список комбинаций для одной грани, нашла 94-ходовый алгоритм[16][32]. В 1982 году в журнале «Квант» был опубликован список комбинаций, позволяющих решить кубик Рубика в 79 ходов[33].
Алгоритм Тистлетуэйта
В начале 1980-х английский математик Морвин Тистлетуэйт разработал алгоритм, позволивший значительно улучшить верхнюю оценку. Детали алгоритма опубликовал Дуглас Хофштадтер в 1981 году в журнале Scientific American. Алгоритм был основан на теории групп и включал в себя четыре этапа.
Чтобы уменьшить количество записей в таблицах поиска, Тистлетуэйт использовал упрощающие предварительные ходы. Первоначально он получил оценку в 85 ходов. В течение 1980 года эта оценка была снижена до 80 ходов, затем до 63 и 52[16][36]. Студенты Тистлетуэйта провели полный анализ каждого из этапов. Максимальные значения в таблицах равны 7, 10, 13 и 15 ходам FTM соответственно. Так как 7 + 10 + 13 + 15 = 45, кубик Рубика всегда может быть решён в 45 ходов FTM[25][37][38].
Модификации алгоритма Тистлетуэйта
В декабре 1990 года Ханс Клоостерман использовал модифицированную версию метода Тистлетуэйта для доказательства достаточности 42 ходов[1][20][41].
В мае 1992 года Майкл Рид показал достаточность 39f или 56q[42].
Уже через несколько дней Дик Т. Винтер снизил оценку в метрике FTM до 37 ходов[43].
В декабре 2002 года Райан Хайз разработал вариант алгоритма Тистлетуэйта, предназначенный для скоростной сборки кубика Рубика[44].
Алгоритм Тистлетуэйта в 1992 году улучшил учитель математики из Дармштадта Герберт Коцемба.
Cube Explorer — программная реализация алгоритма для ОС Windows. Ссылки для загрузки находятся на сайте Герберта Коцембы[54]. В 1992 году на ПК Atari ST с памятью 1 Мбайт и частотой 8 МГц алгоритм позволял в течение 1-2 минут найти решение не длиннее 22 ходов[20][45]. На современном компьютере Cube Explorer позволяет за несколько секунд найти решение не длиннее 20 ходов для произвольно заданной конфигурации[45].
Существует онлайн-версия алгоритма[55].
Анализ
В 1995 году Майкл Рид показал, что первая и вторая фазы алгоритма Коцембы могут потребовать не более 12 и 18 ходов (FTM) соответственно. Из этого следует, что кубик Рубика всегда может быть решён в 30 ходов. Дополнительный анализ показал, что всегда достаточно 29f или 42q[25][56].
В 1997 году Ричард Корф опубликовал алгоритм, позволявший оптимально решать произвольные конфигурации кубика Рубика. Десять выбранных случайным образом конфигураций были решены не более чем в 18 ходов FTM[57][58].
Дальнейшие улучшения
В 2005 году результат Майкла Рида в метрике QTM улучшил Силвиу Раду до 40q[60]. В 2006 году Силвиу Раду доказал, что кубик Рубика можно собрать в 27f[39] или 35q[61].
В 2007 году Дэниел Канкл и Джин Куперман использовали суперкомпьютер для доказательства того, что все нерешённые конфигурации можно решить не более чем в 26 ходов FTM. Идея состояла в том, чтобы привести кубик Рубика в одну из 15 752 конфигураций подгруппы квадратов, каждая из которых может быть окончательно решена с помощью нескольких дополнительных ходов. Большинство конфигураций удалось решить таким образом не более чем в 26 ходов. Оставшиеся конфигурации подвергли дополнительному анализу, который показал, что они также решаются в 26 ходов[40][62].
В 2008 году Томас Рокики опубликовал вычислительное доказательство разрешимости головоломки в 25 ходов FTM[63]. В августе 2008 года Рокики объявил о доказательстве разрешимости в 23f[64]. Позже эта оценка улучшилась до 22f[65]. В 2009 году ему же удалось показать разрешимость в 29 ходов QTM[66].
В 2010 году Томас Рокики, Герберт Коцемба, Морли Дэвидсон и Джон Детридж объявили о доказательстве того, что любая конфигурация кубика Рубика может быть решена не более чем в 20 ходов в метрике FTM[1][14]. Вместе с известной ранее оценкой снизу в 20f* это стало доказательством того, что число Бога кубика Рубика в метрике FTM равно 20.
В августе 2014 года Рокики и Дэвидсон объявили, что число Бога для кубика Рубика в метрике QTM равно 26
|
Просмотр темы (новые вначале)
