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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

Национальный аэрокосмический университет им. Н.Е. Жуковского

«Харьковский авиационный институт»

КУРСОВАЯ РАБОТА

по дисциплине: «Основы системного анализа»

на тему: СИСТЕМНЫЙ АНАЛИЗ ГРУПП ПРЕОБРАЗОВАНИЙ СОСТОЯНИЙ КУБИКА РУБИКА

г. Харьков - 2014 год

Оглавление

Введение

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

.1 Актуальность работы

.2 Дерево проблем

.3 Дерево целей

. Описание системы трехмерного визуализатора процесса дефрагментации (кубика рубика) с точки зрения системного анализа

.1 Структурное описание системы

.2 Функциональное описание системы

.3 Информационное описание системы

.4 Классификационное описание системы

. Модельное представление объекта исследования

.1 Основные уравнения, описывающие объект исследования

.2 Входные и выходные величины

.3 Исследование преобразований состояний кубика Рубика с помощью математической теории групп

.4 Анализ некоторых алгоритмов решения головоломки

.4.1 Алгоритм Тистлетуэйта

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

.4.3 Метод CFOP (метод Джессики Фридрих)

.4.4 Основные факторы, влияющие на оптимизацию групп преобразований состояний кубика Рубика

Заключение

Список литературы

Приложение

Введение

Кубик Рубика - одна из популярнейших в мире головоломок. Её создал в 1975 году Эрнё Рубик (Erne Rubik, Rubik Ernő) - венгерский изобретатель, скульптор и профессор архитектуры.

В 1971 году Эрнё был назначен преподавателем Академии прикладных искусств. Среди прочих дисциплин он преподавал трехмерное моделирование. По одной из версий, при помощи данного учебного пособия Рубик пытался объяснить студентам основы математической теории групп. Задача изобретателя была такова: заставить отдельные разноцветные кубики свободно вращаться на своих местах, не нарушая конструктивного единства всего приспособления.

Самому изобретателю потребовался месяц, чтобы собрать кубик, после создания первой модели.

января 1975 г. Эрнё Рубик подал заявку на патент.

В течение последующих 40 лет ведущие математики и программисты пытались найти кратчайший алгоритм сборка кубика Рубика. На данный момент кратчайший алгоритм не найден.

В первой главе данной работы приведен обзор литературы, сделаны выводы по результатам обзора информационных источников. Также представлены дерево проблем и дерево целей, определена цель исследования. Определен объект исследования, приведено доказательство того, что объект исследования является объектом с точки зрения системного анализа. Определен предмет исследования.

Во второй главе содержится анализ предмета исследования. Приведены структурный, функциональный, информационный и классификационный виды анализа исследуемого объекта.

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

В заключении представлены выводы, предложения и рекомендации, показана практическая значимость работы.

дефрагментация кубик рубик математический

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

.1 Актуальность работы

Кубик Рубика - это пластмассовый куб, разбитый на 27 конгруэнтных кубиков. Внутренний кубик удален, а 26 наружных кубиков соединены так, что любая грань из 9 кубиков, прилегающих к одной грани куба, может быть повернута в любом направлении на 900. После поворота на 900 вся система сохраняет прежнюю свободу вращений: снова любую грань в любом направлении можно повернуть в ее плоскости на 900.

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

«Джон Конвей, один из крупнейших специалистов по теории групп в мире, либо один из его коллег в Кембридже определил кратчайший путь из любого данного состояния назад к начальному состоянию как «Алгоритм Бога» [1].

Число комбинаций кубиков, которые можно получить вращением граней (подсчитано, что их N = 43 252 003 274 489 856 000, т.е. более 43 квинтиллионов) делает ее недоступной для перебора даже на ЭВМ. Можно заметить, что не любая комбинация может быть получена вращением граней куба: если разрешить разборку куба на составляющие его 26 кубиков, то можно составить 12N = 529024039393878272000 различных комбинаций.

1.2 Дерево проблем

Основную проблему данной работы, можно разбить на подпроблемы и представить в виде дерева проблем (см. рис. 1.1)

.Сложность последовательной обработки всех возможных различных состояний кубика Рубика

.1.Сложность построения графа состояний кубика Рубика

.1.1.Ограниченные возможности графических редакторов и средств для визуализации графа состояний кубика Рубика

.2.Ограниченность ресурсов вычислительной техники

.2.1.Ограниченностьвместимости цифровых носителей

Рисунок 1.1 - Дерево проблем

.3 Дерево целей

Основную цель данной работы, можно разбить на подцели и представить в виде дерева целей (см. рис. 1.2).

.Исследовать возможность создания алгоритмов и сформулировать рекомендации, позволяющие оптимизировать количество преобразований между начальным и целевым состояниями кубика Рубика

.1.Оптимизация на группе преобразований состояний кубика Рубика

.1.1.Применение методов теории групп

.2.Поиск алгоритма для нахождения оптимального решения

.2.1.Изучение и анализ алгоритмов преобразования состояний кубика Рубика

Рисунок 1.2 - Дерево целей

Цель работы - исследовать возможность создания алгоритмов и сформулировать рекомендации, позволяющие оптимизировать количество преобразований между начальным и целевым состояниями кубика Рубика.

Объект исследования - Состояния кубика Рубика.

Предмет исследования - Группы преобразований состояний кубика Рубика

Методы исследования:

·Обработка существующей информации;

·Анализ существующих алгоритмов.

Основные задачи исследования:

·Изучение алгоритмов преобразования состояний кубика Рубика;

