Главная » Кубик рубика » Алгоритм бога кубик рубика

Алгоритм бога кубик рубика


Найдено число Бога (для Кубика)

Я ни разу не собирал Кубик Рубика. Даже в детстве у меня всегда было много более интересных дел. Но если честно — у меня просто не получалось.

— Эрно Рубик, архитектор, создатель Кубика Рубика

На прошлой неделе произошло событие, которое заставило меня узнать, что такое Алгоритм Бога, Число Бога, и как это связано с кубиками.

Три на три на три — не так уж и сложно

Комбинаторика — это такой раздел математики, в котором все можно по-разному перемешать. Этот беспорядок всем нравится, но любишь кататься, люби и саночки возить. В комбинаторике все эти перемешивания принято подсчитывать. Это не так уж и просто, почти как собирать Кубик Рубика.

Допустим, вы нашли три разноцветных кубика Лего в кафе, где вы ждете кого-то, но этот кто-то опаздывает. Вы начинаете по-разному соединять эти три кубика, создавая всяческие комбинации из них. Вам конечно все равно, вы думаете только о времени. Но комбинаторика знает — вы можете собрать 3! уникальных конфигураций. 3! это не тройка, которая должна вас удивить, это факториал тройки. 3! = 1 × 2 × 3 = 6. «Больше шести конфигураций собрать не получится», — говорит комбинаторика, но нам все равно, время поджимает.

— 3! вариантов перестановок трех кубиков и человечек А. Но разве Лего может ассоциироваться с кафе?

Так вот, если бы вы крутили в кафе Кубик Рубика, дело было бы немного более безнадежным. Когда мы крутим Кубик Рубика, комбинаторика говорит нам следующее:

Я хотел придумать, как бы наглядно объяснить, насколько это много. Как вам такое — если бы все жители Земли смотрели на каждое состояние по 1 секунде, то им понадобилось бы 211 лет, чтобы все пересмотреть*. То есть, чтобы досмотреть до 2010, надо было начинать с 1799 года (представляете, родился Пушкин**, и давай на Кубик глядеть). Но тогда население Земли было меньше, поэтому все равно не успели бы.

— То, что может занять 211 человечеств на целый год, можно купить за 30 рублей. Меня это никогда не перестанет поражать.

Причем тут Бог

Алгоритм Бога — это такой алгоритм, который решает Кубик Рубика за минимальное число ходов. Самое интересное, что никто даже не знает, существует ли этот алгоритм или нет. Это, видимо, единственное, что у них общего с Богом.

Число Бога для Кубика Рубика — минимальное число ходов за которое Алгоритм Бога гарантированно решит любую конфигурацию Кубика. То есть существуют конфигурации, которые Алгоритм Бога решает за 1 ход. Но не сущетсвует таких, на которые он тратит больше ходов, чем Число Бога.

— Версия кубика на неодимовых магнитах, которую могут использовать слепые, больные дальтонизмом и очень нетерпеливые (ее легко разобрать). Возможно, никто кроме Бога так и не узнает алгоритм Бога для Кубика Рубика, но играть в него могут почти все. Автор идеи и фотографии — Эндрю Кертис.

На прошлой неделе несколько исследователей заявили, что они вычислили число Бога.

Число Бога для алгоритма Кубика Рубика — 20. Да, жаль, что не 42.

20 — это довольно обычное число, но в контексте Кубика Рубика нет числа более саркастичного и издевательского. Дело в том, что в Кубике Рубика 20 подвижных деталей. Признайтесь, отчаившись вы хоть раз хотели разобрать Кубик, чтобы потом правильно его собрать и успокоиться? В это время число Бога смеялось над вами!

Ведь деталей-то тоже 20.

Слишком много цифр для одной статьи

Существуют такие конфигурации Кубика Рубика, которые требуют 20 ходов для решения — это стало известно еще в 1995 году. Все, что оставалось доказать исследователям — отсутствие конфигураций, требующих 21 или более ходов для решения.

Что может быть проще, осталось только поперебирать комбинации. Вот как они решили это сделать***:

  1. Разбить исходные 43 252 003 274 489 856 000 состояний на 2 217 093 120 подмножеств
  2. Сократить число подмножеств до 55 882 296, потому что одни получаются из других поворотами или зеркальными отражениями Кубика
  3. Не искать оптимальное решение для каждого состояния, довольствоваться любым не длиннее 20 ходов
  4. Написать программу, которая решает одно подмножество за примерно 20 секунд

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

Нежелание искать оптимальные пути в пункте 3) тоже не каприз. Они конечно могли бы делать это, но им незачем — они просто хотели проверить, что Число Бога это 20, а не найти все оптимальные пути для всех конфигураций.

Обработав все подмножества, они не нашли ни одного состояния, которое требует 21 или более ходов для решения. А значит доказали — Число Бога для Кубика Рубика равно 20.

Как проверить, что вы все поняли?

Найти Число Бога не значит найти Алгоритм Бога. Если вы понимаете это и согласны, то вы все поняли. Иначе, можете попробовать перечитать определение Алгоритма Бога и Числа Бога.

Как утереть парням нос?

Вы можете обставить их, я не шучу. Для это вам надо придумать алгоритм, который в пункте 3) будет искать только оптимальные ходы. Это и будет Алгоритмом Бога, а вам, вероятно, будут целовать ноги.

