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

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

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

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

До відомих головоломок, які підпадають під це визначення, відносяться кубик Рубика , Ханойська вежа , Гра в 15 , Солітер з фішками , Різні завдання про переливання і перевезення ( « Вовк, коза і капуста »). Загальним для всіх цих головоломок є те, що вони можуть бути описані у вигляді графа , Вершинами якого є всілякі конфігурації головоломки, а ребрами - допустимі переходи між ними ( «ходи»).

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

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

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

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

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

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

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

Число Бога для кубика Рубіка розміром 3х3х3 клітини дорівнює 20 - це діаметр графа Келі групи кубика Рубіка [8] .

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

  • Кубик Рубика 3 × 3 × 3 завжди може бути вирішене не більше ніж в 20 ходів (вважаючи за один хід поворот будь-який з 6 граней на 90 або 180 градусів). відомі конфігурації , Що вимагають для збірки не менше 20 ходів. Таким чином, «число Бога» кубика Рубіка одно 20 [9] .
  • Якщо дозволені лише повороти граней на 90 градусів (але не на 180 градусів, які можливі, але при цьому зараховуються за два ходи), «число Бога» кубика Рубіка одно 26 [10] .
  • Число Бога кубика 2 × 2 × 2 одно 11 ходам, якщо поворот межі на 180 ° вважається за 1 хід, або 14 ходам, якщо поворот межі на 180 ° вважається за 2 ходу. Невелике (3 674 160) кількість конфігурацій кубика 2 × 2 × 2 дозволило обчислити алгоритм Бога (у вигляді оптимального рішення для кожної конфігурації) ще в 80-х роках [11] .
  • Триколірний кубик, протилежні грані якого пофарбовані однаково. Число конфігурацій триколірного кубика одно

2 11 ⋅ 3 7 ⋅ C 12 4 ⋅ (C 8 4) 2 = 10 863 756 288 000 {\ displaystyle 2 ^ {11} \ cdot 3 ^ {7} \ cdot C_ {12} ^ {4} \ cdot ( C_ {8} ^ {4}) ^ {2} = 10 \ 863 \ 756 \ 288 \ 000} 2 11 ⋅ 3 7 ⋅ C 12 4 ⋅ (C 8 4) 2 = 10 863 756 288 000 {\ 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 хід) [13] У березні-квітні 2012 року було встановлено, що число Бога триколірного кубика одно 15 FTM , 17 QTM або 14 STM (згідно метриці STM, поворот будь-якого середнього шару також вважається за 1 хід) [13] .

  • « п'ятнашки »Можуть бути вирішені в 80 «Коротких» [14] або 43 «Довгих» [15] ходів в гіршому випадку (під «короткими» ходами маються на увазі переміщення окремих кісточок, а під «довгими» - переміщення цілих рядів з 1, 2 або 3 кісточок). Для узагальнених квача (з більшим, ніж 15, кількістю кісточок) завдання пошуку найкоротшого рішення є NP-повної [16] .
  • для Ханойська вежі алгоритм Бога існує при будь-якій кількості дисків, але з додаванням дисків число ходів росте експоненціально [17] .
  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 с. - ISBN 978-1-57912-805-0 .
  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 Читальний зал 29 травня 2014 року.
  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. Читальний зал 26 липня 2013 року.
  10. ↑ Rokicki, T. and Davidson, M. God's Number is 26 in the Quarter-Turn Metric (Англ.). Дата обігу 2 липня 2015.
  11. ↑ Jaap Scherphuis. Mini Cube, the 2 × 2 × 2 Rubik's Cube (Англ.). Дата звернення 21 липня 2013. Читальний зал 4 вересня 2013 року.
  12. ↑ Jaap Scherphuis. Pyraminx (Англ.). Дата звернення 21 липня 2013. Читальний зал 29 серпня 2013 року.
  13. ↑ Some 3-color cube results (неопр.). Domain of the Cube Forum. Дата звернення 29 липня 2013. Читальний зал 4 вересня 2013 року.
  14. ↑ 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.
  15. ↑ 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 року.
  16. ↑ 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.
  17. ↑ Carlos Rueda, «An optimal solution to the Towers of Hanoi Puzzle» .