·Определение основных факторов, влияющих на оптимизацию групп преобразований кубика Рубика.

2. Описание системы трехмерного визуализатора процесса дефрагментации (кубика рубика) с точки зрения системного анализа

.1 Структурное описание системы

Рассмотрим структуру системы кубика Рубика (Рисунок 2.1) и её свойства с позиций системного анализа.

Рисунок 2.1 - Структура кубика Рубика

Свойства системы:

)Эмерджентность

Центральный механизм - предназначен для соединения 26 конгруэнтных кубиков управления вращениями граней

Кубики - определяют положение цветовых индикаторов на каждой грани

Каждая из систем выполняет свою функцию, но их объединение способствует визуализации пошагового процесса дефрагментации без нарушения целостности всего устройства.

)Целостность

При удалении из системы всех центральных кубиков реберные и угловые кубики перестают управляться центральным механизмом, и система перестает существовать

)Аддитивность

Переход системы в нулевое состояние осуществляется последовательными поворотами граней куба.

)Синергизм

Вращение одной грани вызывает одновременное изменение положения и ориентации в пространстве девяти кубиков, принадлежащих вращающейся грани.

)Прогрессирующая систематизация

Процесс сборки кубика Рубика - это стремление к целостному цветовому покрытию каждой грани

)Изоморфизм

Все центральные, реберные и угловые кубики сходны между собой по строению (внутри группы).

Тип элементного состава - смешанный тип. Однотипными элементами являются кубики и в то же время они отличаются от центрального механизма.

Тип элементов - вещественный.

Тип связей между элементами - информационный.

Тип структуры - иерархическая.

Условно кубик Рубика можно представить кибернетической моделью, где {x1, …, xn} - вектор входов объекта, а {y} - выход.

.2 Функциональное описание системы

Функциональное описание системы - это описание как основной функции, выполняемой системой, так и функций подсистем и элементов данной системы с указанием параметров системы, подсистем и элементов. Функциональное описание также содержит структурноеописание системы, описание системоразрушающих и системообразующих факторов.

Структурное описание системы:

.Кубик Рубика

.1.Центральный механизм

.1.1.Толстое плечо креста

.1.2.Тонкая ось креста

.1.2.1.Шайба

.1.2.2.Пружина

.1.2.3.Гайка

.2.Кубики

.2.1.Центральные

.2.1.1.Цветные накладки

.2.2.Реберные

.2.2.1.Цветные накладки

.2.3.Угловые

.2.3.1.Цветные накладки

Функции системы и ее подсистем представлены в таблице 2.1

Таблица 2.1 - Функциональное описание системы

КодЭлементФункцияФункции системы первого уровня1Кубик РубикаПреобразование групп состояний цветовой схемы кубика РубикаФункции подсистем второго уровня1.1Центральный механизмКрепление центральных кубиков Вращение граней кубика Рубика1.2КубикиВизуализация вращений гранейФункции подсистем третьего уровня1.1.1Толстое плечо крестаОбеспечение фиксации центральных кубиков1.1.2Тонкая ось крестаОбеспечение подвижного крепления центральных кубиков при помощи пружины, шайбы и гайки1.2.1Центральные кубикиОпределение цвета соответствующей грани Фиксация угловых и реберных кубиков1.2.2Реберные кубикиОпределение состояния кубика Рубика Ориентация цветовых накладок относительно «собранного» состояния1.2.3Угловые кубикиОпределение состояния кубика Рубика Ориентация цветовых накладок относительно «собранного» состоянияФункции подсистем четвертого уровняКодЭлементФункция1.1.3ШайбаОбеспечение защиты пластмассовой части центрального кубика от продавливания металлической пружиной1.1.4ПружинаОбеспечение упругого соединения вращаемой грани1.1.5ГайкаОбеспечение фиксации пружины1.2.1.1 1.2.2.1 1.2.3.1Цветные накладкиВизуализация состояний кубика Рубика

Параметры системы и ее подсистем представлены в таблице 2.2

Таблица 2.2 - Параметры подсистем и элементов

КодЭлементПараметрыПараметры системы первого уровня1Кубик РубикаКачество Количество слоевПараметры подсистем второго уровня1.1Центральный механизм1.2КубикиКачество материала Безопасность материала Пластичность материала Длина стороныПараметры подсистем третьего уровня1.1.1Толстое плечо крестаДлина Диаметр Симметричность относительно центра1.1.2Тонкая ось крестаДиаметр Длина1.2.1Центральные кубикиТолщина внешней части Внешний диаметр выступа Внутренний диаметр выступа1.2.2Реберные кубикиДлина до внутреннего выступа Длина внутреннего выступа Ширина внутреннего выступа Радиус скругления1.2.3Угловые кубикиДлина до внутреннего выступа Длина внутреннего выступа1.2.3Угловые кубикиШирина внутреннего выступа Радиус скругленияПараметры подсистем четвертого уровня1.1.3ШайбаВнутренний диаметр Внешний диаметр Толщина шайбы1.1.4ПружинаДиаметр проволоки Стержень Внутренний диаметр Внешний диаметр Расточка Шаг Длина в сжатом состоянии Допустимая длина Свободная длина Количество витков Коэффициент упругости Длина под нагрузкой1.1.5ГайкаМарка стали Класс точности Класс прочности Поле допуска резьбы1.2.1.1 1.2.2.1 1.2.3.1Цветные накладкиБезопасность материала Толщина основы Толщина клеевого слоя Ширина основы

Итоговое и суммарное количество функций

·Функции первого уровня - 1

