Дата: 2013-11-06Редактор: Загуменный Владислав
Математики технологического университета в Массачусете оценили количество ходов, которые необходимо выполнить чтобы решить головоломку кубик Рубика любого размера
По данным СМИ исследовать кубик Рубика математики начали еще в начале 80-х годов прошлого века, так как сама головоломка была придумана в далеком 1974 году. По выводам математиков оказалось что группа симметрий кубика, которая действует на множество его квадратиков, очень сложна и неохотно поддается изучению.
В 2010 году ученые просчитали на супермощном компьютере по теории игр все 43 252 003 274 489 856 000 возможных первоначальных алгоритмов для стандартного Рубиковского кубика (3 Х 3 Х 3) и сделали выводы, что из какого либо начального положения, таинственный кубик можно собрать лишь за коротких 20 ходов.
По плану новых исследований ученых очень заинтересовала асимптотическая показательная оценки количества движений, которые необходимы для решения головоломки Рубика (кстати, ученные называю его простым прямоугольным параллелепипедом) со сторонами с любой произвольной величиной. При эксперименте параметром оценки выступало число p - максимальная длинна стороны головоломки, а слово «асимптотическая» в выше упомянутом названии указывает на то, что оценка не точная, но с ростом числа p оптимальное число ходов растет так же как и оценка.
Ученным удалось установить, что в общем случае количеством ходов есть формула O(p2) - что значить то, что число необходимых движений куба, для его решения, увеличивается как квадрат p, умноженный на константу заранее не известную. После этого утверждения учеными был предложен уточненный алгоритм решения, который подтверждает предложенную оценку. Алгоритм предложенный учеными очень похож на онлайн игру igonki.ru.
В ходе эксперимента ученымы в частных случаях удалось улучшить свой результат. По эксперименту оказалась истина: для «квадратного» кубика Рубика, то есть размеры головоломки должны быть p на p на p, и для «неквадратного» кубика Рубика - головоломки с размерами p на p на 1, решение выглядит как O(p2/log p). Последний момент связан с тем, что одним движением в неквадратных головоломках можно ставить на свое место сразу несколько элементов.
Решение задачи сложить кубика Рубика относится к ветке алгоритмических реорганизаций. К примеру к такой задачи можно отнести перестановку нужным образом на складе коробок.
Выберите достойную оценку заметке:
5 последних заметок категории "Разное"
Представленное на фото здание удивляет своим необычным дизайнерским решением. Этот оранжевый кубик Рубик находится в городе Леоне...
«Кубик Рубика» празднует своё 40-летие. Трудно, наверное, найти человека, который хоть раз в жизни не держал в руках «Кубик Рубика». И, если это увлечение давно забыто, то сейчас самое время о нём вспомнить. Игрушка празднует своё 40-летие...
30 августа в Харькове прошел чемпионат по скоростной сборке кубика Рубика и других головоломок Kharkiv Cube Day 2014...
Состязания по скоростной сборке головоломки пройдут в актовом зале Национального университета Юридическая академия имени Ярослава Мудрого
Оставьте комментарий
Для комментария нажмите на картинку "змейка Рубика"!