Исследования кубика Рубика математиками начались в начале 80-х годов
прошлого века (сама головоломка была создана в 1974 году). Как
оказалось, группа симметрий кубика, действующая на множестве его
квадратов, довольно сложна и плохо поддается изучению.
В 2010
году специалисты по теории игр просчитали на суперкомпьютере все 43 252
003 274 489 856 000 возможных первоначальных позиций для стандартного
кубика Рубика (3 на 3 на 3) и установили, что из любого начального положения кубик можно собрать всего за 20 ходов, сообщает lenta.ru.
В
рамках нового исследования ученых интересовала асимптотическая оценка
количества движений, необходимых для решения кубика Рубика (хотя, в
данном случае, его правильнее было бы называть прямоугольным
параллелепипедом) со сторонами произвольной величины. В качестве
параметра оценки выступало число n - длина максимальной стороны
головоломки, а «асимптотическая» в названии означает, что оценка не
точная, но с ростом n оптимальное число ходов растет как оценка.
Исследователям
удалось установить, что в общем случае количество ходов есть O(n2) - то
есть число необходимых для решения движений куба увеличивается примерно
как квадрат n, умноженный на некоторую константу. При этом учеными
предложен непосредственный алгоритм решения, который реализует
предложенную оценку.
В двух частных случаях ученым удалось
улучшить этот результат. Так, оказалось что для «кубического» кубика
Рубика, то есть головоломки с размерами n на n на n, и для «веревки»
Рубика - головоломки с размерами n на n на 1, оценка выглядит как
O(n2/log n). Последний эффект связан с тем, что за одно движение в
подобных головоломках можно ставить на нужное место сразу несколько
квадратов.
Задача о решении кубика Рубика относится к классу
алгоритмических задач реорганизации. Типичным примером такой задачи,
встречающимся на практике, является перестановка нужным образом коробок
на складе.
Ранее группа американских ученых под руководством
профессора Морли Дэвидсона из университета Кента в штате Огайо, которая с
помощью компьютеров корпорации Google перебрала все возможные
комбинации головоломки, пришла выводу, что собрать кубик Рубика из любого исходного состояния можно не более чем за 20 ходов.
В результате выяснилось, что так называемое «число Бога», минимально необходимое
количество ходов для сборки кубика Рубика из любой начальной комбинации,
равно 20. «Теперь мы точно знаем, что волшебное число - это 20», -
заявил Дэвидсон.
До 1995 года считалось, что теоретический
минимум для сборки популярной головоломки составляет 18 ходов, однако
математик Майкл Райд нашел исходную конфигурацию, из которой кубик
Рубика можно собрать лишь за 20 ходов.
По словам Дэвидсона, с тех
пор считалось, что «число Бога» равно именно 20, однако это
предположение было основано лишь на вере ученых: никому ранее не
удавалось проверить все конфигурации головоломки. «Мы втайне надеялись,
что в ходе тестов найдем комбинацию, для которой нужен 21 ход», - сказал
Дэвидсон.
Чтобы решить эту задачу, ученые разбили все возможные
исходные состояния примерно на 2,2 миллиарда групп по 20 миллиардов
вариантов в каждой - именно столько состояний у классического кубика
Рубика. Выявляя одинаковые и симметричные состояния, исследователи
сократили тестовый набор до 56 миллионов групп.
Корпорация Google
предложила ученым свой парк компьютеров для проверки всех этих
комбинаций. По оценкам Дэвидсона, хорошему настольному ПК с
четырехъядерным процессором микроархитектуры Nehalem и тактовой частотой
2,8 гигагерца на это потребовалось бы около 35 лет машинного времени.
Ученые
опубликовали результаты своей работы в Интернете и собираются
подготовить статью для научного журнала. По их словам, протестировать
код сможет любой обладатель небольшого суперкомпьютера. Сами
исследователи собираются продолжить работу и, в частности, найти «число
Бога» для других вариантов головоломки.
|