·Функции второго уровня - 2

·Функции третьего уровня - 5

·Функции четвертого уровня - 4

Общие характеристики системы представлены в таблице 2.3

Таблица 2.3 - Общие характеристики системы

ФункциональностьРангФакторыСистеморазрушающиеСистемообразующиеМногофункциональнаяПассивное существованиеНарушение правил эксплуатацииСоблюдение правил эксплуатации

.3 Информационное описание системы

Информационное описание должно давать представление об организации и управлении системой. Это наиболее полное описание, так как описывает систему уже в процессе ее функционирования. Информационное описание определяет зависимость морфологических и функциональных свойств системы от качества и количества внутренней (о самом себе и о среде) и внешней (поступающей из внешней среды) информации.

Принцип работы объекта исследования

На рисунках 2.2, 2.4 и 2.5 изображены внутренний крест, реберный кубик и угловой кубик соответственно. На рисунке 2.3 изображено крепление центрального кубика на внутреннем кресте

Рисунок 2.6 изображает внутреннюю сторону грани, снятой с креста.

Рисунок 2.7 изображает кубик Рубика, с которого снята одна грань и один реберный кубик.

Для большей наглядности на рисунках 2.6 и 2.7 центральные кубики, реберные кубики, угловые кубики и внутренний крест окрашены в разные цвета. Эта окраска не имеет отношения к цветным накладкам на внешних гранях кубиков.

На рисунках 2.6 и 2.7 видно как выступы на реберных и угловых кубиках складываются в почти цилиндрический выступ с внутренней стороны грани большого куба, а на среднем слое образуется цилиндрическое кольцеобразное углубление. Поворот грани отвечает повороту цилиндрического выступа в цилиндрическом углублении.

Роль пружины 4 (Рисунок 2.2) - в том, чтобы иметь возможность слегка оттягивать при поворотах вращающуюся грань.[2]

Рисунок 2.2

Перечень элементов системы:

)толстое плечо креста - 1;

)тонкая ось креста - 6;

)пружина - 6;

)гайка - 6;

)центральные кубики - 6;

)реберные кубики - 12;

)угловые кубики - 8;

)цветные накладки -54 (9шт х 6цветов).

Свойства деталей элементов представлены в таблице 2.4

Таблица 2.4 - Свойства деталей элементов системы

№Наименование элементаОбозначениеКоличество свойствПримечание1Толстое плечо крестаа111(1) - является несущим элементом системы2Тонкая ось крестаа221(2) - связывает механизм крепления центральных кубиков с толстым плечом креста 2(2) - является осью вращения граней3Шайба а311(3) - обеспечивает защиту пластмассовой части центрального кубика от продавливания металлической пружиной4Пружинаа421(4) - развивает усилие в растянутом состоянии 2(4) - развивает усилие в сжатом состоянии 3(4) - обеспечивает подвижность грани5Гайкаа511(5) - фиксирует положение пружины6Центральные кубикиа611(6) - обеспечивают крепление реберных и угловых кубиковПродолжение таблицы 2.4№ п/пНаименование элементаОбозначениеКоличество свойствПримечание7Реберные кубикиа711(7) - вращаются вокруг центральных кубиков8Угловые кубикиа811(8) - вращаются вокруг центрального кубика9Цветные накладкиа911(9) - обеспечивают цветовую идентификацию всех видов кубиков

Среднегеометрическое число свойств на один элемент:

а = = = 1,167

Структура объекта представлена на рисунке 2.3

Рисунок 2.3 - Граф системы

Связи системы между элементами системы:

1)Соединительные

. Угловые кубики - центральный кубик

. Реберные кубики - центральный кубик

. Центральный кубик - шайба

. Угловой кубик - цветные накладки

. Реберный кубик - цветные накладки

. Центральный кубик - цветная накладка

. Пружина - гайка

. Гайка - тонкая ось креста

. Тонкая ось креста - толстое плечо креста

)Преобразующие

. Внешняя среда (пользователь) - угловые кубики

. Внешняя среда (пользователь) - реберные кубики

. Шайба - пружина

Количество связей на один элемент системы представлено в таблице 2.5

Таблица 2.5 - Количество связей на один элемент

№Наименование элементаКоличество связей1Толстое плечо креста12Тонкая ось креста23Шайба24Пружина25Гайка26Центральные кубики37Реберные кубики38Угловые кубики39Цветные накладки1

Среднегеометрическое число связей на один элемент:

а = = = 1,963

Определяем число квантов пространства, занимаемых элементами (Таблица 2.6).

Квант пространства элемента vi- объем прямоугольного параллелепипеда, ограничивающего заданный элемент.

Объем пространства существования элементов V - это объем куба с ребром, равным сумме максимальных габаритов размеров элементов.

Число квантов: =

Таблица 2.6 - Число квантов пространства, занимаемых элементами

№Наименование элементаГабаритные размерыКвант пространства элементаМаксимальный размерЧисло квантов1Толстое плечо креста19х19х196859190,004 х1052Тонкая ось креста15х3х3135150,19 х1053Шайба 6х6х0,51861,429х1054Пружина10х5х5250100,103х1055Гайка3х5х57550,343 х1056Центральные кубики19х19х196859190,004 х1057Реберные кубики24х24х2011520240,002 х105 8Угловые кубики24х24х2413824240,002 х1059Цветные накладки15х15х1225150,114 х105

V = =

Среднегеометрическое число квантов пространства:

а==

=

=3,426*

2.4 Классификационное описание системы

Классификация - это разделение совокупности объектов на

