Существует множество алгоритмов, которые собирают кубик Рубика — более или менее эффективно. Те из них, которые может выучить и применять средний смертный, обычно требуют более 40 ходов. Алгоритмом бога называют алгоритм, использующий для сборки любой начальной конфигурации минимальное количество ходов (термин связан с концепцией всеведения и применяется также для ряда других механических и логических задач). Число бога, соответственно, определяют как количество ходов, требующееся этому алгоритму в худшем случае. Так вот, для кубика Рубика это число равно 20.
Сам кубик был придуман в 1974 году. Теоретические исследования кубика сосредотачивались на оценке нижней и верхней границ максимального количества ходов для решения кубика.
К 1980 году нижняя граница была оценена как 18: существенно разных последовательностей ходов длиной 17 и менее оказалось меньше, чем конфигураций кубика. Эта оценка продержалась 15 лет — до 1995 года, когда Майкл Рейд (Michael Reid) доказал, что для конфигурации «superflip» (правильные уголки и перепутанные середины сторон) нужно ровно 20 ходов.
Тем временем оценка верхней границы снижалась чаще, но медленнее: в 1981 году она равнялась 52, в 1995 тот же Майкл Рейд получил величину 29, в 2008 Томаш Рокицки (Tomas Rokicki) уменьшил ее до 25-23-22 (оценка в 23 хода даже удостоилась статьи на Хабре :-)), и вот наконец в июле 2010 тот же Томаш Рокицки вместе с Morley Davidson, John Dethridge и Herbert Kociemba получили окончательный результат — 20 ходов.
Всего существует 8! * 37 * 12! * 210 = 43,252,003,274,489,856,000 ~ 4.3 * 1019 конфигураций кубика. С использованием симметрий и покрытия множеств они свелись к 55,882,296 существенно разным конфигурациям, которые пришлось честно решать. Для упрощения задачи для каждой конфигурации искали не оптимальное решение (оно же решение бога), а решение за 20 или менее ходов.
Наконец, конфигурации были распределены между множеством компьютеров Гугл, и вычисления завершились всего за несколько недель. На хорошем компьютере (Intel Nehalem, four-core, 2.8GHz) эти вычисления заняли бы 1.1 миллиард секунд, или 35 лет.
Хотя кубик Рубика многие критикуют за отсутствие практической ценности, полученный результат все-таки интересен — хотя бы своей окончательностью, поскольку ни верхняя, ни нижняя граница не могут быть сдвинуты дальше. Широко известная (а вы сами увлекались кубиком?) открытая задача решена, можно поздравить иссдедователей и переключиться на что-то другое.
Забавно, что многие люди, узнающие об этом результате, укоризненно высказываются в том плане, что Гуглу некуда девать вычислительные мощности, которыми можно решить проблему рака. Ну, если кто-то действительно может найти лечение рака всего лишь за 35 CPU-лет (и несколько лет своей работы), я думаю, Гугл с удовольствием ему их выделит.
1. God's Number is 20
2. Кубик Рубика в Википедии
3. Обсуждение новости на reddit
Немного истории
Сам кубик был придуман в 1974 году. Теоретические исследования кубика сосредотачивались на оценке нижней и верхней границ максимального количества ходов для решения кубика.
К 1980 году нижняя граница была оценена как 18: существенно разных последовательностей ходов длиной 17 и менее оказалось меньше, чем конфигураций кубика. Эта оценка продержалась 15 лет — до 1995 года, когда Майкл Рейд (Michael Reid) доказал, что для конфигурации «superflip» (правильные уголки и перепутанные середины сторон) нужно ровно 20 ходов.
Тем временем оценка верхней границы снижалась чаще, но медленнее: в 1981 году она равнялась 52, в 1995 тот же Майкл Рейд получил величину 29, в 2008 Томаш Рокицки (Tomas Rokicki) уменьшил ее до 25-23-22 (оценка в 23 хода даже удостоилась статьи на Хабре :-)), и вот наконец в июле 2010 тот же Томаш Рокицки вместе с Morley Davidson, John Dethridge и Herbert Kociemba получили окончательный результат — 20 ходов.
Как?
Всего существует 8! * 37 * 12! * 210 = 43,252,003,274,489,856,000 ~ 4.3 * 1019 конфигураций кубика. С использованием симметрий и покрытия множеств они свелись к 55,882,296 существенно разным конфигурациям, которые пришлось честно решать. Для упрощения задачи для каждой конфигурации искали не оптимальное решение (оно же решение бога), а решение за 20 или менее ходов.
Наконец, конфигурации были распределены между множеством компьютеров Гугл, и вычисления завершились всего за несколько недель. На хорошем компьютере (Intel Nehalem, four-core, 2.8GHz) эти вычисления заняли бы 1.1 миллиард секунд, или 35 лет.
Реакция
Хотя кубик Рубика многие критикуют за отсутствие практической ценности, полученный результат все-таки интересен — хотя бы своей окончательностью, поскольку ни верхняя, ни нижняя граница не могут быть сдвинуты дальше. Широко известная (а вы сами увлекались кубиком?) открытая задача решена, можно поздравить иссдедователей и переключиться на что-то другое.
Забавно, что многие люди, узнающие об этом результате, укоризненно высказываются в том плане, что Гуглу некуда девать вычислительные мощности, которыми можно решить проблему рака. Ну, если кто-то действительно может найти лечение рака всего лишь за 35 CPU-лет (и несколько лет своей работы), я думаю, Гугл с удовольствием ему их выделит.
Источники
1. God's Number is 20
2. Кубик Рубика в Википедии
3. Обсуждение новости на reddit
