21 октября 2014 17:29

ЦБ USD 40.8815 (-0.1635); EUR 52.1198 (-0.4055)

Москва: 2...4 °С

18+

Наука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

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


Золотой iPad и iMac по цене машины


Что ждет русского туриста в США


33 цитаты Оскара Уайльда, с которыми невозможно поспорить


Почему у вас такое бездарное начальство


Свежие леденцы от Google


Что на самом деле сделает вас элегантным


Как получить высший балл?


На что тратят деньги очень богатые люди


Почему мужчина уходит из семьи, если о нем заботятся


Я не такая, я жду трамвая