классы по наиболее существенным признакам.

Результаты классификации системы представлены в таблице 2.7.

Таблица 2.7 - классификация системы по классификационным признакам

№Признак классификацииТип системы по признакуОпределение1По связи системы с окружающей средойОткрытаяВзаимодействует с окружающей средой2По происхождениюИскусственнаяСистема создана человеком3По объективности существованияРеальнаяСистема состоит из искусственных объектов4По типу описания законов функционированияСистема типа «белый ящик»Для данной системы законы функционирования известны полностью5По способу управления системойСистема с комбинированным управлениемБлок управления в системе - это центральный механизм, но вращает грани человек6По действиюТехническаяДанная система - совокупность взаимосвязанных физических элементов7По централизацииЦентрализованнаяВ данной системе есть центральный механизм управления8По однородности структурыРазнороднаяВ данной системе элементы не взаимозаменяемы9По типу сложностиИнформационно-логическаяДанная система является головоломкой10По мерностиМногомернаяВ данной системе много входов и один выход11По организованностиХорошо организованнаяДля данной системы определены все ее элементы, связи и цели12По линейностиНелинейнаяНе описывается линейным уравнением13По непрерывностиДискретнаяВсе элементы данной системы дискретны14По обусловленности действияДетерминированнаяВходы однозначно определяют выход

3. Модельное представление объекта исследования

.1 Основные уравнения, описывающие объект исследования

Для обозначения последовательности поворотов граней кубика Рубика 3×3×3 используется «нотация Сингмастера» [3], разработанная Дэвидом Сингмастером и опубликованная им в 1981 г.

Буквы L, R, F, B, U, D обозначают поворот на 90° по часовой стрелке левой (left), правой (right), передней (front), задней (back), верхней (up) и нижней (down) граней соответственно. Повороты на 180° обозначаются добавлением справа к букве цифры 2 или добавлением в верхнем индексе цифры 2 справа от буквы. Поворот на 90° против часовой стрелки обозначается добавлением штриха ( ′ ) или добавлением в верхнем индексе -1 справа от буквы. Так, например, записи L2 и L2; L′ и L-1 эквивалентны.

Существует два наиболее распространённых способа измерения длины решения (метрики). Первый способ - одним шагом (ходом) решения считается поворот грани на 90° (quarterturnmetric, QTM). По второму способу - за 1 ход также считается и полуоборот грани (faceturnmetric, FTM, иногда это обозначают HTM - half-turnmetric). Так, F2 (поворот передней грани на 180°) должен считаться за два хода в метрике QTM или за 1 ход в метрике FTM.

Для указания в тексте длины последовательности для используемой метрики используется нотация, состоящая из цифр числа ходов и строчной первой буквы обозначения метрики. Так, 14f обозначает «14 ходов в метрике FTM», а 10q - «10 ходов в метрике QTM». Чтобы указать, что количество ходов является минимальным в данной метрике, используется звёздочка: 10f* обозначает оптимальность решения в 10 ходов FTM.

3.2 Входные и выходные величины

Входными величинами являются всевозможные состояния кубика Рубика. Единственной выходной величиной является нулевое (собранное) состояние.

.3 Исследование преобразований состояний кубика Рубика с помощью математической теории групп

Состояния - различные варианты сборки кубика Рубика, возникающие при произвольной расстановке 8 угловых кубиков по вершинам куба и 12 реберных - по ребрам. Центральные кубики во всех состояниях расположены одинаково - так же, как в нулевом состоянии, когда каждая грань куба окрашена в один цвет. Если состояние S2 можно получить из состояния S1 с помощью некоторой операции, то и от S2 можно перейти к S1, изменив направление каждого из поворотов на противоположное и выполняя их в обратном порядке. В этом случае состояния S1 и S2 являются связанными.

Чтобы полностью описать состояние кубика Рубика, нужно для каждого маленького кубика указать место, которое он занимает, и его ориентацию на этом месте. Каждый угловой кубик можно поместить в одно и то же место тремя, а реберный - двумя способами.

Пусть кубик Рубика находится в нулевом состоянии. Перенумеруем его вершины и находящиеся в них угловые кубики числами от 1 до 8, а ребра и соответствующие реберные кубики - числами от 1 до 12. Кроме того на каждом ребре большого куба выберем определенное направление (вектор).

Теперь местонахождение i-го углового (j-го среднего) кубика в состоянии S можно задать номером σS(i) (τS(j)) той вершины (ребра), где он находится (i = 1..8, j = 1..12).

Чтобы задать ориентацию угловых кубиков, выделим пару противоположных граней большого куба, например его горизонтальные грани. Для определенности предположим, что верхний кубик - синий, а нижний - зеленый. Каждый угловой кубик имеет либо одну грань синего цвета, либо одну грань зеленого цвета. Угол α (α = 00, 1200 или 2400), на который следовало бы повернуть этот кубик в его положении вокруг диагонали большого куба против часовой стрелки, чтобы эта грань (синяя или зеленая) стала горизонтальной, будем называть углом поворота данного углового кубика в состоянии S и об означать αS(i), где i - номер кубика.

Ориентацию j-го реберного кубика в состоянии S зададим углом βS(i) между вектором ребра, на котором кубик должен находиться, и вектором ребра, на котором он находится (τS(j)-го ребра). Угол βS(i) может равняться 00 или 1800; будем называть его углом поворота j-го реберного кубика в состоянии S.

