[Из песочницы] Общая схема построения алгоритмов на примере кубика Рубика
Возможно, многие из читателей пытались собрать кубик Рубика 3×3 самостоятельно, но после множества неудачных попыток либо бросали это занятие, либо искали готовое решение. Целью этой статьи является показать на примере кубика Рубика что найти решение любой (из класса решаемых) задачи самостоятельно, есть вполне выполнимая задача для каждого, если при этом руководствоваться определенным набором правил. Данное решение получено мною за 10 часов, плюс этого алгоритма что он не требует запоминать сложные комбинации и длительное время тренироваться — достаточно собрать данным способом всего несколько раз.
Итак, рассмотрим одно из возможных решений. Снизу под каждым пунктом дана грубая оценка вычислительной сложности (Сn) данной подзадачи (исходя из времени поиска решения, которое прямо пропорционально общему количеству комбинаций возможных ходов):
1. Изучаем конструкцию (начальные условия задачи) — понимаем что вершины кубика Рубика, боковые и центральные грани не «перемешиваются», а значит задачу можно разбить как минимум на три подзадачи сборки:
- вершин
- центральных граней
- боковых граней
Еще что необходимо уяснить из конструкции: положение всех цветов по сторонам, собранного куба, относительно друг друга строго фиксировано (убедитесь в этом самостоятельно).
Само собой, постановка задачи и разбиение ее на части это тоже задача, поэтому данному пункту тоже соответствует некая «интеллектуальная сложность», но единого критерия оценки для неё не существует, так что пропускаем.
2. Собираем первую сторону (красную-нижнюю).
С2 ~ 2
3. Выбираем собранную сторону в качестве точки отсчета для поиска алгоритмов сборки оставшихся вершин (принадлежащие стороне рыжего цвета). Ищем относительно этой точки всевозможные инвариантные операторы (Tx), способные всевозможным образом «тасовать» оставшиеся несобранными грани.
В итоге из всего множества, в зависимости от их «действия», мною было выделено 4 основных оператора:
- Tv — «вертикальный»
С3.1 ~ 3 - Tg — «горизонтальный»
С3.2 ~ 3 - Tf — «флип»
С3.3 ~ 2 - Ttw90 — «поворот на 90»
С3.4 ~ 0
Примечание: все перечисленные выше операторы, не требуют «зазубривания», достаточно понять как они работают — проследите за траекторией красных граней.
4. Напрашивается вопрос- Зачем нужны все эти операторы, если сами по себе они не дают однозначного правила для расстановки по местам вершин? Дело в том что механическая система кубика Рубика имеет сложные внутренние связи, и решение требует длительного последовательного перебора что значительно проще выполнить (аналитически) как раз на основе определенных в п. 3 операторов:
- Перестановка двух смежных угловых граней
Tv-Ttw90-Tf-Tg
С4.1 ~ 4 - Поворот двух смежных угловых граней
Tv-Tg-Tg-Ttw90-Tg
С4.2 ~ 5
Данных двух вышеопределенных «манипуляций», достаточно чтобы расставить по местам все угловые грани.
5. Расстанавливаем по местам центральные грани (самостоятельно).
С5 ~ 2
6. Заключительный этап — расстановка боковых граней. Здесь достаточно всего одного оператора:
- Ts — «боковой»
С6.1 ~ 3
Предлагаю читателю самостоятельно разобраться каким образом на основе данного оператора можно «дорешать» головоломку — сложность С6 ~ 2.
В заключение подcчитаем общую «сложность» в понятиях О-оценки, для данного решения алгоритма- это максимальная сложность подзадачи из всех используемых подзадач для законченного решения общей задачи: О (С1)+O (C2) +… = MAX { C1, C2, … }.
Итого, «cложность» общего решения «задачи» кубика Рубика данным способом составила ~ 5.
Остается еще пояснить что есть «сложность подзадачи»- это величина прямо-пропорциональная количеству всех переборов возможных решений с учетом всех условий (симметрии, …), например, в случае поворота любой грани на 180 град, не имеет смысл, при поиске решения, поворачивать ее тут же еще на 180 град.
Таким образом, для построение алгоритма необходимо:
- Разбить задачу, исходя из ее особенностей, на как можно большее количество независимых подзадач.
- Определить точку отсчета для каждой подзадачи, относительно которой ищется решение (в примере кубика Рубика это была красная грань)
- Аналогично для каждой подзадачи построить полный набор операторов («перетасовки»), с помощью которых будет осуществляться условный перебор всевозможных решений.
- Определить условия перебора (для исключения «симметричных дубликатов»).
Все остальное сделает за вас ЭВМ — чем сложнее, тем дольше будет осуществляться поиск.
