Pull to refresh

Кубик Рубика за 20 шагов

Abnormal programming *
Translation
Original author: Tomas Rokicki
Любая позиция Кубика Рубика может быть решена не более, чем за 20 шагов.

Несколько лет назад было доказано, что для Кубика Рубика есть решение за 23 хода. Теперь это число сократилось до 20. Чтобы это сделать, потребовалось 35 (тридцать пять) лет компьютерного времени, пожертвованного Гуглом.


Каждый блок решения использовал свой алгоритм — последовательность шагов для достижения нужной конфигурации. Например, один алгоритм предназначался для решения верхней грани, а другой — для позиционирования средних краев. Есть множество различных алгоритмов, различающихся по степени сложности и количеству требуемых шагов, но те, которые может запомнить человек, обычно требуют больше 40 шагов.

Разумно полагать, что Бог может использовать более эффективный алгоритм, который решает задачу за наикратчайшее число шагов. Этот алгоритм известен как “алгоритм Бога”. Число шагов в худшем случае называется числом Бога. В конце концов, было показано, что это число — 20.

После изобретения Кубика Рубика пятнадцать лет ушло на поиск позиции, которая наверняка решается за 20 шагов. Через 15 лет после этого мы докажем, что 20 шагов достаточно для любой позиции.

История числа Бога


К 1980 году было установлено, нижняя граница — 18, а верхняя — вероятно, около 80. В таблице ниже собраны все результаты:


Как мы это сделали



Как мы справились с 43 252 003 274 489 856 000 позициями Кубика Рубика?
  • Мы разделили все позиции на 2 217 093 120 множеств — по 19 508 428 800 позиций в каждом.
  • Мы уменьшили число множеств для решения до 55 888 296 на основе симметрии и покрытии множества.
  • Мы не искали оптимальное решение, а только решения с длиной 20 или менее шагов.
  • Мы написали программу, находящее решение для одного множества за 20 секунд.
  • Потребовалось 35 лет компьютерного времени для поиска решений всех конфигураций в каждом из 55 888 296 множеств.


Деление пространства позиций


Мы разбили большую задачу на 2 217 093 120 меньших подзадач: в каждую входило по 19,508,428,800 различных позиций. Одна такая подзадача легко помещается в память современного компьютера, и этот метод позволил достаточно быстро получить решение.

Симметрия


Если повертеть Кубик Рубика влево-вправо или вверх-вниз, то, по сути, ничего не изменится: число шагов в решении останется тем же самым. Вместо того, чтобы решать все эти позиции, можно получить решение для одной и распространить его на повернутые позиции. Есть 24 различных ориентации в пространстве и 2 зеркальных положения Кубика для каждой позиции, что позволяет уменьшить число решаемых позиций в 48 раз. Если использовать аналогичные рассуждения и воспользоваться поиском задачи “покрытия множества”, то число подзадач уменьшается от 2 217 093 120 до 55 882 296.

Хорошие и оптимальные решения


Оптимальное решение содержит достаточное количество шагов, но не больше, чем надо. Так как уже известна одна позиция, для которой требуется 20 шагов, то мы можем не искать оптимальное решение для каждой позиции, а только решения в 20 или менее шагов. Это многократно убыстряет задачу.

Оборудование


У нас была возможность решить 55 882 296 подзадач на мощностях Гугла и выполнить все вычисления за несколько недель. Гугл не раскрывает характеристики компьютеров, но было затрачено 1.1 миллиард секунд компьютерного времени (Intel Nehalem, four-core, 2.8GHz) на выполнение расчетов.

Самая трудная позииция



Мы знали в течении 15 лет, что есть позиции, которые требует 20 шагов, но мы доказали, что ни для одной позиции и не надо больше.

Позиции с решениями в 20 шагов редки, но их вполне возможно встретить в реальности. Вероятность встретить такую позицию варьируется от 10^(-9) до 10^(-8). Мы точно не знаем точное количество таких позиций. Таблица дает оценку числа позиций для каждой длины решения.


Для длин от 16 и больше, числа являются примерными. Наши исследования подтвердили все первоначальные данные до 14 строки включительно, а 15 строка — новый результат. На 11 августа мы обнаружили 12 миллионов позиций с длиной решения 20. Эта позиция была самой сложной для наших программ:

Tags:
Hubs:
Total votes 144: ↑134 and ↓10 +124
Views 304K
Comments Comments 94