Проследим, как изменяются характеристики состояний αS, βS, τS и σS при поворотах граней. Легко проверить что:

)Углы поворотов угловых кубиков не изменяются при поворотах четырех вертикальных граней на 1800 и при произвольных поворотах горизонтальных граней.

)Углы поворотов реберных кубиков не изменяются при поворотах двух противоположных граней на 1800 и при произвольных поворотах остальных граней.

)При повороте любой вертикальной грани на ±900 к углам поворотов αs двух кубиков, стоящих в ее противоположных вершинах, добавляется по 1200, а к углам поворотов двух ее других угловых кубиков добавляется по 2400.

)При повороте правой или левой грани на ±900 меняются углы поворотов всех четырех реберных кубиков этой грани.

A(S) = αS(1) + αS(2) + … + αS(S) = βS(1) + βS(2) + … + βS

остаются постоянными при всех поворотах граней. Такие характеристики состояний называются инвариантами. Значения любого инварианта для двух связанных состояний S1 и S2 совпадают. Поэтому равенства A(S1) = A(S2) и B(S1) = B(S2) являются необходимыми условиями связанности состояний. Присоединив к ним аналогичное равенство для еще одного инварианта, получаются достаточные условия.

Перестановкой конечного множества называется любое отображение этого множества на себя. Таким образом, функция σs заданная на множестве {1, …, 8}, является перестановкой этого множества, а τS - перестановка множества {1, … , 12}. С любой операцией F также связаны две перестановки τF и σFэтих же множеств: если нулевое состояние S0 переводится операцией F в состояние S, то, по определению, σS(i) = σF(i), τF(j) = τS(j). Другими словами, σF(i) и τF(j) - это номера тех мест, которые занимают в результате операции F угловой кубик, стоявший на i-м месте, и реберный кубик, стоявший на j-м месте.

Выполнив одну за другой перестановки σ1 и σ2 одного и того же множества, мы снова получим его отображение на себя - перестановку σ. Она называется композицией перестановок σ1 и σ2: σ = σ1 ○ σ2.

Пусть σ - произвольная перестановка множества {1, 2, … , n}. Нарисуем одну под другой две строчки по n точек. Если при перестановке σ число i переходит в j, соединим i-ю точку верхней строки отрезком с j-й точкой нижней строки - мы получим граф перестановки σ. Обозначим через N(σ) число точек пересечения отрезков графа (точку, в которой пересекается больше двух отрезков, сосчитаем столько раз, сколько пар отрезков ее содержит). Перестановка σ называется четной (нечетной), если число N(σ) четно (нечетно). Знак перестановки σ определим равенством ε(σ) = (-1) N(σ). ε(σ) равно 1 или -1 в зависимости от того, четна или нечетна перестановка. Выясним, как зависит четность композиции σ1 ○ σ2 от четностей σ1 и σ2. Граф композиции строится очень просто: совмещаем нижнюю строку графа перестановки σ1 с верхней строкой графа σ2 - получается промежуточный граф, а затем заменяем каждую ломаную в промежуточном графе на отрезок, соединяющий ее концы. Число точек пересечения ломаных в промежуточном графе равно N(σ1) + N(σ2). При распрямлении число точек пересечения ломаных может уменьшиться, но его четность сохранится.

Таким образом, N(σ1 ○ σ2) и N(σ1) + N(σ2) - числа одной четности; следовательно, ε(σ1 ○ σ2) = (-1) N(σ1 ○ σ2) = (-1) N(σ1) + N(σ2)= (-1) N(σ1) × 1N(σ2) = ε(σ1) ○ ε(σ2). Другими словами, композиция двух перестановок четна, если их четности совпадают, и нечетна в противном случае.

Допустим, что перестановка σ множества из n элементов оставляет неподвижными n - mэлементов, а остальные m элементов можно упорядочить так, что первый из них переходит во второй, второй - в третий, i-й - в (i+1)-й, а m-й элемент - опять в первый. Тогда перестановка называется циклом длины m или m-циклом.

Назовем знаком состояния S число ε(S) = ε(σS) ○ ε(τS). Оно равно 1 или -1 в зависимости от того, совпадают или нет четности перестановок σSи τS.

Рассмотрим поворот F любой грани на 900. Пусть в результате этого поворота кубик Рубика перешел из состояния S в состояние S. Тогда σS = σS ○ σF, τS = τS ○ τF. Перестановки σFи τF - это 4-циклы, поэтому они нечетны и ε(σF) = ε(τF) = -1. Следовательно, ε(σS) = ε(σS)× ε(σF) = -ε(σS), ε(τS) = ε(τS)× ε(τF) = -ε(τS)и ε(S) = ε(S). Знак состояния не меняется при поворотах граней. Это и есть третий инвариант.

Система инвариантов A(S), B(S) и ε(S) - полная, то есть совпадение их значений для двух состояний обеспечивает связанность этих состояний. [4]

3.4 Анализ некоторых алгоритмов решения головоломки

Первые разработанные алгоритмы требовали 200-300 ходов (поворотов граней) для того, чтобы вернуть кубик в нулевое состояние.

Постепенно длина алгоритмов (т.е. минимальное число ходов, гарантирующее решение) сокращалась. Это происходило за счет изменения последовательности сборки разных частей головоломки (улучшения стратегии) и применения более коротких операций для перестановки и правильной ориентации кубиков (улучшения тактики). Ставший самым популярным «послойный» алгоритм кубика Рубика осуществляет сборку не более чем за 108 ходов. Совершенствуя его, удается уменьшить это число до 86 ходов. Дальнейшие улучшения требуют резкого увеличения количества формул, которые необходимо держать в голове или на бумаге в процессе сборки.

