Алгоритм Бога
Алгори́тм Бо́га — термін, який з'явився у зв'язку з обговоренням способів вирішення кубика Рубіка. Термін може також бути використаний у відношенні до інших перестановочних головоломок. Під алгоритмом Бога головоломки розуміється будь-який алгоритм, котрий дозволяє отримати рішення головоломки, яке містить мінімально можливе число ходів (оптимальне рішення), починаючи з будь-якої заданної конфігурації.
Один із піонерів математичної теорії кубика Рубіка Девід Сінгмастер[1] описує появу терміну таким чином:
Джон Конвей, один з найбільших спеціалістів по теорії груп у світі, відмітив, що Кубик Рубіка підпорядковується так званим законам збереження (або парності), а це означає, що деякі рухи просто неможливі. Конвей або один із його колег в Кембриджі визначив найкоротший шлях з будь-якого даного стану назад до початкового стану як «Алгоритм Бога».[
Визначення
Алгоритм Бога може існувати для головоломок з кінцевим числом можливих конфігурацій і з кінцевим набором «ходів», які допускаються у кожній конфігурації і які переводять поточну конфігурацію в іншу. Термін «розв'язати головоломку» означає — вказати послідовність ходів, що переводять деяку початкову конфігурацію в деяку кінцеву конфігурацію. Оптимально вирішити головоломку — вказати найкоротшу послідовність ходів для вирішення головоломки. Оптимальних рішень може бути декілька.
До відомих головоломок, які підпадають під це визначення, належать кубик Рубіка, Ханойська вежа, П'ятнашки, Солітер з фішками (англ.), різні завдання про переливання та перевезення («Вовк, коза і капуста»). Спільним для всіх цих головоломок є те, що вони можуть бути описані у вигляді графа, вершинами якого є всілякі конфігурації головоломки, а ребрами — допустимі переходи між ними («ходи»).
У багатьох подібних головоломках кінцева конфігурація негласно передбачається, наприклад, в «п'ятнашках» — впорядковане розташування кісточок, для кубика Рубіка — однокольоровість граней. У цих випадках «зібрати головоломку» означає, що потрібно для довільної початковій конфігурації вказати послідовність ходів, що приводять у фіксовану кінцеву конфігурацію.
Алгоритм вирішує головоломку, якщо він приймає в якості вихідних даних довільну пару початкової та кінцевої конфігурацій (або тільки початкову конфігурацію, якщо кінцева конфігурація зафіксована) і повертає в якості результату послідовність ходів, що переводять початкову конфігурацію в кінцеву (якщо така послідовність існує, в іншому випадку, алгоритм повідомляє про неможливість рішення). Оптимальне рішення містить мінімально можливу кількість ходів.
Тоді алгоритм Бога (для даної головоломки) — це алгоритм, який вирішує головоломку і знаходить для довільної пари конфігурацій хоча б одне оптимальне рішення.
Деякі автори вважають, що алгоритм Бога повинен також бути практичним, тобто використовувати розумний обсяг пам'яті і завершуватися в розумний час.
Нехай G — група перестановочної головоломки (із заданою породжуючою множиною), v — вершина графа Келі групи G. Знайти ефектнивний, практичний алгоритм для визначення шляху із v до вершини v0, пов'язану з нейтральним елементом, довжина якого дорівнює відстані від v до v0. […] Цей алгоритм називається алгоритмом Бога.— Девід Джойнер[2]
Приктичність можна розуміти по-різному. Так, існують комп'ютерні програми, які дозволяють за прийнятний час знайти оптимальне рішення для довільної конфігурації кубика Рубіка[3]. Водночас аналогічна задача для кубика 4 × 4 × 4 на даний момент залишається практично нездійсненною[4][5][6]. Для деяких головоломок існує стратегія, що дозволяє відповідно до простих правил визначити оптимальне рішення вручну, без допомоги комп'ютера.
Альтернативне визначення алгоритму Бога: від алгоритму не потрібно знаходження всієї послідовності ходів; замість цього достатньо знайти перший хід оптимального рішення, що наближує до мети і переводить в нову конфігурацію. Два визначення є еквівалентними: повторне застосування алгоритму до нової пари конфігурацій знову знаходить хід оптимального рішення, що дозволяє отримати всю послідовність ходів оптимального рішення.
Число Бога
Числом Бога даної головоломки називається число n, таке, що існує хоча б одна конфігурація головоломки, оптимальне рішення якої складається з n ходів, і не існує жодної конфігурації, довжина оптимального вирішення якої перевищує n. Іншими словами, число Бога — це точна верхня грань множини довжин оптимальних рішень конфігурацій головоломки.
У загальному випадку (для довільної перестановною головоломки), число Бога дорівнює не діаметру графа Келі групи головоломки, а ексцентриситету вершини, відповідної «зібраному» стану головоломки.
Приклади
- Кубик Рубіка 3×3×3 завжди може бути вирішене не більше ніж в 20 ходів[8]. Відомі конфігурації(англ.), вимагають для збірки не менше 20 ходів. Таким чином, «число Бога» кубика Рубіка дорівнює 20.
- Число Бога кубика Рубіка 2 × 2 × 2 дорівнює 11 ходам, якщо поворот грані на 180° вважається за 1 хід, або 14 ходам, якщо поворот грані на 180° вважається за 2 ходи. Невелика (3674160) кількість конфігурацій кубика Рубіка 2 × 2 × 2 дозволило обчислити алгоритм Бога (у вигляді оптимального рішення для кожної конфігурації) ще в 80-х роках[9].
- Число Бога пірамідки Мефферта дорівнює 11[10].
- Триколірний кубик — кубик Рубіка, протилежні грані якого пофарбовані однаково. Число конфігурацій триколірного кубика дорівнює
- У березні-квітні 2012 року було встановлено, що число Бога триколірного кубика дорівнює 15 FTM, 17 QTM або 14 STM (згідно метриці STM, поворот будь-якого середнього шару також вважається за 1 хід)[11].
- П'ятнашки можуть бути вирішені в 80 «коротких»[12] або 43 «довгих»[13] ходів в гіршому випадку (під «короткими» ходами маються на увазі переміщення окремих кісточок, а під «довгими» — переміщення цілих рядів з 1, 2 або 3 кісточок). Для узагальнених пятнашек (з більшим, ніж 15, кількістю кісточок) завдання пошукунайкоротшого рішення є NP-повної[14].
- Для Ханойської вежі алгоритм Бога існує при будь-якій кількості дисків, але з додаванням дисків число ходів зростає експоненціально[15].
Немає коментарів:
Дописати коментар