Интересные факты по теме

  • Конфигурации Кубика, которые требуют 20 ходов для решения, не так уж часто встречаются (примерно 0,0000000007% от общего числа конфигураций). Первая была обнаружена только через 15 лет после появления Кубика на свет. 
  • Компьютеры решают Кубик Рубика быстрее, чем люди на них смотрят. Для перебора всех вариантов понадобилось 35 ядро-лет. Это значит, что одно ядро одного компьютера, на котором производились вычисления, справилось бы с ними за 35 лет. Сколько ядер было у них в распоряжении, исследователи не сообщают.
  • Компьютерные мощности для решения задачи предоставила компания  Google, в которой работает один из исследователей.

Зачем?

Иногда в конце статей я задаю вопрос — почему? Но сегодня другая история, ведь не совсем понятно, зачем знать число Бога для Кубика Рубика. Если вы думаете, что я сейчас скажу: «Попались!», — пошучу шутку и невзначай расскажу, какую великую пользу принесет это открытие, то вы ошибаетесь. Я не знаю зачем. Но я знаю, что мы можем вынести для себя из всего этого.

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

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

Разделяйте и властвуйте!

* — в большом числе одинаковые конфигурации Кубика, повернутые и отраженные, учитываются как разные; а под населением Земли понимается 6,5 миллиардов человек, которые не спят, не едят, а только пялятся на кубики 24 часа в сутки ** — в 1799 году родился самый неоцененный мною писатель Александр Сергеевич Пушкин *** — пункты «???» и «PROFIT» опущены из-за уважения к читателю

See you!

www.lookatme.ru

Число Бога – это число ходов для сборки Кубика Рубика

кубик Рубика и число Бога

Число Бога - это максимальное число ходов за которые можно решить всем известную головоломку кубик Рубика. Таким образом как бы ни были перепутаны грани и ячейки в кубике его можно решить не более чем за 20 поворотов. А алгоритм сборки кубика Рубика называется “алгоритмом Бога“.

Так чему же равно максимально удаленное решение кубика Рубика, или так называемое “число Бога”, ведь многие пытаются собрать его годами?

Интересный факт: речь пойдет о британце Грэме Парке. Он посвятил сборке Кубика Рубика целых.. 26 лет! За это время он обзавелся бессоницей, радикулитом, почти лишился семьи, но это не остановило его самостоятельно собрать этот “проклятый” кубик. И вот, в один прекрасный момент, когда Грэму было уже 45 лет он собрал Кубик Рубика без чье-либо помощи, и по словам родственников – разрыдался как ребенок. Так что друзья, нельзя превращать какое-либо занятие в навязчивую идею, тем более такое, как бы сказать, глупое занятие как сбор Кубика Рубика)

Мы немного отвлеклись, теперь продолжим дальше о числе Бога. По последним данным это число всего навсего 20 – эх, Грэм, знал бы ты его, то понимал бы насколько был близок к разгадке все эти длинные годы. Как то описать “алгоритм Бога” по которому получили число очень и очень сложно, и описание нет как такового – это результат трудоемких вычислений.

Таким образом, в самых сложных позициях Кубика Рубика, от решения нас будут отделять 20 ходов –  а таких позиций, представьте себе, двенадцать миллионов.

qbici.ru

Кубик Рубика: воплощение гармонии, алгоритм Бога

Поделиться

Отправить по e-mail Скопировать ссылку

13 июля 1944 года родился Эрне Рубик, изобретатель знаменитой головоломки, названной в его честь. Wеllup.me собрал интересные факты о всемирно известном кубике.

Учебное пособие

Эрне Рубик в 1970-е годы преподавал архитектуру и дизайн в Академии прикладных искусств и ремесел в Будапеште. Кубик создавался для студентов, он должен был помочь им освоить теорию групп и развить навыки пространственного мышления. Кстати, сам Рубик в первый раз собирал свою головоломку целый месяц! Интересно, что размер стороны кубика, 57 мм, научное сообщество признало «золотым стандартом».

43 252 003 274 489 856 000

Число, которое вы видите выше, — это 43 с лишним квинтиллионов! Именно такое количество возможных конфигураций дают 6 сторон, 21 часть, 54 поверхности головоломки. Если бы вы поворачивали кубик Рубика каждую секунду, вам бы потребовалось 1400 триллионов лет, чтобы пройти все возможные комбинации. Зная это, перестаешь удивляться тому, что сам создатель головоломки собирал ее целый месяц!

Алгоритм Бога

Существует алгоритм, позволяющий собрать головоломку из любого положения за 20 ходов. Правда, доказали его существование только теоретически. В 2010 году собралась команда:  программист Томас Рокики, математики Герьерт Коцемба, Морли Дэвидсон и инженер компании Google Джон ...

Полный текст материала доступен зарегистрированным пользователям

Чтобы продолжить чтение войдите или зарегистрируйтесь

Это абсолютно бесплатно и займет не более минуты.После регистрации вам будут доступны не только материалы целиком, но и наши рекомендательные сервисы

Источник: Wellup.me

Автор: Юлия Муштакова

Поделиться

Отправить по e-mail Скопировать ссылку

Пожалуйста, оцените статью:

wellup.me

Алгоритм Бога

Previous Entry | Next Entry

smartcubeЛюбая позиция Кубика Рубика может быть решена не более, чем за 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. Эта позиция была самой сложной для наших программ:

Метки:

smartcube.livejournal.com

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