Одновременно с любителями решать головоломку, держа ее в руках, неприступный кубик штурмовали и программисты. Сначала успеха добились те из них, кто взялся за малый кубик размером 2×2×2. Задачу они решали с конца: исходя из нулевого состояния кубика, программа начинает разрушать его, получая и запоминая результаты всевозможных поворотов граней. Если какая-либо расцветка кубика появляется повторно, то соответствующая операция игнорируется, так что в памяти компьютера остаются только самые короткие формулы. В результате был получен список всевозможных состояний малого кубика с указанием после каких поворотов граней они впервые появились. Этот список никогда не был ни опубликован, ни напечатан хотя бы в одном экземпляре. Причина не столько в его громадных размерах, сколько в том, что из-за таких размеров слишком трудно найти в списке нужную в данный момент операцию.

Поворачивая грани 12 раз, компьютер не нашел ни одного нового состояния Малого кубика. Следовательно, чтобы решить головоломку из 8 кубиков, всегда достаточно сделать не более 11 ходов.

Малый кубик есть не что иное, как 8 угловых кубиков классического кубика Рубика. Но в последнем - 26 кубиков, а это усложняет задачу перебора. Кубик Рубика может иметь N 4,3×1019 различных состояний.

Из программистов, занимавшихся разработкой алгоритма для классического кубика Рубика, первым добился успеха английский математик Морвин Тистлетуэйт, который в июле 1981г. разработал алгоритм, позволявший всегда упорядочить кубик Рубика не более чем за 52 хода. Хотя в принципе с помощью этого алгоритма можно собрать кубик Рубика и вручную, реально его может выполнить только компьютер. В дальнейшем этот алгоритм удалось несколько улучшить - сначала этого добился сам англичанин, а позже, в декабре 1990г. Ханс Клостерман из Голландии довел длину алгоритма до 42 ходов. Важно отметить, что эта граница обоснована строго, а не эмпирически, т.е. доказано, что из любого состояния кубика Рубика можно вернуться в нулевое не более чем за 42 хода, причем данный алгоритм не может гарантировать лучшего результата. Это означает, что другой алгоритм не может оказаться короче. Конечно, это доказательство существенно использует компьютер: для каждого из этапов сборки был осуществлен полный перебор вариантов, число ходов, понадобившееся в худшем случае, и принимается за длину данного этапа.

Нового достижения в 1992г. добился немецкий математик Герберт Коцемба. Он был среди тех, кто занимался малым кубиком, но затем примкнул к программистам, исследующим классический кубик Рубика. Он разработал алгоритм и написал программу, которая позволяет собрать головоломку не более чем за 21 ход. Эта оценка длины, в отличие от предыдущей, эмпирическая: все состояния кубика Рубика, которые предлагались программе Коцембы, были упорядочены не более чем за 21 ход.

В июле 2010 года программист из Пало-Альто Томас Рокики, учитель математики из Дармштадта Герберт Коцемба, математик из Кентского университета Морли Дэвидсон и инженер компании Google Inc. Джон Детридж доказали, что каждая конфигурация кубика Рубика может быть решена не более чем в 20 ходов. [5] При этом любой поворот грани считался одним ходом. Таким образом, число Бога в метрике FTM оказалось равно 20 ходам. Объём вычислений составил около 35 лет процессорного времени, пожертвованного компанией Google. Технические данные о производительности и количестве компьютеров не разглашаются; продолжительность вычислений составляла несколько недель.

В августе 2014 г. Томас Рокики и Морли Дэвидсон объявили, что в метрике QTM число Бога равно 26q.

3.4.1 Алгоритм Тистлетуэйта

Тистлетуэйт использовал ряд подгрупп длины 4

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

Эта группа совпадает с группой кубика Рубика. Её порядок равен

·G1 = (L2, R2, F, B, U, D)

Эта подгруппа включает в себя все состояния, которые могут быть решены без использования поворотов левой или правой граней на ±90°. Её порядок равен

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

Эта подгруппа включает в себя все состояния, которые могут быть решены при условии, что повороты четырёх вертикальных граней на ±90° запрещены. Её порядок равен

·G3 = (L2, R2, F2, B2, U2, D2)

Эта подгруппа включает в себя все состояния, которые могут быть решены с использованием только поворотов на 180°. Её порядок равен

·G4 = {1}

Эта подгруппа включает в себя единственное нулевое состояние.

На первом этапе произвольно заданное состояние из группы G приводится к состоянию, лежащему в подгруппе G1. Цель второго этапа состоит в том, чтобы привести кубик к состоянию, находящемуся в подгруппе G2, не используя поворотов левой и правой граней на ±90°. На третьем этапе кубик Рубика приводится к конфигурации, принадлежащей группе G3, при этом повороты вертикальных граней на ±90° запрещены. На заключительном, четвёртом этапе, кубик Рубика полностью собирается поворотами граней на 180°.

Упомянутые группы промежуточных состояний определяются путем вычисления определенных характеристик этих состояний. Эти характеристики, сохраняющиеся при любых разрешенных действиях, математики называют инвариантами. Каждая подгруппа соответствует своему набору инвариантов и их значений.

Тистлетуэйт, проделав весьма кропотливую работу по перебору алгоритмов, показал, что для первого этапа всегда достаточно 7 ходов, для второго - 13, для третьего - 15, а для четвертого - 17. Итого весь алгоритм требует не более чем 52 хода. Этот результат был намного лучше, чем могли в то время дать все остальные алгоритмы сборки кубика. У него был один-единственный "недостаток": он никак не помогал собрать кубик вручную.

