Алгоритм Бога

Алгори́тм Бо́га — термін, який з'явився у зв'язку з обговоренням способів вирішення кубика Рубіка. Термін може також бути використаний у відношенні до інших перестановочних головоломок. Під алгоритмом Бога головоломки розуміється будь-який алгоритм, котрий дозволяє отримати рішення головоломки, яке містить мінімально можливе число ходів (оптимальне рішення), починаючи з будь-якої заданої конфігурації.

Один із піонерів математичної теорії кубика Рубіка Девід Сінгмастер описує появу терміну таким чином:

Джон Конвей, один з найбільших спеціалістів по теорії груп у світі, відмітив, що Кубик Рубіка підпорядковується так званим законам збереження (або парності), а це означає, що деякі рухи просто неможливі. Конвей або один із його колег в Кембриджі визначив найкоротший шлях з будь-якого даного стану назад до початкового стану як «Алгоритм Бога».

Оригінальний текст (англ.)

John Conway, one of the world's greatest group theorists, observed that the Cube obeys what are known as conservation (or parity) laws, meaning that some moves are simply not possible. Either Conway or one of his colleagues at Cambridge defined the shortest route from any given position back to the starting position as «God's Algorithm».

— Девід Сінгмастер

Визначення

Алгоритм Бога може існувати для головоломок зі скінченним числом можливих конфігурацій і з скінченним набором «ходів», які допускаються у кожній конфігурації і які переводять поточну конфігурацію в іншу. Термін «розв'язати головоломку» означає — вказати послідовність ходів, що переводять деяку початкову конфігурацію в деяку кінцеву конфігурацію. Оптимально вирішити головоломку — вказати найкоротшу послідовність ходів для вирішення головоломки. Оптимальних рішень може бути декілька.

До відомих головоломок, які підпадають під це визначення, належать кубик Рубіка, Ханойська вежа, П'ятнашки, ^[en], різні завдання про переливання та перевезення («Вовк, коза і капуста»). Спільним для всіх цих головоломок є те, що вони можуть бути описані у вигляді графу, вершинами якого є всілякі конфігурації головоломки, а ребрами — допустимі переходи між ними («ходи»).

У багатьох подібних головоломках кінцева конфігурація негласно передбачається, наприклад, в «п'ятнашках» — впорядковане розташування кісточок, для кубика Рубіка — однокольоровість граней. У цих випадках «зібрати головоломку» означає, що потрібно для довільної початковій конфігурації вказати послідовність ходів, що приводять у фіксовану кінцеву конфігурацію.

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

Тоді алгоритм Бога (для даної головоломки) — це алгоритм, який вирішує головоломку і знаходить для довільної пари конфігурацій хоча б одне оптимальне рішення.

Деякі автори вважають, що алгоритм Бога повинен також бути практичним, тобто використовувати розумний обсяг пам'яті і завершуватися в розумний час.

Нехай G — група (із заданою породжуючою множиною), v — вершина графу Келі групи G. Знайти (ефектнивний), практичний алгоритм для визначення шляху із v до вершини v₀, пов'язану з нейтральним елементом, довжина якого дорівнює відстані від v до v₀. […] Цей алгоритм називається алгоритмом Бога.

Оригінальний текст (англ.)

Let G be the group of a permutation puzzle (with a fixed generating set) and let v be a vertex in the Cayley graph of G. Find an effective, practical algorithm for determining a path from v to the vertex v₀ associated to the identity having a length equal to the distance from v to v₀. [...] This algorithm is called God’s algorithm.

— Девід Джойнер

Практичність можна розуміти по-різному. Так, існують комп'ютерні програми, які дозволяють за прийнятний час знайти оптимальне рішення для довільної конфігурації кубика Рубіка. Водночас аналогічна задача для кубика 4 × 4 × 4 на даний момент залишається практично нездійсненною. Для деяких головоломок існує стратегія, що дозволяє відповідно до простих правил визначити оптимальне рішення вручну, без допомоги комп'ютера.

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

Число Бога

Числом Бога даної головоломки називається число n, таке, що існує хоча б одна конфігурація головоломки, оптимальне рішення якої складається з n ходів, і не існує жодної конфігурації, довжина оптимального вирішення якої перевищує n. Іншими словами, число Бога — це точна верхня грань множини довжин оптимальних рішень конфігурацій головоломки.

Число Бога для кубика Рубіка дорівнює 20 — це діаметр графу Келі (групи кубика Рубіка).

