Я жодного разу не збирав Кубик Рубика. Навіть в дитинстві у мене завжди було багато цікавіших справ. Але якщо чесно - у мене просто не виходило.
Минулого тижня відбулася подія, яка змусила мене дізнатися, що таке Алгоритм Бога, Число Бога, і як це пов'язано з кубиками.
Три на три на три - не так вже й складно
Комбінаторика - це такий розділ математики, в якому все можна по-різному перемішати. Цей безлад всім подобається, але любиш кататися, люби і саночки возити. В комбінаториці всі ці перемішування прийнято підраховувати. Це не так вже й просто, майже як збирати Кубик Рубика.
Припустимо, ви знайшли три різнокольорових кубика Лего в кафе, де ви чекаєте когось, але цей хтось спізнюється. Ви починаєте по-різному поєднувати ці три кубика, створюючи всілякі комбінації з них. Вам звичайно все одно, ви думаєте тільки про час. Але комбинаторика знає - ви можете зібрати 3! унікальних конфігурацій. 3! це не трійка, яка повинна вас здивувати, це факторіал трійки. 3! = 1 × 2 × 3 = 6. «Більше шести конфігурацій зібрати не вийде», - каже комбінаторика, але нам все одно, час підтискає.
- 3! варіантів перестановок трьох кубиків і чоловічок А. Але хіба Лего може асоціюватися з кафе?
Так ось, якщо б ви крутили в кафе Кубик Рубика, справа була б трохи більше безнадійним. Коли ми крутимо Кубик Рубика, комбінаторика говорить нам наступне:
- Те, що може зайняти 211 человечеств на цілий рік, можна купити за 30 рублів. Мене це ніколи не перестане дивувати.
Причому тут Бог
Алгоритм Бога - це такий алгоритм, який вирішує Кубик Рубика за мінімальне число ходів. Найцікавіше, що ніхто навіть не знає, чи існує цей алгоритм чи ні. Це, мабуть, єдине, що у них спільного з Богом.
Число Бога для Кубика Рубика - мінімальне число ходів за яке Алгоритм Бога гарантовано вирішить будь-яку конфігурацію Кубика. Тобто існують конфігурації, які Алгоритм Бога вирішує за 1 хід. Але не Сущетсвует таких, на які він витрачає більше ходів, ніж Число Бога.
Минулого тижня кілька дослідників заявили. що вони вирахували число Бога.
Число Бога для алгоритму Кубика Рубика - 20. Так, шкода, що не 42.
20 - це досить звичайне число, але в контексті Кубика Рубика немає числа більш саркастичного і принизливого. Справа в тому, що в Кубику Рубика 20 рухомих деталей. Зізнайтеся, засмучуються ви хоч раз хотіли розібрати Кубик, щоб потім правильно його зібрати і заспокоїтися? У цей час число Бога сміялося над вами!
Адже деталей-то теж 20.
Занадто багато цифр для однієї статті
Що може бути простіше, залишилося тільки поперебірать комбінації. Ось як вони вирішили це зробити ***:
- Розбити вихідні 43 252 003 274 489 856 000 станів на 2 217 093 120 підмножин
- Скоротити число підмножин до 55 882 296, тому що одні виходять з інших поворотами або дзеркальними відображеннями Кубика
- Чи не шукати оптимальне рішення для кожного стану, задовольнятися будь-яким не довше 20 ходів
- Написати програму, яка вирішує одне підмножина за приблизно 20 секунд
Пункт 1) дуже важливий для того, щоб виконати пункт 2). Треба бути хитрим лисом, щоб скласти підмножини саме так, щоб їх потім скоротити.
Небажання шукати оптимальні шляхи в пункті 3) теж не примха. Вони звичайно могли б робити це, але їм нема чого - вони просто хотіли перевірити, що Число Бога це 20, а не знайти все оптимальні шляхи для будь-яких змін.
Обробивши все підмножини, вони не знайшли жодного стану, яке вимагає 21 або більше ходів для вирішення. А значить довели - Число Бога для Кубика Рубіка одно 20.
Як перевірити, що ви все зрозуміли?
Знайти Число Бога не означає знайти Алгоритм Бога. Якщо ви розумієте це і згодні, то ви все зрозуміли. Інакше, можете спробувати перечитати визначення Алгоритму Бога і Числа Бога.
Як утерти хлопцям ніс?
Ви можете обставити їх, я не жартую. Для це вам треба придумати алгоритм, який в пункті 3) буде шукати тільки оптимальні ходи. Це і буде Алгоритмом Бога, а вам, ймовірно, будуть цілувати ноги.
Цікаві факти по темі
- Конфігурації Кубика, які вимагають 20 ходів для вирішення, не так вже й часто зустрічаються (приблизно +0,0000000007% від загального числа конфігурацій). Перша була виявлена тільки через 15 років після появи Кубика на світло.
- Комп'ютери вирішують Кубик Рубика швидше, ніж люди на них дивляться. Для перебору всіх варіантів знадобилося 35 ядро-років. Це означає, що одне ядро одного комп'ютера, на якому вироблялися обчислення, впоралося б з ними за 35 років. Скільки ядер було у них в розпорядженні, дослідники не повідомляють.
- Комп'ютерні потужності для вирішення завдання надала компанія Google, в якій працює один з дослідників.
Іноді в кінці статей я задаю питання - чому? Але сьогодні інша історія, адже не зовсім зрозуміло, навіщо знати число Бога для Кубика Рубика. Якщо ви думаєте, що я зараз скажу: «Попалися!», - пожартую жарт і ненароком розповім, яку велику користь принесе це відкриття, то ви помиляєтеся. Я не знаю навіщо. Але я знаю, що ми можемо винести для себе з усього цього.
Насправді, ми давно вже це винесли це для себе - якщо розбити задачу на підзадачі, то її рішення помітно спрощується. Вся проблема в тому, щоб правильно розбити.
А ще наступають нові часи для науки, коли деякі речі стає швидше перевірити, ніж довести. Але про це я одного разу вже писав мигцем.
Розділіть і володарюйте!
* - у великому числі однакові конфігурації Кубика, повернені і відбиті, враховуються як різні; а під населенням Землі розуміється 6,5 мільярда чоловік, які не сплять, не їдять, а тільки витріщаються на кубики 24 години на добу
** - в 1799 році народився самий неоцінений мною письменник Олександр Сергійович Пушкін
*** - пункти «. »І« PROFIT »опущені через повагу до читача