Системный анализ групп преобразований состояний кубика Рубика

курсовая работа

3.4.2 Алгоритм Коцембы

Алгоритм Тистлетуэйта был в 1992 году улучшен учителем математики из Дармштадта Гербертом Коцембой.

Коцемба сократил количество этапов алгоритма до двух

· G0 = (U, D, L, R, F, B)

· G1 = (U, D, L2, R2, F2, B2)

· G2 = {1}

Наглядное описание группы G1 можно получить, если произвести следующую разметку (рисунок 3.1):

· Все этикетки U и D пометить знаком «+».

· Все этикетки на рёберных элементах FR, FL, BL и BR пометить знаком «-»

· Все остальные этикетки оставить без меток.

Тогда все конфигурации группы будут иметь одну и ту же разметку (совпадающую с разметкой на собранном кубике).

Рисунок 3.1 - Промежуточное состояние кубика Рубика в алгоритме Коцембы. Группа G1

Алгоритм Коцембы еще в меньшей степени, чем алгоритм Тистлетуэйта, можно назвать "алгоритмом сборки" в привычном смысле этого слова. Реализовать этот алгоритм способен только достаточно быстрый компьютер с большой оперативной памятью. Однако сама идея довольно проста.

Вся сборка кубика разбивается на 2 этапа. На первом этапе допускаются любые повороты граней. Единственной целью первого этапа является приведение кубика в некоторое "промежуточное" состояние. Как только кубик после некоторого числа поворотов оказался в промежуточном состоянии, начинается второй этап. В этом этапе используются уже не все возможные повороты граней, а только такие, которые не выводят кубик из класса промежуточных состояний. Нулевое состояние (полностью собранный кубик) также принадлежит этому классу, поэтому рано или поздно оно будет найдено обыкновенным перебором вариантов.

Если суммарное число ходов, затраченных на первый и второй этап, больше 21, то программа возвращается к первому этапу и берет следующее промежуточное состояние. Экономия перебора, получаемая благодаря этой идее, колоссальна: на первом этапе рассматривается примерно вариантов, а на втором - вариантов. Итого программа должна просмотреть около вариантов, а это число на 9 порядков меньше, чем общее количество состояний куба.

У алгоритмов Коцембы и Тистлетуэйта есть много общего. Например, оба они используют такое понятие, как класс промежуточных состояний. При этом "промежуточные состояния Коцембы" практически совпадают со "вторым классом промежуточных состояний" Тистлетуэйта. Разница только в системе обозначений - на втором этапе Коцемба разрешает произвольные вращения U и D, и повороты на 180 остальных граней, а Тистлетуэйт на своем третьем этапе оставлял для произвольных вращений грани F и B. Иначе говоря, первый этап способа Коцембы соответствует двум первым этапам алгоритма Тистлетуэйта, а второй этап - двум последним. Различия между этими алгоритмами не столь заметны, но более принципиальны. А именно, Тистлетуэйт получил конкретные наборы операций и привел строгие математические доказательства, обосновывающие указанные им длины каждого этапа. А Герберт Коцемба, не утруждая себя никакими обоснованиями, просто бросил вызов всем любителям: можете присылать мне все те задачки, которые у вас не получаются, и моя программа справится с ними за 20 ходов!

Реально программа Коцембы немного сложнее, чем это описано выше. Она не делает полного перебора вариантов ни на одном из своих этапов. Вместо этого она тратит некоторое время на создание специальных фильтров: огромных массивов, содержащих списки состояний, из которых можно достичь конечного (для этого этапа) состояния за определенное число ходов (от 1 до 8). Начав сборку кубика, программа пытается выполнить первый этап за 10 ходов. Она делает первые два хода и смотрит массив-фильтр на 8 ходов. Если состояние не отсеется, то делается третий ход и просматривается фильтр на 7 ходов и т.д. В противном случае делается другой второй ход. Точно по такой же схеме выполняется и второй этап сборки - на него программа Коцембы отводит не более 14 ходов.

Сообщение Коцембы неоднократно перепроверялось и уточнялось другими специалистами. В результате оказалось, что для обоих этапов оценки, количества ходов, приведенные Коцембой, чересчур оптимистичны: существуют начальные позиции, из которых нельзя закончить первый этап быстрее чем за 12 ходов, кроме того, существуют состояния из "промежуточного" класса, от которых нельзя перейти к собранному кубику быстрее чем за 18 ходов. Приведенные числа 12 и 18 - это точные границы: последователям Коцембы удалось произвести полный перебор для 1-го и 2-го этапов. Таким образом, доказано, что алгоритм Бога имеет длину не более 30 ходов. [6]

Делись добром ;)