Сборка Кубика Рубика генетическим алгоритмом online без смс / Хабрахабр. В то время пока я собирался на ланч, мой ко- воркер Дейв окликнул меня: «Хэй, Алекс, а ты не хочешь заниматься улучшениями навыков своего программирования?». Это было интересное предложение, но я склонялся ответить отказом: «Сейчас я занимаюсь развитем навыков говорения на языках, дружище!». Утро началось с того, что я добрался до почты и заполучил в руки копеечный китайский Кубик, случайно заказанный на али. К обеду я проштудировал мануал сборки и обновил мышечную память, а к вечеру пришло осознание, что я наигрался.
Будущее кубика было ясным: он будет пылиться на полке, раз или два в неделю может быть я буду его собирать, чтобы привести мысли в порядок или отвлечься, но не более того. Соревнование в механической скорости сборки?
Однажды отец принес с работы нарисованную вручную схему по сборке кубика Рубика. Как оказалось, iPhone тоже умеет собирать кубик Рубика. Программы, написанные мною. Сборка кубика рубика. Робот собирает кубик Рубика, менее чем за одну секунду - Duration: 2:03. Простая схема сборки Кубика Рубика 3х3, она поможет вам быстро и легко научиться его собирать.
Non merci, уж лучше скворечники делать. После недолгого изучения я узнал рекогнисцировку. Для начала, число Бога уже давно найдено и равно 2. Правда задача сборки от этого не упрощается, т. Алгоритм Бога предполагает под собой некое разумное количество использованной памяти, и в то же время обязан обеспечить минимально возможное число модификаций. Так вот, такого алгоритма еще нет. Есть ряд алгоритмов, позволяющих заметно ускорить сборку по сравнению с традиционными шаблонными методоми, но повторять кем- то уже проложенный (математически) путь мне показалось скучным.
Если кому интересно, вот хороший анализ Далее есть традиционные шаблонные методы. Идея здесь в послойной сборке снизу вверх с использованием формул. Формула — последовательность модификаций Кубика, приводящая к таким- то целевым модификациям, и таким- то побочным. Соответственно, побочные модификации почти всегда падают на еще не собранные слои. Различаются шаблонные методы уровнем детализации шаблонов.
Всякого рода спидкуберы знают все мыслимые шаблоны для большого количества частных случаев, что позволяет отыграть лишнюю 0. Пример, на что еще можно потратить жизнь. Итак, я постепенно формировал для себя задачу. В итоге, формулируется она так: за кратчайшее реальное время необходимо написать решалку для Кубика Рубика.
Что мы знаем о Кубике? Число его состояний описывается как(8! Что мы знаем о его правилах?
То что каждый конкретный элемент (боковой или угловой) должен стоять точно на своём месте. Что является точным местом? Для бокового элемента — это соотстветствие обоих его цветов цветам центральных элементов, для углового элемента — соответствие трёх центральных элементов трём цветам этого углового элемента.
Как возможные гены, программа использует набор формул, . Детективы использовали программу для возрастной коррекции побил мировой рекорд по скорости сборки кубика Рубика Археологи. Как возможные гены, программа использует набор формул. Решение кубика Рубика максимум на 20 шагов сборку, так как необходимо правильно сориентировать остов до начала сборки слоев. Сборщики кубика Рубика: . Собиратель Кубика Рубика - http:// Робот Робот-змея R3PTAR из NXT 2.0 - http:// blogspot.ru/2013/03/nxt-r3ptar.html. Инструкция и программа доступны по ссылке Обратите.
Таким образом мы можем в любой момент времени просто ответить на вопрос — «стоит ли данный элемент на своём месте?». Второй аспект, который мы знаем — Кубик может быть собран послойно, при чём каждый слой собирается постепенно. Нужна градиентная эвристика. Осталось лишь выбрать метод реализации.
Алгебраические методы я не стал рассматривать, т. Но по понятным причинам, кроме тоски этот вариант не навевал ничего. Оставался перебор. Несмотря на полное возможное число состояний, перебор представлялся мне самым простым решением. Оставалось выяснить детали реализации.
Интуиция подсказывала мне, что потребуется некая конкурентная среда возможных вариантов, чтобы из представленных вариантов было быстрее найти переход на следующий уровень сборки. В общем- то вариант генетического алгоритма начал доминировать сам собой. Средой исполнения я решил выбрать обычный современный браузер, т. Я поделился идеей с приятелем, занимавшимся в этот момент выпасом гусей в Белоруссии, или чем- то в этом роде. Дима подхватил предложение, мы начали смотреть способы параллельного объединения усилий.
Довольно быстро нашёлся collabedit. Java. Script код нескольким людям одновременно. Я закинул html на хостинг с инклюдами< script src=«collabedit. И мы приступили. Хранить кубик как описание физического объекта нам показалось бессмысленным и гораздо более сложным процессом, чем хранение и связка отдельных 6- ти плоскостей, состоящих из массивов по 9 элементов. Я сел за написание UI и рендеринг кубика, Дима сел за описание объекта куба и его модификаций.
Для того чтобы выполнить над кубиком абсолютно любой набор действий, требуется уметь выполнять 3 операции. Вращение куба влево. Вращение куба вверх. Вращение фронтальной плоскости по часовой стрелке. Я думаю нет смысла доказывать утверждение, оно вполне интуитивно понятно.
При вращении куба, например, вверх, необходимо циклично поменять местами 4 массива плоскостей, вращать левую и правую стороны против и по- часовой стрелке соответсвенно, а так же отразить по горизонтальной оси заднюю плоскость. На следующее утро я убил практически 2 часа времени на осознание последнего факта, получая после вращений виртуального и реального кубиков расхождение в симметрии. Кубик научился поддерживать через метод . Right, Left, Upper, Down, Front), а так же их против- часовые модификации с апострофом. Далее я написал функцию run.
Sequence позволяющую выполнять формулу целиком над заданным кубиком. Часть подготовки интерпретатора была почти завершена. Последним штрихом я сделал функцию shuffle с выводом новой случайной формулы тасования кубика, и на всякий случай сверил результат интерпретатора и реального кубика. Теперь всё, рутинная часть позади. Общество Кубов, в котором нет цветовой дифференциации, лишено цели.
Каждый член Популяции Кубов, каждый маленький Кубик, должен представлять на сколько он близок, как личность, к Высшему Кубу. В противном случае данная социальная группа очевидно повязнет в хаосе и модификационных излишествах.
Первым делом, я сел за описание фитнесс- функции. Было очевидно, что просто считать количество одинаковых цветов на каждой из плоскостей, возводить их, скажем, в квадрат и складывать — хочется, но нельзя. В противном случае из ближайшего локального максимума популяция Кубов никогда не выберется.
Луч надежды должен быть более узконаправленным. Я описал функцию в соотстветсвии с классическими методами сборки — послойно. При чем каждый следующий слой, и каждый следующий элемент текущего слоя давал ощутимый прирост фитнесса, что позволяло более приспособленным только что появившимся Кубособям быстро доминировать в популяции. Если все 4 элемента стоят на своих местах, мы можем переходить к следующему уровню. Это обеспечивает плавную сегрегацию всей популяции. Далее, предстоял сам генетический алгоритм. Очевидно, геном является некая шаблонная модификация Куба.
Геномом — весь набор модификаций, который привел к текущему состоянию. Что же является результатом скрещиванием Кубов? Ничего, они все однополые и размножаются почкованием. В каждом раунде эволюции происходит мутация всех геномов путем добавления генов к уже существующему геному. Еще одним параметром мутации является значение gene. Max. Append. Count — максимальное возможное число генов, которые будут добавлены во время следующей мутации.
Это важное число, которое регулирует, на сколько сложную модификацию Куб сможет сгенерировать за один раз. После мутации Куба считается его фитнесс, а затем и всех остальных кубов. Затем считается средняя температура по больнице, и на основании неё — насколько широко генотип конкретного Куба распространится теперь в популяции. Count = Math. floor((1) * (cur. Fitness / average. Temperature - 1) ).
Count *= poluttion. Count. poluttion. Count- -. Далее этот более сильный Куб вымещает собой несколько более слабых Кубов популяции, и начинается следующий виток эволюции.
Ура! Оно работает. Основная проблема с которой я столкнулся, заключалась в самом последнем этапе сборки: полностью собраны 2 уровня, на 3- м уровне верно стоят боковины, и даже на своих местах расположены углы — осталось лишь повернуть по- или против часовой стрелки несколько уголков и вот он полностью готовый Куб.
И несмотря на то, что с самым последним действием интуитивно справится даже двухлетний ребёнок, мне не хотелось закладыавть в фитнесс- функцию каких- то частных случаев. Задача эволюционного алгоритма любыми способами перескочить яму, которая необходима для промежуточной сборки финальной части. Для этого я сделал две вещи: 1. В набор формул я добавил формулы поворота угла в повторении 2х и 4х, для того чтобы угол поворачивался против или по часовой стрелке за 1 ген соответственно. Это увеличивает вероятность выполнить большую часть операцию за одну мутацию.
Ввел значение gene. Max. Append. Count и включил его в фитнесс- функцию: points += cube.
Max. Append. Count * 3. Дело в том, что обычно Кубы стартую с максимального значения в 4 или 5. В самом начале, когда улучшение Куба сделать легко, оно происходит за 1 или 2 гена, в популяции начинают доминировать Кубы с короткими генетическими переходами. На самом последнем этапе подобная стратегия уже не проходит, и мы должны поощрять особей, которые пытаются найти более сложные решения, но так, чтобы рост gene.
Max. Append. Count не стал самоцелью популяции. Два этих ухищрения позволили гарантированно решать любой Кубик Рубика в среднем за 3. Куба). Иногда процесс затягивается на последнем этапе, до тех пор, пока случайная мутация не переживет яму, временно разрушающую Куб. Вручную, по самому примитивному алгоритму я собираю Кубик в среднем за 1. Но я считаю для переборного алгоритма это вполне разумное число, к тому же перед популяцией вполне можно поставить задачу сокращения длины генотипа, что резко снизит требуемое число операций.
Далее, о более низкоуровневом решении. Как возможные гены, программа использует набор формул, которые я скопировал из случайной статьи в интернете. Из- за усложнения на порядок пути до полезой модификации, Кубы очень трудно переживали периоды временного разрушения. Нужно было каким- то образом обеспечить протекцию некоторых смелых Кубов, ушедших в поисках лучшей формы. Я решил ввести политику Льготного Кредитования Популяции.
В случае, когда за последние 1. Кубы безпроцентно кредитовались на 3. Но они не могли использовать свой кредит, чтобы только за счет него возвыситься над всей популяцией и расплодиться. Они получали временную протекцию от более приспособленных в данный момент Кубов, для того чтобы иметь больше шансов выйти на следующую выйгрышную конфигурацию.