Алгоритм кубика Рубика сократили до 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 дней.
ГГ. Что тут скажеш
Даже грубо прикинув - один месяц на довольно интересный проект распределённых вычислений это совсем мизерное время.

[Death]

кто бы сделал.. напиши ему на мыло

[Death]

написал ему
http://cubezzz.homelinux.org/drupal/?q=node/view/117

оригинальный пост если кому интересно.

Two things enabled this jump, actually:

1. Scads of CPU time from Imageworks, and

2. A suggestion from Herbert Kociemba on improving the way the coset solver worked. This suggestion simplified some of the code and lifted the "restriction" that the rubik25 paper discusses.

The amount of CPU time required to prove 20 (my ultimate goal) is still absolutely insane; it's on the order of 3500 core-years. So there's still some work to do to reduce this (or we just wait on Moore's Law).

And there's always the chance some position will actually require more than 20 moves; if I find a 21, suddenly the problem is easier.

[nikelong]

под боинк запиз.дячить этот проект.

Кстати, я когда рыдся по боинках, то там герасим"хоме закрылся потому что проект есть, а цели - нед

Может нам братьям-русичам идейку подкинуть?