О головоломках и перестановках

Давно не писал тут #научпоп, но начавшиеся трудовые будни и необходимость объяснять и мотивировать к примеру понятия теории групп и графов Кэли, а также беседа со знакомым чемпионом мира по футболу (среди роботов) навела на один сюжет.

Вот есть у нас кубик Рубика (дальше КР), обычный: 3 на 3. Элементарные действия для сборки это вращения граней: их по 3 в каждой плоскости, плоскостей 3 штуки: итого 9 штук. Всевозможные комбинации этих элементарных вращений --- образуют множество. Каждый его элемент это некое допустимое вращение КР, в т.ч. и тривиальное (т. е. когда ничего не вращаем).

Элементы этого множества можно умножать: беру первое допустимое вращение, затем делаю второе допустимое вращение: получаю третье. Легко проверить (взяв в руки КР), что операция не коммутативна: важно какое вращение делаем первым, а какое вторым. Также легко понять, что каждое вращение обратимо: если проделать элементарные вращения в обратном порядке — вернёмся в то состояние с которого начали. Чуть сложнее проверить, что эти вращения ассоциативны: a(bc) = (ab)c. В это просто поверим.

Из сказанного следует, что множество допустимых вращений КР это группа с 9 образующими (образующие = элементарные вращения).

Теперь рассмотрим множество всех допустимых состояний КР (это не тоже самое, что вращения!). Превратим это множество в направленный цветной граф. Из состояния A в состояние B нарисуем стрелка цвета s (где s — элементарное вращение), если s переводит A в B. Сразу понятно, что граф связен: из любого допустимого состояния можно попасть в любое.

Каждое допустимое вращение w кодирует преобразование графа: переведя состояние A в w(A). Например, тривиальное вращение оставит все вершины на месте. Легко понять, что при этом вершины которые были соседними раньше, таковыми и останутся.

Заметим два свойства. Транзитивность: допустимое состояние можно перевести в любое другое. Свобода: разные вращения действуют на граф по-разному. Из этого следует (теорема Сабидусси), что граф состояний = графу Кэли группы допустимых вращений. Но и без этого можно понять, что граф вершинно-транзитивен: любую вершину можно перевести в другую единственным образом.

Два дармовых следствия:
* Нет волшебного алгоритма, состоящего из фиксированного набора действий, механическое повторение которых соберёт кубик из произвольного состояния. Однако, при достаточном количестве повторений — мы вернёмся в то состояние, из которого начали.
* Нет плохих или хороших состояний: если мы умеем собирать граф в одно состояние не более чем за N элементарных действий, то и в любое другое состояние тоже.

Это число N называют «числом Бога» (God number). Для КР это 20, как в 2010 году выяснила корпорация Google. А ещё в этом графе есть гамильтонов цикл (проявление гипотезы Ловаса). Значит можно «пробежать» по всем допустимым состояниям, побывав в каждом из них ровно один раз.

Вся эта логика работает не только для головоломок. Вот, скажем, задача сортировки. К примеру, пузырьком. На множестве состояний (допустимых сортировок) строим граф при помощи транспозиций (меняем местами k и k+1). Тогда диаметр графа состояний это просто минимальное достаточное число действий нужных для сортировки, а сам алгоритм сортировки — нахождение пути в графе. Ну, а граф — граф Кэли для группы перестановок Sn.

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

Ещё одна мысль такая. Минимальное достаточное число действий (число Бога) это идеальная реализация способа сортировки. А конкретный алгоритм -- построение пути в графе. И таких алгоритмов для одной системы образующих может быть много. Самый плохой из них движение по Гамильтоновому циклу «в неправильную сторону» (если он есть, т. е. если гипотеза Ловаса верна). Самый лучший (который хрен найдёшь) — движение по «алгоритму Бога». Так, для КР реальные алгоритмы — за сотню элементарных вращений.

Вот такой сюжет. Если будет интерес — разовью тему.