23 апреля 2014 13:12

ЦБ USD 35.6688 (+0.1299); EUR 49.2978 (+0.1937)

Москва: 14...16 °С

18+

Наука20 строк

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

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

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

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

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

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

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

  • Livejournal

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


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


Умные очки - это не только Google Glass


Пять главных хитов Kickstarter


18 самых скандальных фактов о «Лолите»


8 неизвестных фактов о Чарли Чаплине


Он всегда следит за тобой: обзор умного браслета Jawbone UP24


Шесть городов России, о которых вы не знали


Пасха по-монастырски


Как победить весеннюю депрессию


Где в Британии хорошая погода


Как просто остаться без квартиры в России

/nm2012/ssi/right_stuff/else.shtml