Математика кубика Рубика

Математика кубика Рубика - сукупність математичних методів для вивчення властивостей кубика Рубіка з абстрактно-математичної точки зору. Цей напрямок математики вивчає алгоритми складання кубика і оцінює їх. Заснована на теорії графів , теорії груп , теорії обчислюваності і комбінаторики .

Існує безліч алгоритмів , призначених для перекладу кубика Рубіка з довільної конфігурації в кінцеву конфігурацію (зібраний куб). У 2010 році строго доведено, що для перекладу кубика Рубіка з довільної конфігурації в зібрану конфігурацію (часто цей процес називають «складанням» або «рішенням») досить не більше ніж 20 поворотів граней [1] . Це число - діаметр графа Келі групи кубика Рубика [2] . У 2014 році доведено, що для вирішення кубика Рубіка тільки за допомогою поворотів граней на 90 ° ніколи не бракує 26 ходів [3] .

Алгоритм, який вирішує головоломку за мінімально можливу кількість ходів, називають алгоритмом Бога >>> .

[pic 1]

зміст

• 1позначення
• 2Метрики графа конфігурацій
• 3Група кубика Рубіка
• 4алгоритм Бога

• 4.1Нижні оцінки числа Бога
• 4.2Верхні оцінки числа Бога

• 4.2.1алгоритм Тістлетуейта

• 4.2.1.1опис
• 4.2.1.2Граф Шрайера

• 4.2.2Модифікації алгоритму Тістлетуейта
• 4.2.3Двофазний алгоритм Коцемби

• 4.2.3.1опис
• 4.2.3.2Альтернативні субоптимальних рішення
• 4.2.3.3особливості реалізації
• 4.2.3.4програмні реалізації
• 4.2.3.5аналіз

• 4.3алгоритм Корфа
• 4.4подальші поліпшення
• 4.5Пошук антиподів
• 4.6асимптотичні оцінки

• 5інші головоломки

• 5.1Void Cube
• 5.2Кубик 4 × 4 × 4

• 5.2.1Метрики 4 × 4 × 4
• 5.2.2Оцінки числа Бога кубика 4 × 4 × 4

• 5.3Мегамінкс

• 6Див. також
• 7Примітки
• 8рекомендована література
• 9посилання

Позначення 

Метрики графа конфігурацій [ правити | правити код ]

Існує два найбільш поширених способу вимірювання довжини рішення ( метрики ). Перший спосіб - одним ходом рішення вважається поворот межі на 90 ° ( quarter turn metric , QTM ). За другим способом, за 1 хід також вважається і напівоберт межі ( face turn metric , FTM , іноді це позначають HTM - half-turn metric ). Так, F2 (поворот передній грані на 180 °) повинен вважатися за два ходи в метриці QTM або за 1 хід в метриці FTM [6] [7] .

Для вказівки в тексті довжини послідовності для використовуваної метрики використовується нотація [8] [9] [10] , що складається з цифр числа ходів і малої першої літери позначення метрики. 14f позначає «14 ходів в метриці FTM», а 10q - «10 ходів в метриці QTM». Щоб вказати, що кількість ходів є мінімальним в даній метриці, використовується зірочка : 10f * позначає оптимальність рішення в 10 ходів FTM.

Група кубика Рубика [ правити | правити код ]

Основна стаття: Група кубика Рубіка

Кубик Рубика може розглядатися як приклад математичної групи .