Вы здесь: Главная -> Новости -> 2011 -> Новости за июнь -> Математики разобрались с гигантскими кубиками Рубика
Новости науки
2016:
78
2015:
12345678910
2014:
123456789101112
2013:
123456789101112
2012:
123456789101112
2011:
123456789101112
2010:
123456789101112
2009:
123456789101112
2008:
123456789101112
2007:
123456789101112
2006:
123456789101112
Рейтинг@Mail.ru

Математики разобрались с гигантскими кубиками Рубика

Математики из Массачусетского технологического университета оценили количество ходов, необходимых для решения кубика Рубика (то есть приведения граней куба к одному цвету) произвольного размера. Препринт их статьи появился на сайте arXiv.org.

Исследования кубика Рубика математиками начались в начале 80-х годов прошлого века (сама головоломка была создана в 1974 году). Как оказалось, группа симметрий кубика, действующая на множестве его квадратов, довольно сложна и плохо поддается изучению. В 2010 году специалисты по теории игр просчитали на суперкомпьютере все 43 252 003 274 489 856 000 возможных первоначальных позиций для стандартного кубика Рубика (3 на 3 на 3) и установили, что из любого начального положения кубик можно собрать всего за 20 ходов.

В рамках нового исследования ученых интересовала асимптотическая оценка количества движений, необходимых для решения кубика Рубика (хотя, в данном случае, его правильнее было бы называть прямоугольным параллелепипедом) с сторонами произвольной величины. В качестве параметра оценки выступало число n - длина максимальной стороны головоломки, а "асимптотическая" в названии означает, что оценка не точная, но с ростом n оптимальное число ходов растет как оценка.

Исследователям удалось установить, что в общем случае количество ходов есть O(n2) - то есть число необходимых для решения движений куба увеличивается примерно как квадрат n, умноженный на некоторую константу. При этом учеными предложен непосредственный алгоритм решения, который реализует предложенную оценку.

В двух частных случаях ученым удалось улучшить этот результат. Так, оказалось что для "кубического" кубика Рубика, то есть головоломки с размерами n на n на n, и для "веревки" Рубика - головоломки с размерами n на n на 1, оценка выглядит как O(n2/log n). Последний эффект связан с тем, что за одно движение в подобных головоломках можно ставить на нужное место сразу несколько квадратов.

Задача о решении кубика Рубика относится к классу алгоритмических задач реорганизации. Типичным примером такой задачи, встречающимся на практике, является перестановка нужным образом коробок на складе.

Источник: Лента.ру



главная :: наверх :: добавить в избранное :: сделать стартовой :: рекомендовать другу :: карта сайта :: создано: 2011-06-30
Наша кнопка:
Научно-образовательный портал