Я ни разу не собирал Кубик Рубика. Даже в детстве у меня всегда было много более интересных дел. Но если честно — у меня просто не получалось.
— Эрно Рубик, архитектор, создатель Кубика Рубика
На прошлой неделе произошло событие, которое заставило меня узнать, что такое Алгоритм Бога, Число Бога, и как это связано с кубиками.
Комбинаторика — это такой раздел математики, в котором все можно по-разному перемешать. Этот беспорядок всем нравится, но любишь кататься, люби и саночки возить. В комбинаторике все эти перемешивания принято подсчитывать. Это не так уж и просто, почти как собирать Кубик Рубика.
Допустим, вы нашли три разноцветных кубика Лего в кафе, где вы ждете кого-то, но этот кто-то опаздывает. Вы начинаете по-разному соединять эти три кубика, создавая всяческие комбинации из них. Вам конечно все равно, вы думаете только о времени. Но комбинаторика знает — вы можете собрать 3! уникальных конфигураций. 3! это не тройка, которая должна вас удивить, это факториал тройки. 3! = 1 × 2 × 3 = 6. «Больше шести конфигураций собрать не получится», — говорит комбинаторика, но нам все равно, время поджимает.
— 3! вариантов перестановок трех кубиков и человечек А. Но разве Лего может ассоциироваться с кафе?
Так вот, если бы вы крутили в кафе Кубик Рубика, дело было бы немного более безнадежным. Когда мы крутим Кубик Рубика, комбинаторика говорит нам следующее:
Я хотел придумать, как бы наглядно объяснить, насколько это много. Как вам такое — если бы все жители Земли смотрели на каждое состояние по 1 секунде, то им понадобилось бы 211 лет, чтобы все пересмотреть*. То есть, чтобы досмотреть до 2010, надо было начинать с 1799 года (представляете, родился Пушкин**, и давай на Кубик глядеть). Но тогда население Земли было меньше, поэтому все равно не успели бы.
— То, что может занять 211 человечеств на целый год, можно купить за 30 рублей. Меня это никогда не перестанет поражать.
Алгоритм Бога — это такой алгоритм, который решает Кубик Рубика за минимальное число ходов. Самое интересное, что никто даже не знает, существует ли этот алгоритм или нет. Это, видимо, единственное, что у них общего с Богом.
Число Бога для Кубика Рубика — минимальное число ходов за которое Алгоритм Бога гарантированно решит любую конфигурацию Кубика. То есть существуют конфигурации, которые Алгоритм Бога решает за 1 ход. Но не сущетсвует таких, на которые он тратит больше ходов, чем Число Бога.
— Версия кубика на неодимовых магнитах, которую могут использовать слепые, больные дальтонизмом и очень нетерпеливые (ее легко разобрать). Возможно, никто кроме Бога так и не узнает алгоритм Бога для Кубика Рубика, но играть в него могут почти все. Автор идеи и фотографии — Эндрю Кертис.
На прошлой неделе несколько исследователей заявили, что они вычислили число Бога.
Число Бога для алгоритма Кубика Рубика — 20. Да, жаль, что не 42.
20 — это довольно обычное число, но в контексте Кубика Рубика нет числа более саркастичного и издевательского. Дело в том, что в Кубике Рубика 20 подвижных деталей. Признайтесь, отчаившись вы хоть раз хотели разобрать Кубик, чтобы потом правильно его собрать и успокоиться? В это время число Бога смеялось над вами!
Ведь деталей-то тоже 20.
Существуют такие конфигурации Кубика Рубика, которые требуют 20 ходов для решения — это стало известно еще в 1995 году. Все, что оставалось доказать исследователям — отсутствие конфигураций, требующих 21 или более ходов для решения.
Что может быть проще, осталось только поперебирать комбинации. Вот как они решили это сделать***:
Пункт 1) очень важен для того, чтобы выполнить пункт 2). Надо быть хитрым лисом, чтобы составить подмножества именно так, чтобы их потом сократить.
Нежелание искать оптимальные пути в пункте 3) тоже не каприз. Они конечно могли бы делать это, но им незачем — они просто хотели проверить, что Число Бога это 20, а не найти все оптимальные пути для всех конфигураций.
Обработав все подмножества, они не нашли ни одного состояния, которое требует 21 или более ходов для решения. А значит доказали — Число Бога для Кубика Рубика равно 20.
Найти Число Бога не значит найти Алгоритм Бога. Если вы понимаете это и согласны, то вы все поняли. Иначе, можете попробовать перечитать определение Алгоритма Бога и Числа Бога.
Вы можете обставить их, я не шучу. Для это вам надо придумать алгоритм, который в пункте 3) будет искать только оптимальные ходы. Это и будет Алгоритмом Бога, а вам, вероятно, будут целовать ноги.
Иногда в конце статей я задаю вопрос — почему? Но сегодня другая история, ведь не совсем понятно, зачем знать число Бога для Кубика Рубика. Если вы думаете, что я сейчас скажу: «Попались!», — пошучу шутку и невзначай расскажу, какую великую пользу принесет это открытие, то вы ошибаетесь. Я не знаю зачем. Но я знаю, что мы можем вынести для себя из всего этого.
На самом деле, мы давно уже это вынесли это для себя — если разбить задачу на подзадачи, то ее решение заметно упрощается. Вся проблема в том, чтобы правильно разбить.
А еще наступают новые времена для науки, когда некоторые вещи становится быстрее проверить, чем доказать. Но об этом я однажды уже писал мельком.
Разделяйте и властвуйте!
* — в большом числе одинаковые конфигурации Кубика, повернутые и отраженные, учитываются как разные; а под населением Земли понимается 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. В таблице ниже собраны все результаты:Для длин от 16 и больше, числа являются примерными. Наши исследования подтвердили все первоначальные данные до 14 строки включительно, а 15 строка — новый результат. На 11 августа мы обнаружили 12 миллионов позиций с длиной решения 20. Эта позиция была самой сложной для наших программ:
smartcube.livejournal.com