Наука20 строк

Кубик Рубика за 20 ходов

Собрать кубик Рубика из любого исходного состояния можно не более чем за 20 ходов. К такому выводу пришла группа ученых под руководством профессора Морли Дэвидсона из университета Кента в штате Огайо.

С помощью компьютеров корпорации Google исследователям удалось перебрать все возможные комбинации головоломки, изобретенной венгерским архитектором Эрне Рубиком в 1974 году. В результате выяснилось, что так называемое число Бога — минимально необходимое количество ходов для сборки кубика Рубика из любой начальной комбинации — равно 20, сообщает РИА «Новости».

По словам Дэвидсона, предположение, что «число Бога» равно именно 20, было основано лишь на вере ученых: никому ранее не удавалось проверить все конфигурации головоломки. «Мы втайне надеялись, что в ходе тестов найдем комбинацию, для которой нужен 21 ход», — сказал Дэвидсон.

Чтобы решить эту задачу, ученые разбили все возможные исходные состояния примерно на 2,2 миллиарда групп по 20 миллиардов вариантов в каждой — именно столько состояний у классического кубика Рубика. Выявляя одинаковые и симметричные состояния, исследователи сократили тестовый набор до 56 миллионов групп. Корпорация Google предложила ученым свой парк компьютеров для проверки всех этих комбинаций. По оценкам Дэвидсона, хорошему настольному ПК с четырехъядерным процессором микроархитектуры Nehalem и тактовой частотой 2,8 гигагерца на это потребовалось бы около 35 лет машинного времени.

Ученые опубликовали результаты своей работы в интернете и собираются подготовить статью для научного журнала. По их словам, протестировать код сможет любой обладатель небольшого суперкомпьютера. Сами исследователи собираются продолжить работу и, в частности, найти «число Бога» для других вариантов головоломки.

Как сообщала «Газета.Ru», два с половиной года назад американский программист Томас Рокицкий доказал: среди конфигураций головоломки не найдётся ни одной, на решение которой идеальному мозгу потребуется больше 25 поворотов.

  • Livejournal


Главное сегодня






/nm2012/ssi/right_stuff/else.shtml

Читайте также


10 лучших упражнений для тех, кто хочет укрепить свою память


Самые лучшие и худшие платья церемонии вручения «Оскар-2015»


5 самых необычных десертов с шоколадом


Как стать чище


Белый дом на страже интернета


Вирус стратегического назначения


Как выглядеть умнее, чем вы есть


Что надеть приличной женщине


Как Motorola поссорилась с Apple


Как российские и украинские хакеры украли миллиард

АРХИВ
           
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31