zeftera.ru.

Компьютер сумел скопить кубик-рубика

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

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

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

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

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

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

Фото с веб-сайта: wikipedia.org

Ресурс: «Lenta.ru»

Оставить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>