Найдено необходимое число ходов для решения кубика Рубика

 


Общее число возможных комбинаций у классического кубика Рубика (3 х 3 х 3 клетки) составляет 43 квинтиллиона (миллиарда миллиардов).

Нахождение всех возможных путей решения для каждого исходного положения — непосильная задача даже для суперкомпьютера. Потому авторы работы придумали специальный алгоритм, позволивший им вплотную подступиться к решению давней проблемы — нахождению "числа Бога" (God's Number) — так называют наименьшее число ходов за которые, в принципе, возможна сборка кубика из абсолютно любого исходного положения (подразумевается, что Бог всегда знает самый короткий путь).

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

Так выяснилось, что из любой исходной позиции кубика его можно собрать максимум за 29 ходов (а иной раз — гораздо быстрее). То есть — остальные решения, с числом ходов 30, 75 или 200, к примеру, тут уже следует признавать неоптимальными.

При этом большинство исходных позиций потребовало всего-то 26-ти и меньше ходов для своего решения.

Далее авторы работы сосредоточили своё внимание на нескольких позициях, решение которых требовало 27-29 ходов. Число таких проблемных комбинаций было невелико, так что для них суперкомпьютер мог перебрать все варианты стратегии сборки кубика и найти самый короткий. Оказалось, что все трудные позиции также решаются за 26 ходов или быстрее!

Исследователи предсказывают, что "число Бога", в конечном счёте, должно составить 20 с небольшим. Так что в данном вычислении они вплотную приблизились к нему.

Свои выкладки соавторы представили на международном симпозиуме по символьным и алгебраическим вычислениям (ISSAC 2007), прошедшем недавно в канадском городе Ватерлоо (Waterloo).


Источник: MEMBRANA.RU