Кубик Рубіка за 20 кроків переклад

Кубик Рубіка за 20 кроків переклад

Кубик Рубіка за 20 кроків переклад

Будь-яка позиція Кубика Рубіка може бути вирішена не більше, ніж за 20 кроків.

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

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

Розумно вважати, що Бог може використовувати більш ефективний алгоритм, який вирішує завдання за найліпший число кроків. Цей алгоритм відомий як «алгоритм Бога». Число кроків в гіршому випадку називається числом Бога.

Зрештою, було показано, що це число — 20.

Після винаходу Кубика Рубика п’ятнадцять років пішло на пошук позиції, яка напевно вирішується за 20 кроків. Через 15 років після цього ми доведемо, що 20 кроків достатньо для будь-якої позиції.

Історія числа Бога

До 1980 року було встановлено, нижня межа — 18, а верхня — ймовірно, близько 80. У таблиці нижче зібрані всі результати:

Як ми це зробили

Як ми впоралися з 43 252 003 274 489 856 000 позицій Кубика Рубика?

  • Ми розділили всі позиції на 2217093120 множин — по 19508428800 позицій у кожному.
  • Ми зменшили число множин для вирішення до 55888296 на основі симетрії і покритті множини.
  • Ми не шукали оптимальне рішення, а тільки рішення з довжиною 20 або менше кроків.
  • Ми написали програму, що знаходить рішення для одного безлічі за 20 секунд.
  • Знадобилося 35 років комп’ютерного часу для пошуку рішень всіх конфігурацій в кожному з 55888296 множин.
  • Ми розбили велике завдання на 2217093120 менших підзадач: в кожну входило по 19,508,428,800 різних позицій. Одна така підзадача легко поміщається в пам’ять сучасного комп’ютера, і цей метод дозволив досить швидко отримати рішення.

    Якщо повертати Кубик Рубіка вліво-вправо або вгору-вниз, то, по суті, нічого не зміниться: число кроків у вирішенні залишиться тим же самим. Замість того, щоб вирішувати всі ці позиції, можна отримати рішення для однієї і поширити його на повернені позиції. Є 24 різних орієнтації в просторі і 2 дзеркальних положення Кубика для кожної позиції, що дозволяє зменшити число розв’язуваних позицій в 48 разів. Якщо використовувати аналогічні міркування і скористатися пошуком завдання «покриття безлічі», то число підзадач зменшується від 2217093120 до 55882296.

    Оптимальне рішення містить достатню кількість кроків, але не більше, ніж треба. Так як вже відома одна позиція, для якої потрібно 20 кроків, то ми можемо не шукати оптимальне рішення для кожної позиції, а тільки рішення в 20-менш кроків. Це багаторазово прискорює задачу.

    Обладнання

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

    Сама важка позііція

    Ми знали протягом 15 років, що є позиції, які вимагає 20 кроків, але ми довели, що ні для однієї позиції і не треба більше.

    Позиції з рішеннями в 20 кроків рідкісні, але їх цілком можливо зустріти в реальності. Ймовірність зустріти таку позицію варіюється від 10 (-9) до 10 (-8). Ми точно не знаємо точну кількість таких позицій.

    Таблиця дає оцінку числа позицій для кожної довжини рішення.

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

    Сподобалася стаття? Поділися нею з друзями!