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

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

Определение

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

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

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

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

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

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