.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]

3.4.3 Метод CFOP (метод Джессики Фридрих)- это название четырёх стадий сборки(рисунок 3.2): Cross, F2L, OLL, PLL:

)Cross - сборка креста, четырёх рёберных кубиков на нижней грани;

)F2L (First two layers) - первые два слоя - нижний и средний;

)OLL (Orient the last layer) - ориентацияпоследнегослоя;

)PLL (Permute the last layer) - перестановка последнего слоя.

Рисунок 3.2 - Четыре стадии метода CFOP

.Cross

Единственный этап для которого нет четкой методики.

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

.F2L

Нужно расставить на места восемь кубиков: четыре угловых нижнего слоя и четыре рёберных боковых в среднем слое. Начинающих пара из углового и рёберного кубика собирается сразу же (то есть надо собрать четыре таких пары). В зависимости от первоначальной расстановки кубиков пары нужно применить тот или иной алгоритм (последовательность поворотов). Всего таких алгоритмов больше 40.

Основная сложность этапа в том, чтобы быстро находить парные кубики. Они могут находиться в 16 различных местах: 8 мест в последнем слое и 8 в столбиках. Столбики просматривать сложнее, а чем меньше столбиков собрано, тем больше шансов, что в несобранных находятся нужные кубики. Если вы при сборке креста не обращали внимания на кубики для F2L, при переходе к этому этапу вы можете потерять много времени просто на поиск.

.OLL

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

Существует 57 различных исходных ситуаций, для каждой из которых есть свой алгоритм сборки, от 6 до 14 ходов.

.PLL

Заключительный этап сборки состоит в том, чтобы расставить кубики последнего слоя на нужные места. Подход примерно аналогичный предыдущему этапу, но комбинаций и алгоритмов здесь меньше, всего 21 (13, если считать зеркальные и обратные за одну). С другой стороны их несколько сложнее опознавать, так как здесь надо учитывать разные цвета, причём цвета на схеме могут не совпадать с фактическими цветами (с точностью до циклической перестановки):

Деление пространства позиций

Количество состояний кубика Рубика было разбито на 2 217 093 120 групп, в каждую входило по 19,508,428,800 различных состояний. Одна такая подзадача легко помещается в память современного компьютера, и этот метод позволил достаточно быстро получить решение.

.Симметрия

Если повертеть Кубик Рубика влево-вправо или вверх-вниз, то, по сути, ничего не изменится: число шагов в решении останется тем же самым. Вместо того, чтобы решать все эти состояния, можно получить решение для одного и распространить его на повернутые состояния. Есть 24 различных ориентации в пространстве и 2 зеркальных положения Кубика для каждого состояния, что позволяет уменьшить число решаемых состояний в 48 раз. Если использовать аналогичные рассуждения и воспользоваться поиском задачи покрытия множества, то число подзадач уменьшается от 2 217 093 120 до 55882296.

.Хорошие и оптимальные решения

Оптимальное решение содержит достаточное количество шагов, но не более, чем необходимо. Так как уже известно одно состояние, для которого требуется 20 шагов, то можно не искать оптимальное решение для каждого состояния, а только решения в 20 или менее шагов. Это многократно ускоряет задачу.

.Оборудование

Для решения 55 882 296 подзадач компания Google предоставила целый парк компьютеров и все вычисления заняли всего несколько недель. Google не раскрывает характеристики компьютеров, но было затрачено 1,1 миллиард секунд (35 лет) компьютерного времени на выполнение расчетов. [5]

Заключение

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

Показана актуальность и практическая значимость работы.

Детально была рассмотрена структура системы. Проведена классификация системы, а также следующие описания:

·морфологическое, описывающее структуру системы, а также свойства каждого элементы системы;

·функциональное, в основе которого лежат составные части системы, их функции, входные и выходные данные;

·информационные, предоставляющее анализ свойств и связей каждого элемента системы.

Были изучены алгоритмы преобразования групп состояний кубика Рубика и определены основные факторы, влияющие на оптимизацию групп преобразований состояний кубика Рубика.

Список литературы

1.Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings The Cube: The Ultimate Guide to the World's Bestselling Puzzle - Secrets, Stories, Solutions. - N. Y., 2009

2.М. Евграфов Механика волшебного кубика // Квант. - 1982. - № 3. - С. 20-25

.David Joyner Adventures in group theory: Rubik's Cube, Merlin's machine, and Other Mathematical Toys. - Baltimore: Johns Hopkins University Press, 2002. - С. 7.

.В. Дубровский Алгоритм волшебного кубика // Квант. - 1982. - № 7. - С. 22-25.

.God's Number is 20 [Электронныйресурс] // URL: cube20.org

.К. Кноп Кубик Рубика: штурм твердыни [Электронный ресурс]// URL: #"justify">Приложение А

Алгоритм CFOP (алгоритм Джессики Фридрих)

Язык вращений:- front - фронтальная сторона- back - задняя сторона- left - левая сторона- right - правая сторона- up - верхняя сторона- down - нижняя сторона- фронтальная вместе со средним слоем- задняя вместе со средним слоем- левая вместе со средним слоем- правая вместе со средним слоем- верхняя вместе со средним слоем- нижняя вместе со средним слоем- средний слой, находящийся между левым и правым слоями- средний слой, находящийся между фронтальным и задним слоями- средний слой, находящийся между верхним и нижним слоями- весь куб вращается от себя по плоскости, совпадающей с правым слоем. Это, по сути, то же самое, что повернуть правую грань кубика по часовой стрелке вместе со всем кубиком.- весь куб по часовой в горизонтальной плоскости (верхнюю грань кубика по часовой стрелке вместе со всем кубиком)- весь куб по часовой в фронтальной плоскости (фронтальную грань кубика по часовой стрелке вместе со всем кубиком)

