Лого

Наборы с поздравлением!

Теперь вы можете бесплатно заказать
персональное поздравление
в составе набора для рукоделия. Удивите своих близких! Просто укажите при заказе!
НатаТойс — Шейте сами

наборы для рукоделия:   шьём подушки и мягкие игрушки



Корзина
корзина

В Вашей корзине нет товаров

оформить заказ



Кубик рубика за 20 ходов


Кубик Рубика за 20 шагов

Любая позиция Кубика Рубика может быть решена не более, чем за 20 шагов. Несколько лет назад было доказано, что для Кубика Рубика есть решение за 23 хода. Теперь это число сократилось до 20. Чтобы это сделать, потребовалось 35 (тридцать пять) лет компьютерного времени, пожертвованного Гуглом. Каждый блок решения использовал свой алгоритм — последовательность шагов для достижения нужной конфигурации. Например, один алгоритм предназначался для решения верхней грани, а другой — для позиционирования средних краев. Есть множество различных алгоритмов, различающихся по степени сложности и количеству требуемых шагов, но те, которые может запомнить человек, обычно требуют больше 40 шагов. Разумно полагать, что Бог может использовать более эффективный алгоритм, который решает задачу за наикратчайшее число шагов. Этот алгоритм известен как “алгоритм Бога”. Число шагов в худшем случае называется числом Бога. В конце концов, было показано, что это число — 20. После изобретения Кубика Рубика пятнадцать лет ушло на поиск позиции, которая наверняка решается за 20 шагов. Через 15 лет после этого мы докажем, что 20 шагов достаточно для любой позиции.

История числа Бога
К 1980 году было установлено, нижняя граница — 18, а верхняя — вероятно, около 80. В таблице ниже собраны все результаты:

Как мы это сделали
Как мы справились с 43 252 003 274 489 856 000 позициями Кубика Рубика?
  • Мы разделили все позиции на 2 217 093 120 множеств — по 19 508 428 800 позиций в каждом.
  • Мы уменьшили число множеств для решения до 55 888 296 на основе симметрии и покрытии множества.
  • Мы не искали оптимальное решение, а только решения с длиной 20 или менее шагов.
  • Мы написали программу, находящее решение для одного множества за 20 секунд.
  • Потребовалось 35 лет компьютерного времени для поиска решений всех конфигураций в каждом из 55 888 296 множеств.
Деление пространства позиций
Мы разбили большую задачу на 2 217 093 120 меньших подзадач: в каждую входило по 19,508,428,800 различных позиций. Одна такая подзадача легко помещается в память современного компьютера, и этот метод позволил достаточно быстро получить решение.
Симметрия
Если повертеть Кубик Рубика влево-вправо или вверх-вниз, то, по сути, ничего не изменится: число шагов в решении останется тем же самым. Вместо того, чтобы решать все эти позиции, можно получить решение для одной и распространить его на повернутые позиции. Есть 24 различных ориентации в пространстве и 2 зеркальных положения Кубика для каждой позиции, что позволяет уменьшить число решаемых позиций в 48 раз. Если использовать аналогичные рассуждения и воспользоваться поиском задачи “покрытия множества”, то число подзадач уменьшается от 2 217 093 120 до 55 882 296.
Хорошие и оптимальные решения
Оптимальное решение содержит достаточное количество шагов, но не больше, чем надо. Так как уже известна одна позиция, для которой требуется 20 шагов, то мы можем не искать оптимальное решение для каждой позиции, а только решения в 20 или менее шагов. Это многократно убыстряет задачу.
Оборудование
У нас была возможность решить 55 882 296 подзадач на мощностях Гугла и выполнить все вычисления за несколько недель. Гугл не раскрывает характеристики компьютеров, но было затрачено 1.1 миллиард секунд компьютерного времени (Intel Nehalem, four-core, 2.8GHz) на выполнение расчетов.
Самая трудная позииция
Мы знали в течении 15 лет, что есть позиции, которые требует 20 шагов, но мы доказали, что ни для одной позиции и не надо больше. Позиции с решениями в 20 шагов редки, но их вполне возможно встретить в реальности. Вероятность встретить такую позицию варьируется от 10^(-9) до 10^(-8). Мы точно не знаем точное количество таких позиций. Таблица дает оценку числа позиций для каждой длины решения.

Для длин от 16 и больше, числа являются примерными. Наши исследования подтвердили все первоначальные данные до 14 строки включительно, а 15 строка — новый результат. На 11 августа мы обнаружили 12 миллионов позиций с длиной решения 20. Эта позиция была самой сложной для наших программ:

Метки:

habr.com

Кубик Рубика можно собрать за 20 ходов

      Собрать кубик Рубика из любого исходного состояния можно не более чем за 20 ходов.

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

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

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

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

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

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

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

Источник

maxxbay.livejournal.com

Кубик Рубика можно собрать за 20 ходов

Собрать кубик Рубика из любого исходного состояния можно не более чем за 20 ходов.

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

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

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

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

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

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

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

maxxbay.livejournal.com

Как собрать кубик Рубика. Самая легкая схема

Кубик Рубика на сегодняшний день признан одной из самых популярных в мире головоломок, состоящей из разноцветных секторов, соединенных в одну фигуру. Ее создателем стал венгерский скульптор, который сделал наглядное пособие по теории групп для своих студентов. Сегодня же эта игрушка является наиболее продаваемой в мире.

Строение кубика

