Приветствую Вас, уважаемые Читатели! Сегодня поговорим о том, что представляет из себя одно универсальное математическое понятие — "алгоритм Бога". Вы поймете, когда о нем говорят, и, что строго говоря, в нём нет ничего божественного. Однако, поехали!
Источник: https://images.ru.prom.st/522774454_w640_h640_skorostnoj-kubik-rubika.jpg
Автором определения является до боли нам знакомый математик Джон Конвей. По его определению алгоритмом Бога является любой набор действий, приводящий систему из одного состояния в другое за минимальное количество шагов.
Алгоритм Бога существует для любой головоломки, которую можно решить за конечно количество шагов, и, конечно, наиболее известной такой головоломкой является кубик Рубика.
Среднее количество ходов для сборки кубика Рубика составляет около 50-200 ходов, в то время как алгоритм Бога позволяет собрать кубик за 20 ходов в независимости от первоначальной конфигурации!
Существует, кстати приложение, которое называется Mistr Kostky, позволяющее с использованием дополненной реальности повторить алгоритм Бога любителю головоломки.
За один ход принимается один поворот грани. Источник: https://cdn-images-1.medium.com/max/1024/1*nLOIdxOAkjHBdFezoSGP6g.gif
Еще раз обращаю внимание, что собрать кубик можно из за число шагов меньшее 20, но сделать это из любого положения минимум за 20.
Создание алгоритма Бога для любой головоломки связано с нахождением пути на графе, вершинами которого являются различные состояния головоломки. При этом ребра графа являются допустимыми переходами между ними.
Например, представьте, что у некоторой головоломки есть 12 состояний, а решить головоломку — значит перевести её из состояния Х. Тогда числом Бога будет минимальное количество ходов, которое из любого из состояний позволит перейти в Х.
Представленную на рисунке задачи еще можно решить простым перебором. По моим подсчетам число Бога для такой головоломки равно 4
Возможные пути по ребрам на графе
Легко, не правда ли? А теперь представьте, что для кубика Рубика число таких вершин — 43 252 003 274 489 860 000, и неудивительно что для него алгоритм Бога был найден лишь в 2010 году.
Для кубика 2х2х2 количество состояний равно 3674160, а число Бога — 11. Это удалось вычислить еще в 80-х годах двадцатого века.
Источник: https://aidexx.ru/wp-content/uploads/www.aidexx.ru-74-91511-0.jpg
Вычисление алгоритма Бога для кубика 4х4х4 для современных компьютеров пока что является непосильной задачей.
Алгоритм Бога существует также для Ханойской башни, пирамидки Мефферта и даже для любимой народами всего мира головоломке о Волке, Козе и капусте. Кстати, чему равно число Бога в последнем случае? Спасибо за внимание!
