Алгоритм кубика Рубика сократили до 23 ходов, это акуенно !!!11111 Налаштування

[ReMMeR]

Максимальное количество ходов, которое требуется для сбора кубика Рубика, сокращено до двадцати трёх. Эту математическую задачу решил стенфордский выпускник Томаш Рокицки. Разработанная им стратегия была запущена на вычислительной станции, которая подтвердила правильность расчётов.

Рокицки применил оригинальный подход. Вместо анализа отдельных ходов он взял в расчёт форму кубика и разбил её на набор его состояний. Всего получилось 2 млрд состояний (sets) с 20 млрд элементов в каждом. В этой концепции ходы рассматриваются как пары «связанных состояний» (cosets). Рокицки доказал, что большое количество состояний на самом деле повторяют друг друга и поэтому могут быть проигнорированы. Но даже после оптимизации для расчёта всей модели требуются очень большие вычислительные ресурсы. Предыдущий рекорд (25 ходов) потребовал 1500 часов на машине с процессором и Q6600 (1,6 ГГц) и 8 ГБ оперативной памяти. Сейчас Рокицки позаимствовал 7,8 ядро-лет вычислений на более мощном кластере в известной киностудии Sony Pictures Imageworks (вычисления выполнялись во время простоя на тех же машинах, где просчитывались спецэффекты «Человека-паука 3» и мультика «Лови волну»): всего было проанализировано более 200 тыс. связанных состояний.

Теоретическая работа Рокицки предполагает, что оптимальное решение может быть в 22 хода или даже в 21 ход, но для проверки этого требуются дополнительные вычислительные ресурсы. Так, для доказательства решения в 22 хода требуется примерно в пять-семь раз больше машинного времени: нужно просчитать от 1 млн до 1,5 млн связанных состояний.

Доказательство решения в 21 ход пока выглядит фантастическим, но оно вполне соответствует выкладкам математиков-теоретиков, которые посвятили свою карьеру решению этой задачи. Они предполагают, что минимальное количество ходов находится где-то в начале третьего десятка.




============= Добавлю от себя.


Как мне на ухо шепчут Великие Умы, достаточно было по идее того же Стенфорда обратится к технологии распределённых вычислений, и, я думаю, он Очень быстро набрал бы требуемых ему 8 ядро-лет.
Если прикинуть затраты на раздачу заданий, и неравномерность мощности процессоров то предположим что нужно взять 16 ядро-лет.

Пусть он наберёт 100 добровольцев. У каждого в среднем 2 компьютера. У каждого в среднем полтора ядра.
Имеем при мизерной раскрутке - 300 ядер.

16 * 356 (дней) / 300 (ядер)

На глаз прикидывается цифра в 16 дней.
ГГ. Что тут скажеш
Даже грубо прикинув - один месяц на довольно интересный проект распределённых вычислений это совсем мизерное время.