Знайдено необхідне число ходів для вирішення кубика Рубіка

Знайдено необхідне число ходів для вирішення кубика Рубіка

Знайдено необхідне число ходів для вирішення кубика Рубіка

А за скільки зазвичай збираєте кубик Рубіка ви?

Деніел Кункле (Daniel Kunkle) і Жене Куперман (Gene Cooperman) з бостонського Північно-східного університету (Northeastern University) склали програму для суперкомп’ютера, яка за 63 години роботи знайшла таке мінімальне число ходів, якого завжди буде достатньо для складання кубика Рубіка з будь-якого вихідного становища.

Загальне число можливих комбінацій у класичного кубика Рубіка (3 х 3 х 3 клітки) становить 43 квінтильйони (мільярди мільярдів).

Знаходження всіх можливих шляхів вирішення для кожного вихідного положення — непосильне завдання навіть для суперкомп’ютера. Тому автори роботи придумали спеціальний алгоритм, що дозволив їм впритул підступитися до вирішення давньої проблеми — знаходженню «числа Бога» (Gods Number) — так називають найменше число ходів за які, в принципі, можлива збірка кубика з абсолютно будь-якого вихідного положення (мається на увазі, що Бог завжди знає найкоротший шлях).

Деніел і Жені запрограмували комп’ютер на пошук найкоротшого рішення для однієї з кожних 15 тисяч якихось проміжних позицій, встановивши заздалегідь, що кожну з них можна привести до збирання кубика за деякий розумне число кроків.

Так з’ясувалося, що з будь-якої вихідної позиції кубика його можна зібрати максимум за 29 ходів (а інший раз — набагато швидше). Тобто — інші рішення, з числом ходів 30, 75 або 200, наприклад, тут уже слід визнавати неоптимальними.

При цьому більшість вихідних позицій зажадало всього-то 26-ти і менше ходів для свого рішення.

Далі автори роботи зосередили свою увагу на декількох позиціях, вирішення яких вимагало 27-29 ходів. Число таких проблемних комбінацій було невелике, так що для них суперкомп’ютер міг перебрати всі варіанти стратегії складання кубика і знайти найкоротший. Виявилося, що всі важкі позиції також вирішуються за 26 ходів або швидше!

Не дарма, значить, нас дивують рекорди — читайте, наприклад, про 11-секундної збірці кубика.

Дослідники передбачають, що «число Бога», В кінцевому рахунку, повинно скласти 20 з невеликим. Так що в даному обчисленні вони впритул наблизилися до нього.

Свої викладки співавтори представили на міжнародному симпозіумі по символьних і алгебраїчним обчисленням (ISSAC 2007), що пройшов недавно в канадському місті Ватерлоо (Waterloo).

Дізнайтеся заодно про недавнє остаточному і повному вирішенні шашок.

Сподобалася стаття? Поділися нею з друзями!