Введение

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

Определение

Понятие относится к головоломкам, которые могут принимать конечное количество "конфигураций", с относительно небольшим, хорошо определенным арсеналом "движений", которые могут применяться к конфигурациям, а затем привести к новой конфигурации. Решение головоломки означает достижение назначенной "окончательной конфигурации", сингулярной конфигурации или одной из коллекции конфигураций. Для решения головоломки применяется последовательность движений, начиная с некоторой произвольной начальной конфигурации.

Решение

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

Примеры

Известные головоломки, соответствующие этому описанию, - это механические головоломки, такие как кубик Рубика, Башня Ханой и головоломка 15. Также рассматривается игра в пасьянс с одним человеком, а также многие логические головоломки, такие как проблема миссионеров и каннибалов. У них есть общее, что они могут быть математически смоделированы как направленный график, в котором конфигурации являются вершинами, а движения - дугами.

n-пазлы

Загадка "Пятнадцать" может быть решена в 80 движениях с одной плитой или в 43 движениях с несколькими плитками в худшем случае. Для его обобщения в головоломке n задача поиска оптимального решения NP-трудна, поэтому неизвестно, существует ли практический алгоритм Бога.

Башни Ханоя

Для головоломки "Турмы Ханоя" алгоритм Бога известен для любого количества дисков. Количество движений увеличивается экспоненциально с количеством дисков .

Кубик Рубика

Алгоритм определения минимального количества ходов для решения кубика Рубика был опубликован в 1997 году Ричардом Корфом. Хотя с 1995 года было известно, что 20 - это нижняя граница количества ходов для решения в худшем случае, Том Рокики доказал в 2010 году, что ни одна конфигурация не требует более 20 ходов. Таким образом, 20 является резкой верхней границей длины оптимальных решений. Математик Дэвид Сингмастер "неосторожно предположил", что в 1980 году это число составит 20.

Нерешенные игры

Некоторые хорошо известные игры с очень ограниченным набором простых, хорошо определенных правил и ходов, тем не менее, никогда не имели своего божественного алгоритма для выигрышной стратегии. Примерами являются настольные игры шахматы и Го. В обеих играх с каждым ходом быстро увеличивается количество позиций. Общее количество всех возможных позиций, примерно 5×1044 для шахмат и 10180 (на доске 19×19) для го, слишком велико, чтобы разрешить решение грубой силы с помощью современных вычислительных технологий (сравните теперь решенный, с большим трудом, куб Рубика только примерно в 4,3 позиции). Следовательно, невозможно определить алгоритм Бога для этих игр с помощью грубой силы. Хотя были созданы шахматные компьютеры, способные победить даже лучших игроков, они не рассчитывают игру до конца. Например, Deep Blue искала только 11 ходов вперед (считая ход каждого игрока как два хода), сократив пространство поиска всего до 1017. После этого он оценивал каждую позицию на пользу в соответствии с правилами, полученными из человеческой игры и опыта. Даже эта стратегия не возможна с Го. Кроме того, что существует огромное количество позиций для оценки, никто до сих пор не смог успешно построить набор простых правил для оценки силы позиции Го, как это было сделано для шахмат, хотя нейронные сети, обученные с помощью обучения с помощью усиления, могут дать оценки позиции, которые превышают человеческие способности. Алгоритмы оценки склонны к элементарным ошибкам, поэтому даже для ограниченного взгляда вперед с целью найти самую сильную промежуточную позицию, алгоритм Бога не был возможен для Го. С другой стороны, шахматы (шашки) давно подозреваются в том, что их "игры" проводятся их профессиональными игроками. В 2007 году Schaeffer et al. доказал это, вычислив базу данных всех позиций с десятью или меньше фигур, предоставив божий алгоритм для всех финальных игр в шашки, который был использован, чтобы доказать, что все идеально сыгранные игры в шашки заканчиваются вничью. Однако чертежи с 5 позициями и даже меньше, 3,9, в базе данных, гораздо легче задать задачу того же порядка, что и куб Рубика. Величина множества позиций головоломки не полностью определяет, возможен ли божий алгоритм. Уже решенная головоломка Башни Ханой может иметь произвольное количество частей, и количество позиций увеличивается экспоненциально, как тем не менее, алгоритм решения применим к любой проблеме размера, с масштабированием времени выполнения как .