Найдено необходимое число ходов для решения кубика Рубика

Дэниел Кункле (Daniel Kunkle) и Жене Куперман (Gene Cooperman) из бостонского Северо-восточного университета (Northeastern University) составили программу для суперкомпьютера, которая за 63 часа работы нашла такое минимальное число ходов, которого всегда будет достаточно для сборки кубика Рубика из любого исходного положения.
Найдено необходимое число ходов для решения кубика Рубика
Общее число возможных комбинаций у классического кубика Рубика (3 х 3 х 3 клетки) составляет 43 квинтиллиона (миллиарда миллиардов).

Нахождение всех возможных путей решения для каждого исходного положения — непосильная задача даже для суперкомпьютера. Потому авторы работы придумали специальный алгоритм, позволивший им вплотную подступиться к решению давней проблемы — нахождению "числа Бога" (God’s Number) — так называют наименьшее число ходов за которые, в принципе, возможна сборка кубика из абсолютно любого исходного положения (подразумевается, что Бог всегда знает самый короткий путь).

Дэниел и Жене запрограммировали компьютер на поиск самого короткого решения для одной из 15 тысяч неких промежуточных позиций, установив заранее, что каждую из них можно привести к сборке кубика за некоторое разумное число шагов.

Так выяснилось, что из любой исходной позиции кубика его можно собрать максимум за 29 ходов (а иной раз — гораздо быстрее). То есть — остальные решения, с числом ходов 30, 75 или 200, к примеру, тут уже следует признавать неоптимальными.

При этом большинство исходных позиций потребовало всего-то 26-ти и меньше ходов для своего решения.

Далее авторы работы сосредоточили своё внимание на нескольких позициях, решение которых требовало 27-29 ходов. Число таких проблемных комбинаций было невелико, так что для них суперкомпьютер мог перебрать все варианты стратегии сборки кубика и найти самый короткий. Оказалось, что все трудные позиции также решаются за 26 ходов или быстрее!

Исследователи предсказывают, что "число Бога", в конечном счёте, должно составить 20 с небольшим. Так что в данном вычислении они вплотную приблизились к нему.

Кроме того...
  • Текущие обсуждения статей
Бионическая рука-протез
Телепортация - фантастика или реальность?
Ученые вывели формулу удачи
Смех не лечит раковых больных
Приливы и отливы вызывают сейсмические колебания
Нью-Йорк и Лос-Анджелес уйдут под воду к 2015-му году
Посмотреть весь форум

  • поиск статей на сайте
Введите фразу, слово или часть слова
Темы этого номера
Созданы прототипы квантовых компьютеров
Созданы прототипы квантовых компьютеров Созданы прототипы квантовых компьютеров
Сразу две группы исследователей, одна из Китая, одна из Австралии
Британцы изобрели легко смываемую жвачку
Британцы изобрели легко смываемую жвачку Британцы изобрели легко смываемую жвачку
Легко смываемая жевательная резинка стала реальностью благодаря крупному достижению британских химиков
Древние рукописи можно читать, не открывая
Древние рукописи можно читать, не открывая Древние рукописи можно читать, не открывая
Неразборчивый или невидимый текст в древних рукописях может быть выявлен с помощью источника света
Новая система не позволит водителю заснуть
Новая система не позволит водителю заснуть Новая система не позволит водителю заснуть
15-20% всех автомобильных аварий связано с тем, что водитель засыпает за рулем
Sony предлагает технологию "захвата улыбки"
Sony предлагает технологию "захвата улыбки" Sony предлагает технологию
Японская компания "Sony" анонсировала новую модель цифровой фотокамеры, которая оснащена затвором
Говорящее увеличительное стекло назовёт насекомых по имени
Говорящее увеличительное стекло назовёт насекомых по имени Говорящее увеличительное стекло назовёт насекомых по имени
Общеизвестно, что дети совершенно серьёзно пользуются увеличительными стёклами – для рассматривания насекомых
Для военных создан быстроходный морской робот
Для военных создан быстроходный морской робот Для военных создан быстроходный морской робот
Британская компания QinetiQ обнародовала свою новую разработку: беспилотный разведывательный катер-невидимку Sentry
Создан лазерный симулятор огнетушителя
Создан лазерный симулятор огнетушителя Создан лазерный симулятор огнетушителя
Американская компания BullEx анонсировала выход на рынок симулятора-огнетушителя BullsEye
За формирование первых звезд ответственна темная материя
За формирование первых звезд ответственна темная материя За формирование первых звезд ответственна темная материя
Загадочная темная материя должна была существовать и в ранней Вселенной, более того
Зверинец отправился в космос
Зверинец отправился в космос Зверинец отправился в космос
С Байконура стартовал научный спутник «Фотон-М», сообщает
Апокалипсис через 5 млрд. лет отменяется
Апокалипсис через 5 млрд. лет отменяется Апокалипсис через 5 млрд. лет отменяется
Появилась надежда, что Земля сможет "выжить" после "агонии" Солнца, который традиционно прогнозируют через 5 млрд. лет
На Марсе открыт странный эстуарий
На Марсе открыт странный эстуарий На Марсе открыт странный эстуарий
Загадочные формы рельефа, похожие на высохшее дно эстуария, обнаружил на Марсе европейский спутник Mars Express
Политические взгляды определяются генами
Политические взгляды определяются генами Политические взгляды определяются генами
Аристотель, возможно, был прав, когда говорил, что человек по своей природе политическое животное
Противозачаточная таблетка от рака
Противозачаточная таблетка от рака Противозачаточная таблетка от рака
Согласно одной из крупнейших работ за все время исследования рака
Цветом кожи управляют кератиноциты
Цветом кожи управляют кератиноциты Цветом кожи управляют кератиноциты
Наиболее многочисленные клетки кожи – кератиноциты – обеспечивают ее цвет посредством синтеза факторов
Самое миролюбивое общество в мире
Самое миролюбивое общество в мире Самое миролюбивое общество в мире
Российские ученые обнаружили в ущелье Олдувай самое миролюбивое общество в мире
Северо-Западный проход в Арктике открылся из-за таяния льдов
Северо-Западный проход в Арктике открылся из-за таяния льдов Северо-Западный проход в Арктике открылся из-за таяния льдов
Северо-Западный проход, арктический маршрут, связывающий Атлантику с Тихим океаном, открылся в связи с таянием льдов
Сумчатого волка погубили собаки Динго
Сумчатого волка погубили собаки Динго Сумчатого волка погубили собаки Динго
Ученые проверили гипотезу, согласно которой тасманский сумчатый волк исчез с лица Земли потому
Неандертальцев убила не климатическая катастрофа
Неандертальцев убила не климатическая катастрофа Неандертальцев убила не климатическая катастрофа
Группа палеоэкологов из Университета Лидса (University of Leeds), Великобритания, под руководством Хрониса Тзедакиса (Chronis Tzedakis)
Изобретение зажигалки
Изобретение зажигалки Изобретение зажигалки
Говорят, к изобретению зажигалки приложил руку сам Леонардо да Винчи

 
  • Главные темы / архив
№082текущий номер Технологии
Биоклиматическое здание
    

    

    

    

    

 
  • Человек
  • Планета Земля
  • История изобретений
  • Чёрный ящик
  • Воля случая
  • Технологии
  • Техника
  • Космос
027