|
Главная :: Архив статей :: Поиск :: Ссылки |
Наши друзья Наша кнопка Партнеры
|
В поисках числа Бога
Нахождение всех возможных путей решения для каждого исходного положения - непосильная задача даже для суперкомпьютера. Потому авторы работы придумали специальный алгоритм, позволивший им вплотную подступиться к решению давней проблемы - нахождению "числа Бога" - так называют наименьшее число ходов за которые, в принципе, возможна сборка кубика из абсолютно любого исходного положения (подразумевается, что Бог всегда знает самый короткий путь). Дэниел и Жене запрограммировали компьютер на поиск самого короткого решения для одной из 15 тыс. неких промежуточных позиций, установив заранее, что каждую из них можно привести к сборке кубика за некоторое разумное число шагов. Так выяснилось, что из любой исходной позиции кубика его можно собрать максимум за 29 ходов (а иной раз - гораздо быстрее). То есть - остальные решения, с числом ходов 30, 75 или 200, к примеру, тут уже следует признавать неоптимальными. При этом большинство исходных позиций потребовало всего-то 26-ти и меньше ходов для своего решения. Далее авторы работы сосредоточили своё внимание на нескольких позициях, решение которых требовало 27-29 ходов. Число таких проблемных комбинаций было невелико, так что для них суперкомпьютер мог перебрать все варианты стратегии сборки кубика и найти самый короткий. Оказалось, что все трудные позиции также решаются за 26 ходов или быстрее!
Исследователи предсказывают, что "число Бога", в конечном счёте, должно составить 20 с небольшим. Так что в данном вычислении они вплотную приблизились к нему. Свои выкладки соавторы представили на международном симпозиуме по символьным и алгебраическим вычислениям (ISSAC 2007), прошедшем недавно в канадском городе Ватерлоо, отмечает журнал "Мембрана". |
|
Главная :: Архив статей :: Поиск ::