У загальному випадку (для довільної перестановної головоломки), число Бога дорівнює не діаметру графу Келі групи головоломки, а (ексцентриситету вершини), що відповідає «зібраному» стану головоломки.

Приклади

• Кубик Рубіка 3×3×3 завжди може бути вирішене не більше ніж в 20 ходів (^[en]), вимагають для збірки не менше 20 ходів. Таким чином, «число Бога» кубика Рубіка дорівнює 20.

• Число Бога кубика Рубіка 2 × 2 × 2 дорівнює 11 ходам, якщо поворот грані на 180° вважається за 1 хід, або 14 ходам, якщо поворот грані на 180° вважається за 2 ходи. Невелика (3674160) кількість конфігурацій кубика Рубіка 2 × 2 × 2 дозволило обчислити алгоритм Бога (у вигляді оптимального рішення для кожної конфігурації) ще в 80-х роках.

• Число Бога пірамідки Мефферта дорівнює 11.

• Триколірний кубик — кубик Рубіка, протилежні грані якого пофарбовані однаково. Число конфігурацій триколірного кубика дорівнює

${\displaystyle 2^{11}\cdot 3^{7}\cdot C_{12}^{4}\cdot (C_{8}^{4})^{2}=10\ 863\ 756\ 288\ 000}$

У березні-квітні 2012 року було встановлено, що число Бога триколірного кубика дорівнює 15 (FTM), 17 QTM або 14 STM (згідно (метриці) STM, поворот будь-якого середнього шару також вважається за 1 хід).

• П'ятнашки можуть бути вирішені в 80 «коротких» або 43 «довгих» ходів в гіршому випадку (під «короткими» ходами маються на увазі переміщення окремих кісточок, а під «довгими» — переміщення цілих рядів з 1, 2 або 3 кісточок). Для узагальнених пятнашек (з більшим, ніж 15, кількістю кісточок) завдання пошуку найкоротшого рішення є NP-повної.

• Для Ханойської вежі алгоритм Бога існує при будь-якій кількості дисків, але з додаванням дисків число ходів зростає експоненціально.

Див. також

• Кубик Рубіка
• Пірамідка Мефферта

Примітки

1. История кубика Рубика. Архів оригіналу за 4 вересня 2013. Процитовано 20 липня 2013.
2. Joyner, David (2002). Adventures in group theory: Rubik's Cube, Merlin's machine, and Other Mathematical Toys. Baltimore: Johns Hopkins University Press. ISBN .
3. Herbert Kociemba. Cube Explorer. Архів оригіналу за 4 вересня 2013. Процитовано 27 липня 2013.
4. . Архів оригіналу за 29 травня 2014. Процитовано 28 травня 2014.
5. . Архів оригіналу за 29 травня 2014. Процитовано 28 травня 2014.
6. . Архів оригіналу за 29 травня 2014. Процитовано 28 травня 2014.
7. Weisstein, Eric W. . Архів оригіналу за 28 березня 2014. Процитовано 28 травня 2014.
8. Rokicki, T.; Kociemba, H.; Davidson, M.; and Dethridge, J. God's Number is 20 (англ.). Архів оригіналу за 26 липня 2013. Процитовано 19 липня 2013.
9. Jaap Scherphuis. Mini Cube, the 2×2×2 Rubik's Cube (англ.). Архів оригіналу за 4 вересня 2013. Процитовано 21 липня 2013.
10. Jaap Scherphuis. Pyraminx (англ.). Архів оригіналу за 29 серпня 2013. Процитовано 21 липня 2013.
11. Some 3-color cube results. Domain of the Cube Forum. Архів оригіналу за 4 вересня 2013. Процитовано 29 липня 2013.
12. A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications [ 11 листопада 2017 у Wayback Machine.], Annals of Operations Research 90 (1999), pp. 45-63.
13. Bruce Norskog (Wed, 12/08/2010 - 16:43). The Fifteen Puzzle can be solved in 43 "moves" (англ.). Архів оригіналу за 4 вересня 2013. Процитовано 20 липня 2013.
14. Daniel Ratner, Manfred K. Warmuth (1986). «Finding a shortest solution for the N × N extension of the 15-puzzle is intractable» [ 9 березня 2012 у Wayback Machine.]. in Proceedings AAAI-86. National Conference on Artificial Intelligence, 1986. pp. 168–172.
15. Carlos Rueda, .

Посилання

• (Костянтин Кноп)
• Алгоритм Бога і число Бога [ 30 травня 2014 у Wayback Machine.] (Sliding Tile Puzzle Corner)