25 ходов на кубик Рубика
Собрать кубик Рубика можно из любого положения всего за 25 шагов. Американский программист Томас Рокицкий доказал: среди конфигураций головоломки не найдётся ни одной, на решение которой идеальному мозгу потребуется больше 25 поворотов. В течение ближайших нескольких месяцев он планирует сократить магическое число до 24.
Изобретение Эрнё Рубика считается самой популярной головоломкой в истории. За 30 с лишним лет, прошедших с поступления первой партии кубиков Рубика в магазины Будапешта, во всё мире было продано свыше 300 миллионов экземпляров оригинального кубика и всевозможных его аналогов.
Внешняя простота игрушки – шесть сторон куба, поворачивающихся вдоль любой из трёх взаимно перпендикулярных осей, скрывает 43 квинтиллиона конфигураций (4,3*1019), и это без учёта вращений кубика как целого. Если бы каждый из 300 миллионов кубиков, проданных в мире (среди них есть и кубики 2x2x2, 4x4x4, 5x5x5 и даже 6x6x6 и 7x7x7, но львиная доля – всё же «классические» 3x3x3), можно было бы перестраивать в новую конфигурацию раз в секунду, перебор всех возможностей потребовал бы более 3 тысяч лет. С начала 1980-х годов проводятся ежегодные чемпионаты мира по скоростной сборке кубика, и в настоящее время рекорд составляет 9,18 секунды, что на полсекунды меньше рекорда преодоления стометровки в лёгкой атлетике.
Алгоритмы сборки головоломки появились вскоре после её появления в продаже. Они отличаются и универсальностью, и длиной, и сложностью. Существуют наборы всего из нескольких универсальных приёмов, включающих два–три поворота, позволяющих разобраться с большинством конфигураций за сотню шагов, существуют наборы из нескольких десятков сложных приёмов, грамотное использование которых сводит количество необходимых операций к трём–четырём десяткам. В конечном итоге вопрос эффективности алгоритма решается индивидуально. Кому-то проще держать в голове много сложных приёмов, дольше времени соображая, каким из них воспользоваться, кому-то – быстро оценить ситуацию и пытаться управиться небольшим количеством заготовок.
Однако если публику больше интересует быстрота сборки, измеренная в секундах, то математиков – количество шагов – единичных операций, за которые эта сборка осуществима.
Шаги и повороты
Прежде чем называть конкретные числа, стоит сразу же оговориться, какие операции мы называем шагом. На этот счёт существуют две основных традиции.
Одна из них признаёт лишь повороты Они заняты поисками самых коротких алгоритмов как для каждой заданной конфигурации, так и для всего их набора. Любой алгоритм можно удлинить, как заблагорассудится – например, накручивать полные обороты любой из сторон, не меняя ничего в итоговой картине. Однако понятно, что для каждой конфигурации кубика есть алгоритм минимальной длины. Эта длина изменяется от нуля шагов – уже собранного кубика, с которым делать ничего не надо, до некоторого числа – длины алгоритма, способного за минимальное количество шагов собрать кубик из самой сложной конфигурации.
Может показаться удивительным, но это число совсем невелико.
Ещё в 1982 году Дэвид Сингмастер и Александр Фрей, сославшись на мнение неназванных «опытных специалистов по теории групп», предположили, что оно должно быть «в начале третьего десятка». В 1992 году Майкл Рид показал, что оно не больше 30, а вскоре догадался, как снизить оценку до 29 движений. В 2006 году предел был сокращён до 27, а в прошлом году Дэниел Канкл и Джин Купермэн доказали, что из любого положения кубик Рубика можно вернуть в исходное за 26 шагов. На это потребовались мозг двух профессиональных математиков и год процессорного времени на параллельном суперкомпьютере с 7 ТБ (7 тысячами гигабайт) памяти.
На фоне последних чисел новая работа калифорнийского программиста Томаса Рокицкого (также, разумеется, не лишённого профессионального математического образования) впечатляет. Он оценивает «цену» своего лимита в полторы тысячи часов (два месяца) компьютерного времени; при этом потребовались скромных 8ГБ памяти – параметр, более характерный для средней руки сервера, чем для суперкомпьютера. На деле подсчёт занял даже меньше двух месяцев, поскольку Рокицкий не начинал с нуля, а успешно приспособил имевшиеся у него прежде разработки касательно кубика Рубика для новой задачи.
Калифорниец модернизировал метод немецкого математика Герберта Коцимбы, разработанный тем в начале 1990-х годов. Среди 43 квинтиллионов конфигураций немец выделил 20 миллиардов «избранных», которые можно перевести друг в друга десятью «избранными» поворотами. Среди этих 20 миллиардов нашлось место и собранному кубику. Как оказалось, все остальные «избранные» отстоят от него не более чем на 18 «избранных» поворотов. Позднее удалось доказать, что любая конфигурация из общего множества отстоит от одной из избранных лишь на 12 ходов, а значит, каждый кубик Рубика можно собрать за 12 + 18 = 30 ходов.
"Суперклип" - пример конфигурации кубика Рубика, требующей для сборки не менее 20 шагов. В данном случае все элементы находятся на своих местах, но элементы посредине всех рёбер перевёрнуты. До сих пор неизвестно ни одной конфигурации, которую нельзя собрать за 20 шагов. //math.ucf.edu
Метод Коцимбы позволяет искать «почти оптимальные» алгоритмы (правда, не позволяя доказать их минимальность) довольно простым способом. Сначала составляется таблица, в которой для всех 20 миллиардов «избранных» конфигураций хранится число ходов, необходимых для сборки кубика. Потом для каждой выбранной конфигурации рассматривается минимальный путь перевести её в одну из избранных. Суммарная длина двух участков пути и даёт полную длину пути от заданного состояния к финальному. Перебирать все пути длиной до 20 шагов программы, основанные на методе Коцимбы, позволяют за несколько миллисекунд. Тот из них, что окажется самым коротким, и берётся за «почти оптимальный».
Рокицкий пошёл иным путём. Для каждой конфигурации он ищет все алгоритмы определённой длины, переводящие её в одну из «избранных». Поскольку все разрешённые конфигурации переводятся друг в друга определённым набором поворотов, то рано или поздно исчерпываются все «избранные». Если записать для каждой из них длину предложенного решения, то максимальная из них даст максимальную длину не только для заданного положения, но и ещё для двух миллиардов конфигураций, отличающихся от своей «избранной» той последовательностью движений, что переводит заданную конфигурацию в свою «избранную». Все эти наборы не пересекаются и вместе составляют полное множество из 43 квинтиллионов конфигураций.
Оценка длины
Рокицкий смог свести задачу к анализу графа, узлами которого являются сами наборы, а рёбрами – последовательности ходов, переводящие один набор в другой. Верхний предел на длину оптимального На данный момент Рокицкому удалось установить предел длины алгоритма для примерно 8 тысяч таких наборов, из которых половина пригодилась для оценки максимальной длины алгоритма во всём большом множестве. Поскольку пределы для других наборов получаются на основе «базовых» (см. врез), то чем больше базовых, тем лучше оказывается предел. На данный момент он составляет 25 ходов для всех конфигураций. Однако с появлением новых «баз» этот предел должен улучшиться. Учёный намерен в ближайшие месяцы улучшить его до 24 ходов.
Сказать, какой именно алгоритм переводит заданную конфигурацию в исходную, можно лишь для тех наборов, длина максимальных алгоритмов которых установлена; таковых на данный момент – 8 тысяч из 2 миллиардов.
Среди них нет ни одного, элементы которого не переводились бы в исходное более чем за 20 ходов.
Многие учёные полагают, что 20 – это и есть истинный предел для длины идеального алгоритма. Если это так, получится весьма красиво. Ведь подвижных элементов в кубике Рубика также 20. В таком случае нечестный «алгоритм» – вытащить каждый элемент и вставить его обратно в нужной позиции окажется столь же трудоёмким, что и идеальный честный алгоритм. Математики называют его ещё «алгоритмом бога».
