Просмотр кода страницы Алгоритм бога

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

Один из пионеров математической теории кубика Рубика [[Сингмастер, Дэвид|Дэвид Сингмастер]]<ref name="cubemir_history" /> так описывает появление термина:

{{начало цитаты}}
[[Конвей, Джон Хортон|Джон Конвей]], один из крупнейших специалистов по теории групп в мире, отметил, что Кубик подчиняется так называемым законам сохранения (или чётности), а это означает, что некоторые движения просто невозможны. Либо Конвей, либо один из его коллег в [[Кембридж]]е определил кратчайший путь из любого данного состояния назад к начальному состоянию как «Алгоритм Бога».
{{oq|en|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.“}}
{{конец цитаты|источник=Дэвид Сингмастер<ref name="slocum2009" />}}

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

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

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

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

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

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

{{начало цитаты}}
Пусть ''G'' — группа [[Перестановочные головоломки|перестановочной головоломки]] (с заданным порождающим множеством), ''v'' — вершина графа Кэли группы ''G''. Найти [[Алгоритм#Эффективность алгоритмов|эффективный]], практичный алгоритм для определения пути из ''v'' в вершину ''v''<sub>0</sub>, связанную с нейтральным элементом, длина которого равна расстоянию от ''v'' до ''v''<sub>0</sub>. [...] Этот алгоритм называется '''алгоритмом Бога'''.
{{oq|en|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<sub>0</sub> associated to the identity having a length equal to the distance from v to v<sub>0</sub>. [...] This algorithm is called '''God’s algorithm'''.}}
{{конец цитаты|источник=Дэвид Джойнер<ref name="joyner" />}}

Практичность можно понимать по-разному. Так, существуют компьютерные программы, позволяющие за приемлемое время найти оптимальное решение для произвольной конфигурации кубика Рубика<ref name="cubeexplorer" />. В то же время аналогичная задача для кубика 4×4×4 на данный момент остаётся практически неосуществимой<ref>[http://forum.projecteuler.net/viewtopic.php?f=26&t=2155 Bigger rubik cube bound] {{webarchive|url=https://web.archive.org/web/20140529052631/http://forum.projecteuler.net/viewtopic.php?f=26&t=2155 |date=2014-05-29 }}</ref><ref>{{Cite web |url=http://www.speedsolving.com/forum/showthread.php?19287-4x4x4-algorithm-generator-(like-cube-explorer) |title=4x4x4 algorithm generator? (like cube explorer) |access-date=2013-07-26 |archive-date=2014-05-29 |archive-url=https://web.archive.org/web/20140529052807/http://www.speedsolving.com/forum/showthread.php?19287-4x4x4-algorithm-generator-(like-cube-explorer) |deadlink=no }}</ref><ref>{{Cite web |url=http://comments.gmane.org/gmane.games.rubiks.speedsolving/19012 |title=4x4 Algorithms |accessdate=2013-07-26 |archiveurl=https://web.archive.org/web/20140529052144/http://comments.gmane.org/gmane.games.rubiks.speedsolving/19012 |archivedate=2014-05-29 |deadlink=yes }}</ref>. Для [[Ханойская башня|некоторых головоломок]] существует стратегия, позволяющая в соответствии с простыми правилами определить оптимальное решение вручную, без помощи компьютера.

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

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

Число Бога для кубика Рубика размером 3х3х3 клетки равно 20 — это диаметр [[Граф Кэли|графа Кэли]] [[Группа кубика Рубика|группы кубика Рубика]]<ref name="mathworld_gn" />.

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

== Примеры ==
{{seealso|Математика кубика Рубика#Другие головоломки}}
* [[Кубик Рубика]] {{times|3|3|3}} всегда может быть решён не более чем в {{ч|20}} ходов (считая за один ход поворот любой из 6 граней на 90 или 180 градусов). [[Суперфлип|Известны конфигурации]], требующие для сборки не менее 20 ходов. Таким образом, «число Бога» кубика Рубика равно 20<ref name="cube20" />.
* Если разрешены лишь повороты граней на 90 градусов (но не на 180 градусов, которые возможны, но при этом засчитываются за два хода), «число Бога» кубика Рубика равно {{ч|26}}<ref name="cube26" />.
* Число Бога кубика {{times|2|2|2}} равно {{ч|11}} ходам, если поворот грани на 180° считается за 1 ход, или {{ч|14}} ходам, если поворот грани на 180° считается за 2 хода. Небольшое ({{num|3674160}}) количество конфигураций кубика {{times|2|2|2}} позволило вычислить алгоритм Бога (в виде оптимального решения для каждой конфигурации) ещё в 80-х годах<ref name="minicube" />.
* Число Бога [[Пирамидка Мефферта|пирамидки Мефферта]] равно {{ч|11}}<ref name="pyraminx11" />.
* Трёхцветный кубик, противоположные грани которого окрашены одинаково. Число конфигураций трёхцветного кубика равно
<center><math>2^{11}\cdot 3^7\cdot C_{12}^4\cdot (C_8^4)^2=10\ 863\ 756\ 288\ 000</math></center>
: В марте-апреле 2012 года было установлено, что число Бога трёхцветного кубика равно {{ч|15}} [[Математика кубика Рубика#metrics|FTM]], {{ч|17}} QTM или {{ч|14}} STM (согласно [[Математика кубика Рубика#metrics|метрике]] STM, поворот любого среднего слоя также считается за 1 ход)<ref name="norskog_3color" />.

* «[[Игра в 15|Пятнашки]]» могут быть решены в {{ч|80}} «коротких»<ref name="stm80" /> или {{ч|43}} «длинных»<ref name="mtm43" /> ходов в худшем случае (под «короткими» ходами подразумеваются перемещения отдельных костяшек, а под «длинными» — перемещения целых рядов из 1, 2 или 3 костяшек). Для обобщённых пятнашек (с бо́льшим, чем 15, количеством костяшек) задача поиска ''кратчайшего'' решения является [[NP-полная задача|NP-полной]]<ref name="NxN_intractable" />. 

* Для [[Ханойская башня|Ханойской башни]] алгоритм Бога существует при любом количестве дисков, но с добавлением дисков число ходов растёт экспоненциально<ref name="rueda_hanoi" />.

== См. также ==
* [[Алгоритм Судного дня]]
* [[Диаметр графа]]
* [[Математика кубика Рубика]]

== Примечания ==
{{примечания|1|refs=

<ref name="cubemir_history">{{cite web
 |url         = http://cubemir.ru/history/history.html
 |title         = История кубика Рубика
 |accessdate         = 2013-07-20
 |archiveurl         = https://www.webcitation.org/6JNKa2nje?url=http://cubemir.ru/history/history.html
 |archivedate         = 2013-09-04
 |deadlink         = yes
 }}</ref>

<ref name="slocum2009">
{{книга
 | автор         = 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
 | ссылка        = http://amzn.com/157912805X
 | год           = 2009
 | страниц       = 142
 | страницы      = 26
 | isbn          = 978-1-57912-805-0
}}
</ref>

<ref name="joyner">{{книга
 |автор       = David Joyner
 |заглавие = Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys
 |ссылка     = http://jhupbooks.press.jhu.edu/ecom/MasterServlet/GetItemDetailsHandler?iN=9780801890123&qty=1&viewMode=3
 |год           = 2008
 |страниц   = 328
 |страницы = 149
}}{{Недоступная ссылка|date=2019-11|bot=InternetArchiveBot }}</ref>

<ref name="cubeexplorer">{{cite web|url=http://kociemba.org/cube.htm|author=Herbert Kociemba|title=Cube Explorer|accessdate=2013-07-27|archiveurl=https://www.webcitation.org/6JNKZHo6Z?url=http://kociemba.org/cube.htm|archivedate=2013-09-04}}</ref>

<ref name="mathworld_gn">{{cite web
| url=https://mathworld.wolfram.com/GodsNumber.html
| author=Weisstein, Eric W.
| title=God's Number
| access-date=2020-05-04
| archive-date=2020-02-21
| archive-url=https://web.archive.org/web/20200221145449/http://mathworld.wolfram.com/GodsNumber.html
| deadlink=no
}}</ref>

<ref name="cube20">
{{cite web
 |url         = http://www.cube20.org
 |title       = God's Number is 20
 |author      = Rokicki, T.; Kociemba, H.; Davidson, M.; and Dethridge, J.
 |accessdate  = 2013-07-19
 |lang        = en
 |archiveurl  = https://www.webcitation.org/6IPSdZhKh?url=http://www.cube20.org/
 |archivedate = 2013-07-26
}}
</ref>

<ref name="cube26">{{cite web
 |url          = http://www.cube20.org/qtm/
 |title        = God's Number is 26 in the Quarter-Turn Metric
 |author       = Rokicki, T. and Davidson, M.
 |accessdate   = 2015-07-02
 |lang         = en
 |archive-date = 2015-07-07
 |archive-url  = https://web.archive.org/web/20150707224122/http://cube20.org/qtm/
 |deadlink     = no
}}</ref>

<ref name="minicube">
{{cite web
 |url         = http://www.jaapsch.net/puzzles/cube2.htm
 |title       = Mini Cube, the 2×2×2 Rubik's Cube
 |author      = Jaap Scherphuis
 |accessdate  = 2013-07-21
 |lang        = en
 |archiveurl  = https://www.webcitation.org/6JNKbczRZ?url=http://www.jaapsch.net/puzzles/cube2.htm
 |archivedate = 2013-09-04
}}
</ref>

<ref name="pyraminx11">
{{cite web
 |url         = http://www.jaapsch.net/puzzles/pyraminx.htm
 |title       = Pyraminx
 |author      = Jaap Scherphuis
 |accessdate  = 2013-07-21
 |lang        = en
 |archiveurl  = https://www.webcitation.org/6JEwJmy3W?url=http://www.jaapsch.net/puzzles/pyraminx.htm
 |archivedate = 2013-08-29
}}
</ref>

<ref name="norskog_3color">{{cite web|url=http://cubezzz.dyndns.org/drupal/?q=node/view/248|publisher=Domain of the Cube Forum|title=Some 3-color cube results|accessdate=2013-07-29|archiveurl=https://www.webcitation.org/6JNKYRdhI?url=http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F248|archivedate=2013-09-04}}</ref>

<ref name="stm80">A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, [http://www.iro.umontreal.ca/~gendron/Pisa/References/BB/Brungger99.pdf The parallel search bench ZRAM and its applications] {{Wayback|url=http://www.iro.umontreal.ca/~gendron/Pisa/References/BB/Brungger99.pdf |date=20171111193526 }}, ''Annals of Operations Research'' '''90''' (1999), pp. 45-63.</ref>

<ref name="mtm43">
{{cite web
 |url         = http://cubezzz.dyndns.org/drupal/?q=node/view/223
 |title       = The Fifteen Puzzle can be solved in 43 "moves"
 |subtitle    = Domain of the Cube Forum
 |author      = Bruce Norskog
 |date        = 2010-08-12
 |accessdate  = 2013-07-20
 |lang        = en
 |archiveurl  = https://www.webcitation.org/6JNKcHV8L?url=http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F223
 |archivedate = 2013-09-04
}}
</ref>

<ref name="NxN_intractable">Daniel Ratner, Manfred K. Warmuth (1986). [http://www.aaai.org/Papers/AAAI/1986/AAAI86-027.pdf «Finding a shortest solution for the N × N extension of the 15-puzzle is intractable»] {{Wayback|url=http://www.aaai.org/Papers/AAAI/1986/AAAI86-027.pdf |date=20120309151834 }}. in ''Proceedings AAAI-86''. National Conference on Artificial Intelligence, 1986. pp. 168—172.</ref>

<ref name="rueda_hanoi">Carlos Rueda, [https://web.archive.org/web/20040605074124/http://yupana.autonoma.edu.co/publicaciones/yupana/003/hanoi/hanoi_eng.html «An optimal solution to the Towers of Hanoi Puzzle»].</ref>

}}

== Ссылки ==
* [https://web.archive.org/web/20091020022021/http://geocities.com/CapeCanaveral/4344/192.html Кубик Рубика: штурм твердыни] (Константин Кноп)

{{Спидкубинг}}

[[Категория:Алгоритмы поиска]]
[[Категория:Математические игры]]
[[Категория:Головоломки]]
[[Категория:Кубик Рубика]]