Алгоритм Бога и число Бога

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

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

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

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

Слушать онлайн Эффект Стаховского - Кубик Рубика:

 

One thought on “Алгоритм Бога и число Бога

  1. Pingback: Во Вселенной все уже есть или как увидеть себя » RikoNw

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.