Приложение Б

Применение Кубика Рубика для объяснений в теории групп

.Множества и функции

ØМножествоэто набор элементов,каждый из которых содержится в множестве более одного раза.(Конечное) множество может быть задано явно в виде списка внутри пары фигурных скобок, например{2,4,6,8}это множество четных натуральных чисел меньше 10. Оно состоит из четырех элементов.Есть бесконечные множества - множества, имеющие бесконечное число элементов - таких, как множество целых чисел, но, как правило, обсуждаются только конечные множества (и группы).

На головоломках, мы часто рассматриваем множество состояний головоломки.

ØФункция F: АBотображающая множество А в множество В - это отношение, которое каждому элементу множества A сопоставляет некоторый элемент множества В.

Шаг на головоломки - это функция на множестве состояний. Шаг применяется к одному состоянию для перехода в другое.

ØФункция F:А -> B называется инъективной, если она сопоставляет различным элементам множества А различные элементы множества B.

Функция F:А -> B называется сюръективной, если каждый элемент множества B она сопоставляет с элементом множества А.

Функция F:А -> B называется биективной, если она является как инъективной, так и сюрьективной.

Функция f называется обратной к F (как правило обозначается F-1), если F:А -> B имеет обратную F-1:В -> А, такую, что всякий раз, когда аF = b, то bF-1 = а

Вращения кубика Рубика всегда обратимы. Например, шаг R, поворот по часовой стрелке правой грани, может быть отменен путем поворота правой грани против часовой стрелки. Обозначается какR-1, хотя R' является более распространенной.

ØКомпозицией двух функций F:А -> B и G:B -> С, называется функция, которая является результатом применения сначала F, а затем G. Таким образом, отображение элемента множества А в элемент множества С определяется по формуле = (аF)G. Эта функция обозначается F ◦ G.

Вращения могут быть объединены в последовательности вращений.

Любая последовательность шагов - это композиция. Например, если мы применяем последовательность вращений FRBк состоянию S, мы можем сделать ходы по одному, которые дают формулу ((SF)R)B, или в качестве одной функции F о R о В, что дает S (F о R о В).

ØФункция тождества IA:A ->A. Определяется аI = а для любого элемента а из множества А. Легко увидеть, функция тождества биективна.

Тождество на кубе - это последовательность перемещений, которые в итоге не меняют состояние, например, F2 B2 L2 R2 F2 B2 L2 R2.

.Группы и гомоморфизмы

ØГруппа замкнута относительно умножения, то есть, если перемножить любые два элемента группы, то результатом будет элемент этой же группы.

Можно объединить две последовательности ходов, чтобы получить третью.

ØСуществует единичный элемент, т.е. элемент е в группе такой, что для любого элемента g в группе у нас есть ge = eg = g.

Единичным элементом группы кубика Рубика является отсутствие вращения.

ØКаждый элемент имеет обратный, то есть, если G есть элемент группы, то есть элемент H в группе такой, что GH = HG = е. Обратный элемент G обозначается G-1.

Обратным элементом группы кубика Рубика является инверсия вращения, т.е. вращение в обратную сторону на тот же угол поворота.

ØУмножение ассоциативно, то есть, если, В и С являются элементами группы, то (АВ) С = А (ВС).

Ассоциативность группы кубика Рубика очевидна

ØГруппа конечна, если она имеет конечное число элементов. Число элементов в группе G называется порядком группы, и обозначается | G |.

Число состояний куба конечно, и, следовательно, число функций на этом множестве состояний также конечно. Группа кубика Рубика, следовательно, также конечна.

Существует еще одна группа - группа вращений куба в целом. Мы можем сделать верхней любую из шести граней, а затем есть четыре варианта, какая из смежных граней должны стать фронтальной. Следовательно, есть 24 возможные ориентации куба. Вращение всего куба это изменение между двумя такими ориентациями.

ØПорядок элемента g в группе это наименьшее натуральное число N, для которого gN = е (если такое N существует), где показатель обозначение gN имеет естественный смысл повторного умножения. Если такого числа не существует, то g, как говорят, бесконечный порядок. Порядок g обычно обозначается O (G).

В конечной группе все элементы имеют конечный порядок

Группа куба конечна. Если делать какие-либо последовательные вращения, а также постоянно повторять их, то в конечном итоге получится начальное состояние.

ØГомоморфизм - это отображение F: G -> H ставящее в соответствие всякому элементу g из группы G однозначно определенный элемент h из группы H, если всякий элемент g из группы G служит при этом отображении образом некоторого элемента h из группы H, и если для любых элементов g1, g2 группы G выполняется равенство (g1 · g2) F = (g1) F · (g2) F. Если гомоморфизм взаимно однозначен, то он называется изоморфизмом.

Существует гомоморфизм из обычного кубика Рубика 3 × 3 × 3 на Малый кубик 2 × 2 × 2. Любой шаг последовательности на кубике Рубика также может быть выполнен на Малом кубике. Таким образом, любая перестановка на обычном кубике привязывается к некоторой перестановке на маленьком кубике. Это отображение не является изоморфизмом, так как маленький кубик имеет группу, которая является упрощенной версией группы большего кубика.