Прежде чем понять, как собирать этот кубик, необходимо разобраться с его строением. Сегодня можно встретить самые разные формы и размеры головоломки. Стандартный кубик Рубика состоит из 12 ребер и имеет 8 углов. Внутри имеется крестовина на которой и крепятся все детали.

Концом крестовины является один из квадратов, вокруг которого и собираются другие квадраты с таким же самым цветом. Собранной головоломка считается в том случае, если на каждой из 6 сторон кубика будет один цвет.

В оригинальном кубике желтый цвет в любом случае будет располагаться непосредственно напротив белого. И если по какой-то причине кубик разобрать и потом неправильно сложить, то собрать головоломку уже будет невозможно.

Помимо центра фигуры, ее постоянными составляющими есть углы, на каждом из которых по 3 цвета. Независимо от того, как вы будете менять положение цветов в фигуре, цвет углов будет оставаться одним и тем же. Для сбора головоломки, средние и угловые сектора перемещаются исходя из того цвета, который установлен на центральном секторе.

Каждая из сторон кубика имеет свое название.

При сборке головоломки необходимо не только перемещать его стороны, но и менять пространственное положение кубика. Такие движения получили название перехват. Схематически это можно показать следующим образом.

В Интернете можно найти массу алгоритмов сборки головоломки. Если в нем указана исключительно буква, то положение стороны нужно проводить по часовой стрелке. А знак апостроф (‘) возле буквы указывает на то, что вращать следует против часовой стрелки. Цифра 2 после буквы означает, что сторону следует провернуть дважды. К примеру, D2’ указывает на то, что нижнюю сторону кубика следует дважды провернуть против часовой стрелки.

Инструкция для новичков

Проще всего складывать кубик Рубика следующим образом:

  1. Начинать собирать кубик следует с правильного креста. Это значит, что с каждой стороны у вас будут центр и ребра одного цвета.
  2. Чтобы это сделать следует найти белые центр и ребра, после чего собрать крест, следуя инструкции на картинке.

  1. Если все сделать правильно, то на одной стороне можно увидеть крест. Вначале крест окажется неправильным и его следует немного переделать. Для этого нужно поменять местами ребра.
  2. Этот алгоритм имеет название «пиф-паф».

  1. На следующем этапе нужно отыскать белый угол снизу и разместить над ним угол красного цвета. Получить такой результат можно несколькими способами, которые выбираются исходя из изначального расположения белого и красного углов.

  1. Таким образом, получится такой вид кубика.

  1. Теперь можно приступать ко второму слою. На данном этапе предстоит найти четыре ребра, где отсутствует желтый цвет и разместить их посредине второго слоя. Кубик нужно крутить до того момента, пока цвет центра и граней не будет одинаковым. Для этого можно использовать один из вариантов.

  1. На следующем этапе собирается желтый крест. В некоторых случаях он может получиться самостоятельно без вашего дополнительного участия, но такое бывает достаточно редко. В основном он может располагаться одним из следующих образов.

  1. После того, как желтый крест собран, нужно воспользоваться одним из ниже приведенных вариантов.

  1. Далее собираются углы на верхнем слое. Для этого один из углов ставится одним из движений: U, U’ и U2. Важно, чтобы цвета угла на всех слоях оказались одинаковыми. На этом этапе нужно держать кубик белой стороной к себе.

  1. На заключительном этапе собираются ребра на верхнем слое. Если все было сделано правильно, то возможно 4 варианта, которые решаются следующим образом.

Метод Джессики Фридрих

Данная методика основана на скорости, с которой собирается головоломка. Но такой вариант не подойдет для тех, кто впервые в жизни взял в руки кубик.

  1. Вначале собирается крест с гранями сбоку. Такой этап имеет название «Cross».
  2. Далее собираются одновременно два слоя кубика «F2L». После чего применяется один из таких алгоритмов.

  1. После этого полностью собирается верхний слой. Этот этап получит название OLL и состоит из таких алгоритмов.

  1. Последний этап носит название PLL. Для него используют такие алгоритмы.

Как собрать кубик в 20 ходов

В 1982 году впервые были проведены соревнования по скорости сборки данной головоломки. После чего многие стали самостоятельно разрабатывать различные алгоритмы, способные быстро собрать кубик, используя минимальное количество действий.

Алгоритмом, состоящим из минимального количества ходов признан, так называемый «Алгоритм Бога», который выполняется в 20 ходов.

Секреты сборки головоломки

Если вы поставили перед собой цель научиться очень быстро собирать кубик Рубика, то нужно запомнить несколько секретов:

  1. Начинать собирать головоломку лучше всего выбрав за основу желтый или белый цвета.
  2. Методика сборки головоломки предполагает, что на это должно уходить минимальное количество времени. Ведь даже миллисекунда может позволить установить новый рекорд. Именно поэтому чаще всего сборка начинается с креста по нижней грани.
  3. Лучший результат всегда будет у того, кто может просчитывать свои действия на 1 шаг вперед.
  4. Важно, чтобы все части кубика хорошо вращались. Чтобы улучшить его в недорогих моделях головоломки, можно воспользоваться специальной смазкой.

Кубик Рубика – достаточно хитрая головоломка, которая может заинтересовать не только взрослого, но и ребенка. Чемпионами по скорости его сборки чаще всего становятся подростки. Последний рекорд принадлежит 15-ти летнему Колину Бернсу, который смог полностью собрать кубик за 5,2 секунды.

pix-feed.com


Смотрите также