Заметки на все случаи жизни
(c) Serg
Главная | Каталог статей | Регистрация | Вход
Среда
22.11.2017
20:12
Приветствую Вас Гость | RSS
Главная » Статьи » Разное

Математики вывели формулу сборки гигантских кубиков Рубика

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

Исследования кубика Рубика математиками начались в начале 80-х годов прошлого века (сама головоломка была создана в 1974 году). Как оказалось, группа симметрий кубика, действующая на множестве его квадратов, довольно сложна и плохо поддается изучению.

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

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

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

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

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

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

В результате выяснилось, что так называемое «число Бога», минимально необходимое количество ходов для сборки кубика Рубика из любой начальной комбинации, равно 20. «Теперь мы точно знаем, что волшебное число - это 20», - заявил Дэвидсон.

До 1995 года считалось, что теоретический минимум для сборки популярной головоломки составляет 18 ходов, однако математик Майкл Райд нашел исходную конфигурацию, из которой кубик Рубика можно собрать лишь за 20 ходов.

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

Чтобы решить эту задачу, ученые разбили все возможные исходные состояния примерно на 2,2 миллиарда групп по 20 миллиардов вариантов в каждой - именно столько состояний у классического кубика Рубика. Выявляя одинаковые и симметричные состояния, исследователи сократили тестовый набор до 56 миллионов групп.

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

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

Читаем еще в разделе "Новости":
[04.02.2010] [Политика]
Уже трое "нунсовцев" отозвали свои голоса за закон о выборах (0)
[07.04.2010] [Политика]
Президент Виктор Янукович назначил глав пяти областей, а также города Севастополя (0)
[15.02.2010] [Политика]
Янукович намерен укрепить отношения Украины с Россией (0)
[15.02.2010] [Политика]
Депутаты проголосуют за перенос местных выборов 16 или 17 февраля, - Литвин (0)
Категория: Разное | Добавил: Serg_m (01.07.2011)
Просмотров: 902 | Рейтинг: 0.0/0 |
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа
Поиск
Карта пробок
Пробки на Яндекс.Картах
Погода
Валюта и металлы
Курсы наличного обмена на сегодня
Курсы НБУ на сегодня
Курсы НБУ на сегодня
Курсы НБУ на сегодня
Курсы НБУ на сегодня
Курсы НБУ на сегодня
Курсы НБУ на сегодня
Курсы НБУ на сегодня
Все АЗС
Полезные странички
  • Кредит. Расчет
  • Читать, читать...
  • ООО "Масалет"
  • ПП "Автократ"
  • Видеопробки
  • Заправки WOG
  • Заправки ОККО
  • Дороги Украины
  • Дороги Navizor
  • Дороги Автострада
  • Кадастрова карта
  • Правозащитные организации
  • Автоподставы
  • Полезные ссылки
  • Площадь, расстояние на карте
  • Каталог сайтов
  • Каталог файлов
  • Категории раздела
    Разное [360]
    Прочие статьи, которые не выделены в отдельные темы
    Техника [39]
    Банковские вопросы [14]
    Статьи о банковской сфере, кредитах, депозитах, задолженностях, нормативных документах затрагивающих банковские дела
    Дети [41]
    Закон [20]
    Нормативные документы и ситуации
    Авто [150]
    Информация о автомобилях, автоправо, и прочее...
    Строительство [45]
    Статьи о строительстве, стройматериалах, технологиях, строительной технике, инструментах...
    Здоровье [102]



    Украинская Баннерная Сеть
    Copyright Serg © 2009-2017
    Яндекс цитирования Rambler's Top100