Методы сборки (LBL, CFOP, двухфазный, редукция)

Методы сборки кубика Рубика делятся на два семейства: те, что запоминают люди, и те, что перебирают компьютеры. Они оптимизируют разное. Человеческие методы удерживают объём запоминаемого в разумных пределах и ценят ходы, естественно текущие под пальцами. Компьютерные методы полностью пренебрегают запоминаемостью, гонясь за короткими решениями, найденными быстро. Ниже — четыре характерных подхода, упорядоченных по тому, чего каждый добивается.

LBL — строить слой за слоем

LBL (Layer By Layer, послойный) — самый прямолинейный метод: сначала завершаем нижний слой, затем средний, затем верхний. Порядок таков: крест, углы первого слоя, рёбра второго, ориентация последнего, перестановка последнего. Достаточно примерно десяти алгоритмов, но решения часто переваливают за 100 ходов. Поскольку каждый этап обязан оставить готовые слои нетронутыми, метод постоянно идёт в обход — разрушает слой и восстанавливает его. Именно эта мысль «разрушь и положи обратно» является самым базовым инструментом в сборке кубика.

CFOP — запомнить больше, чтобы крутить меньше

CFOP (Cross, F2L, OLL, PLL) — господствующий метод скоростной сборки. От LBL он отличается двумя вещами. Во-первых, он перестаёт рассматривать углы первого слоя и рёбра второго по отдельности, вставляя их парами (F2L). Во-вторых, он упорядочивает последний слой в два чистых этапа: сначала всё сориентировать (OLL), затем всё переставить (PLL). Решения падают примерно до 50–60 ходов ценой изучения 57 случаев OLL и 21 случая PLL. Запоминание и число ходов обмениваются друг на друга — этот принцип пронизывает каждый человеческий метод.

Двухфазный — разрезать пространство поиска надвое

Компьютеры чаще всего применяют двухфазный метод (семейство Коцембы). У 3x3x3 около 43 квинтиллионов позиций, поэтому искать кратчайшее решение в лоб трудно. Приём — подгруппа. Позиции, достижимые только с помощью G1 = ⟨U, D, R2, L2, F2, B2⟩, образуют мир, гораздо меньший, чем весь кубик. Метод сначала ищет ходы, опускающие текущую позицию в этот меньший мир, а затем ищет внутри него до завершения. Разбиение одного большого поиска на два маленьких даёт достаточно короткое решение за реалистичное время. Плата за разбиение в том, что результат близок к оптимальному, но не обязательно является истинным минимумом.

Редукция — заставить большой кубик вести себя как 3x3x3

У 4x4x4 и 5x5x5 есть детали, которых нет у 3x3x3: несколько центров на грань и рёбра, составленные из двух или трёх отдельных частей. Редукция обращает это себе на пользу. Сначала собираем одноцветные центры на каждой грани, затем спариваем разрозненные рёберные части. Как только это сделано, большой кубик читается так, будто каждая грань — единый блок, структурно тождественный 3x3x3, и любой метод для 3x3x3 доводит дело до конца. По пути возникает то, чего 3x3x3 никогда не порождает: чётность, выглядящая как единственная переставленная пара. Ничего не сломано — это свойство, присущее кубикам чётного размера.

Как решает cubepic

cubepic подбирает метод под размер. 3x3x3 использует двухфазный метод. 2x2x2 едет на том же двухфазном поиске, в который встроены только углы. 4x4x4 и 5x5x5 пользуются редукцией, а после сведения передают дело двухфазному решателю. Для любого размера возвращаемое решение почти оптимально, без гарантии оптимальности. Несколько известных заготовленных позиций (например, суперфлип) показывают решение, доказанно кратчайшее в метрике HTM (пол-оборота). Дальнейший поиск для сокращения решения запланирован как платный уровень. Целью тоже не обязательно должно быть собранное состояние: можно зарегистрировать любую допустимую позицию. Тогда cubepic решает «текущее до собранного» и «целевое до собранного», а второе решение добавляет развёрнутым и обращённым.

© アサラボ