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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Один из пионеров математической теории кубика Рубика Дэвид Сингмастер[1] так описывает появление термина:

Джон Конвей, один из крупнейших специалистов по теории групп в мире, отметил, что Кубик подчиняется так называемым законам сохранения (или чётности), а это означает, что некоторые движения просто невозможны. Либо Конвей, либо один из его коллег в Кембридже определил кратчайший путь из любого данного состояния назад к начальному состоянию как «Алгоритм Бога».

Дэвид Сингмастер[2]

Определение[править | править вики-текст]

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

К известным головоломкам, подпадающим под это определение, относятся кубик Рубика, Ханойская башня, Пятнашки, Солитер с фишками (англ.), различные задачи о переливании и перевозке («Волк, коза (овца) и капуста»). Общим для всех этих головоломок является то, что они могут быть описаны в виде графа, вершинами которого являются всевозможные конфигурации головоломки, а рёбрами — допустимые переходы между ними («ходы»).

Во многих подобных головоломках конечная конфигурация негласно предполагается, например, в «пятнашках» — упорядоченное расположение косточек, для кубика Рубика — одноцветность граней. В этих случаях «собрать головоломку» означает, что требуется для произвольной начальной конфигурации указать последовательность ходов, приводящих в фиксированную конечную конфигурацию.

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

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

Некоторые авторы считают, что алгоритм Бога должен также быть практичным, то есть использовать разумный объём памяти и завершаться в разумное время.

Пусть G — группа перестановочной головоломки (с заданным порождающим множеством), v — вершина графа Кэли группы G. Найти эффективный, практичный алгоритм для определения пути из v в вершину v0, связанную с нейтральным элементом, длина которого равна расстоянию от v до v0. [...] Этот алгоритм называется алгоритмом Бога.

— Дэвид Джойнер[3]

Практичность можно понимать по-разному. Так, существуют компьютерные программы, позволяющие за приемлемое время найти оптимальное решение для произвольной конфигурации кубика Рубика[4]. В то же время аналогичная задача для кубика 4×4×4 на данный момент остаётся практически неосуществимой[5][6][7]. Для некоторых головоломок существует стратегия, позволяющая в соответствии с простыми правилами определить оптимальное решение вручную, без помощи компьютера.

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

Число Бога[править | править вики-текст]

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

Число Бога для кубика Рубика равно 20 — это диаметр графа Кэли группы кубика Рубика[8].

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

Примеры[править | править вики-текст]

  • Кубик Рубика 3×3×3 всегда может быть решён не более чем в 20 ходов[9]. Известны конфигурации (англ.), требующие для сборки не менее 20 ходов. Таким образом, «число Бога» кубика Рубика равно 20.
  • Число Бога кубика Рубика 2×2×2 равно 11 ходам, если поворот грани на 180° считается за 1 ход, или 14 ходам, если поворот грани на 180° считается за 2 хода. Небольшое (3674160) количество конфигураций кубика Рубика 2×2×2 позволило вычислить алгоритм Бога (в виде оптимального решения для каждой конфигурации) ещё в 80-х годах[10].
  • Трёхцветный кубик — кубик Рубика, противоположные грани которого окрашены одинаково. Число конфигураций трёхцветного кубика равно
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 ход)[12].
  • Пятнашки могут быть решены в 80 «коротких»[13] или 43 «длинных»[14] ходов в худшем случае (под «короткими» ходами подразумеваются перемещения отдельных костяшек, а под «длинными» — перемещения целых рядов из 1, 2 или 3 костяшек). Для обобщённых пятнашек (с бо́льшим, чем 15, количеством костяшек) задача поиска кратчайшего решения является NP-полной[15].
  • Для Ханойской башни алгоритм Бога существует при любом количестве дисков, но с добавлением дисков число ходов растёт экспоненциально[16].

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. История кубика Рубика. Проверено 20 июля 2013. Архивировано из первоисточника 4 сентября 2013.
  2. Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings The Cube: The Ultimate Guide to the World's Bestselling Puzzle — Secrets, Stories, Solutions. — 2009. — С. 26. — 142 с.
  3. David Joyner Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys. — 2008. — С. 149. — 328 с.
  4. Herbert Kociemba. Cube Explorer. Проверено 27 июля 2013. Архивировано из первоисточника 4 сентября 2013.
  5. Bigger rubik cube bound
  6. 4x4x4 algorithm generator? (like cube explorer)
  7. 4x4 Algorithms
  8. Weisstein, Eric W. God's Number.
  9. Rokicki, T.; Kociemba, H.; Davidson, M.; and Dethridge, J. God's Number is 20 (англ.). Проверено 19 июля 2013. Архивировано из первоисточника 27 июля 2013.
  10. Jaap Scherphuis. Mini Cube, the 2×2×2 Rubik's Cube (англ.). Проверено 21 июля 2013. Архивировано из первоисточника 4 сентября 2013.
  11. Jaap Scherphuis. Pyraminx (англ.). Проверено 21 июля 2013. Архивировано из первоисточника 29 августа 2013.
  12. Some 3-color cube results. Domain of the Cube Forum. Проверено 29 июля 2013. Архивировано из первоисточника 4 сентября 2013.
  13. A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications, Annals of Operations Research 90 (1999), pp. 45-63.
  14. Bruce Norskog. The Fifteen Puzzle can be solved in 43 "moves" Domain of the Cube Forum (англ.) (Wed, 12/08/2010 - 16:43). Проверено 20 июля 2013. Архивировано из первоисточника 4 сентября 2013.
  15. Daniel Ratner, Manfred K. Warmuth (1986). «Finding a shortest solution for the N × N extension of the 15-puzzle is intractable». in Proceedings AAAI-86. National Conference on Artificial Intelligence, 1986. pp. 168—172.
  16. Carlos Rueda, «An optimal solution to the Towers of Hanoi Puzzle».

Ссылки[править | править вики-текст]