Ученые разработали универсальный алгоритм для сборки кубиков Рубика любого размера

Сегодня нет ничего удивительного в том, что компьютеры научились собирать кубики Рубика, на это способны даже процессоры смартфонов не первой свежести. Ведь данная задача связана с простой логикой и четкими математическими моделями. Теперь же решение данной задачи упростилось, инженер Эрик Демейн (Erik Demaine) разработал алгоритм, позволяющий собирать кубики Рубика любого размера.

Изначально он занимался исследованием головоломки третьего порядка, это кубик с тремя частями на каждом ребре. В натуральном виде задача не так-то проста, ведь в данном случае общее число комбинаций кубика составляет 43 квинтиллиона. А что будет, если речь идет о кубике Рубика 11 порядка? Страшно даже представить! Первым делом автор разработал универсальный алгоритм, который позволяет перемещать любую клетку кубика на заданную позицию, сохраняя положение всех остальных деталей.

 

В общем случае для этого требуется одно и то же число ходов, соответствующее квадрату числа клеток на одном ребре. Этого уже достаточно, однако для скоростной сборки кубика этого маловато. Поэтому авторы усовершенствовали алгоритм, заставив перемещаться не одиночные клетки, но и целые блоки. В этом случае число ходов сокращается в lg(n) раз. Таким образом, для того, чтобы определить общее число ходов необходимо возвести в квадрат порядок головоломки и разделить его на десятичный логарифм от порядка кубика. Хотелось бы посмотреть, как какой-нибудь робот соберет кубик Рубика с ребром в 20 клеток.

4 Июля, 2011

Комментарии

Источник: MobileDevice.ru

Ваш комментарий к новости:
Комментарии публикуются после проверки администратором. При добавлении отрицательного комментария читайте соглашение об использовании. Мы не публикуем: сообщения, не относящиеся к новости: "Ученые разработали универсальный алгоритм для сборки кубиков Рубика любого размера".
Ваше имя:		E-mail:
Оценка:	нет 1 2 3 4 5
*Cообщение (30-1000 зн.):

* * *

Еще новости