Русская Википедия:Алгоритм бога

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

Определение

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

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

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

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

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

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

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

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

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

Число Бога

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

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

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

Примеры

Шаблон:Seealso

  • Если разрешены лишь повороты граней на 90 градусов (но не на 180 градусов, которые возможны, но при этом засчитываются за два хода), «число Бога» кубика Рубика равно Шаблон:Ч[8].
  • Число Бога кубика Шаблон:Times равно Шаблон:Ч ходам, если поворот грани на 180° считается за 1 ход, или Шаблон:Ч ходам, если поворот грани на 180° считается за 2 хода. Небольшое (Шаблон:Num) количество конфигураций кубика Шаблон:Times позволило вычислить алгоритм Бога (в виде оптимального решения для каждой конфигурации) ещё в 80-х годах[9].
  • Трёхцветный кубик, противоположные грани которого окрашены одинаково. Число конфигураций трёхцветного кубика равно
<math>2^{11}\cdot 3^7\cdot C_{12}^4\cdot (C_8^4)^2=10\ 863\ 756\ 288\ 000</math>
В марте-апреле 2012 года было установлено, что число Бога трёхцветного кубика равно Шаблон:Ч FTM, Шаблон:Ч QTM или Шаблон:Ч STM (согласно метрике STM, поворот любого среднего слоя также считается за 1 ход)[11].
  • «Пятнашки» могут быть решены в Шаблон:Ч «коротких»[12] или Шаблон:Ч «длинных»[13] ходов в худшем случае (под «короткими» ходами подразумеваются перемещения отдельных костяшек, а под «длинными» — перемещения целых рядов из 1, 2 или 3 костяшек). Для обобщённых пятнашек (с бо́льшим, чем 15, количеством костяшек) задача поиска кратчайшего решения является NP-полной[14].
  • Для Ханойской башни алгоритм Бога существует при любом количестве дисков, но с добавлением дисков число ходов растёт экспоненциально[15].

См. также

Примечания

Шаблон:Примечания

Ссылки

Шаблон:Спидкубинг

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Ошибка цитирования Неверный тег <ref>; для сносок cubemir_history не указан текст
  2. ↑ Ошибка цитирования Неверный тег <ref>; для сносок cubeexplorer не указан текст
  3. ↑ Bigger rubik cube bound Шаблон:Webarchive
  4. ↑ Шаблон:Cite web
  5. ↑ Шаблон:Cite web
  6. ↑ Ошибка цитирования Неверный тег <ref>; для сносок mathworld_gn не указан текст
  7. ↑ Ошибка цитирования Неверный тег <ref>; для сносок cube20 не указан текст
  8. ↑ Ошибка цитирования Неверный тег <ref>; для сносок cube26 не указан текст
  9. ↑ Ошибка цитирования Неверный тег <ref>; для сносок minicube не указан текст
  10. ↑ Ошибка цитирования Неверный тег <ref>; для сносок pyraminx11 не указан текст
  11. ↑ Ошибка цитирования Неверный тег <ref>; для сносок norskog_3color не указан текст
  12. ↑ Ошибка цитирования Неверный тег <ref>; для сносок stm80 не указан текст
  13. ↑ Ошибка цитирования Неверный тег <ref>; для сносок mtm43 не указан текст
  14. ↑ Ошибка цитирования Неверный тег <ref>; для сносок NxN_intractable не указан текст
  15. ↑ Ошибка цитирования Неверный тег <ref>; для сносок rueda_hanoi не указан текст
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Алгоритм_бога&oldid=8940260