Компания Google рассчитала "число Бога"
19 августа 2010 10:34
30 летняя одиссея, направленная на поиск минимального числа ходов, необходимого для решения любой из миллиардов конфигураций кубика Рубика завершена.
По словам исследователей, насколько бы ни был запутан кубик Рубика, его можно собрать за 20 или меньше ходов. Интернациональная команда, с помощью вычислительных мощностей, которые предоставила компания Google, обнаружила это число.
Это число известно под названием «числа Бога», потому что только всезнающая сущность знает оптимальное число, необходимое для решения этой головоломки.
«Мы выяснили, что это магическое число равно 20», — заявил профессор Морли Девидсон, математик из Кентского университета. При этом львиная доля стартовых позиций разрешаются за 15-19 ходов.
’Неразрешимая проблема’
До 1996 исследователи считали, что любая комбинация кубика Рубика может быть разрешена максимум за 18 шагов. Работа математика Майкла Рейда, заставила увеличить это число до 20, — он обнаружил конфигурации, которые не могли быть решены за меньшее количество ходов.
Но, как заметил профессор Девидсон, это число было «чистой теорией», так как никто на самом деле не проверял все возможные конфигурации.
«Мы проводили множество тестов, в надежде обнаружить хотя бы одну комбинацию, которая бы требовала 21 ход для своего решения», — сказал он.
Чтобы проверить все возможные комбинации кубика Рубика, исследователи разделили их на 2.2 миллиарда групп (сомножеств). Каждое такое сомножество состояло из 20 миллиардов комбинаций.
Профессор Девидсон рассказал, что любая попытка просчитать все эти варианты, обречена на провал. Поэтому, чтобы облегчить задачу, они убрали дубликаты и другие сходные комбинации.
В конце концов, им удалось снизить количество комбинаций до 56 миллионов сомножеств, по 20 миллиардов комбинаций в каждом.
Произвести вычисления такого объема на обычном компьютере не представлялось возможным.
Предварительно, команда планировала произвести необходимые вычисления с помощью суперкомпьютера.
«Затем Google выступил с предложением произвести вычисления», — сказал он.
«Мы до сих пор не знаем, какое оборудование они для этого использовали».
Проверка кода
С помощью компьютеров было проверено максимально возможное количество комбинаций. Но, какая-та часть все-таки «проскочила через щели», что вызвало необходимость в применении более медленных алгоритмов.
По мере выполнения расчетов, вероятность нахождения комбинации, для решения которой необходимо сделать более 20 ходов, «снизилась до очень малых чисел».
В конце концов, профессор Девидсон и его команда убедились что проблема была решена и число Бога для кубика Рубика равно 20. «Круг замкнулся», — сказал он. «Кубик Рубика был культовой головоломкой 80х, и благодаря нему я и увлекся математикой».
Предварительные результаты уже были опубликованы в интернете, и по словам профессора Девидсона, будут направлены на экспертную оценку.
«Люди могут произвести проверку кода, который выложен в свободном доступе», — заявил он. «Это можно сделать с помощью небольшого суперкомпьютера».
Но кубик Рубика еще таит в себе немало загадок.
В будущем, команда планирует взяться за четырехслойную версию кубика или за разрешение других проблем, связанных с классическим кубиком Рубика.
«Эта головоломка популярна везде, — это возможно самая популярная головоломка в истории человечества».
Это исследование было выполнено инженером из Google Джоном Детриджом, учителем математики Гербертом Косимба, и программистом из Калифорнии Томасом Рокики.