Суперкомпьютеры улучшили рекорд решения головоломки «кубик Рубика»: теперь всего 26 ходов
22 августа 2007 года
Благодаря мощностям современных суперкомпьютеров люди вплотную приблизились к самому быстрому решению головоломки «кубик Рубика». Последнее исследование, проведенные двумя учеными из Северо-Восточного университета в Бостоне, показало, что головоломку можно решить за 26 ходов из любого положения. Ранее был известен способ решения головоломки за 29 ходов, сообщает 3DNews (Архивная копия от 28 декабря 2007 на Wayback Machine).
Найти решение головоломки, даже при условии использования суперкомпьютера, непросто, поскольку требуется перебрать около 43 триллиона (это 10 в восемнадцатой степени) комбинаций.
Поэтому ученые использовали несколько математических уловок, чтобы свести число комбинаций к минимуму. Сначала они уменьшили количество комбинаций до одного триллиона, за счет того, что сделали такое предположение: если на каждой стороне куба находятся элементы одного цвета, то головоломка решена, вне зависимости от того, на какой стороне какой цвет используется. Таким образом, можно считать идентичными те комбинации, которые отличаются друг от друга только двумя переставленными цветами.
Затем задача была упрощена: из всех комбинаций были выбраны только те, которые можно решить, поворачивая элементы на 180 градусов, то есть, в полоборота, не используя повороты на четверть оборота. Таким образом, было отобрано 15 тысяч комбинаций из триллиона. Это - сравнительно немного, и обычный компьютер может найти самый быстрый способ решения каждой из таких комбинаций за один день. Дав компьютеру задание решить все эти комбинации, ученые выяснили, что все они могут быть решены за 13 ходов или быстрее.
Затем ученые посчитали, сколько ходов требуется для того, чтобы из любой случайной комбинации перейти к одной из 15 тысяч решенных комбинаций. Для этого все комбинации были классифицированы по группам. В рамках одной группы все комбинации могли быть преобразованы одна в другую с использованием только полуоборота. Таким образом, число комбинаций было сокращено до 1,4 миллиарда. Все эти комбинации были решены, и было установлено, что для того, чтобы добиться перехода от любой из таких комбинаций до одной из 15 тысяч решенных комбинаций требуется не более 16 ходов. То есть, на решение самого сложного задания требуется не более 29 ходов.
Стремясь улучшить этот показатель, ученые отобрали 80 миллионов комбинаций, которые были решены компьютером более, чем за 26 ходов и, поскольку такое число комбинаций не является очень большим, смогли дать компьютеру задание перебрать все возможные способы решения. Для всех 80 миллионов сложных комбинаций было найдено решение за 26 ходов.
Несмотря на то, что ученым удалось улучшить предыдущий результат на три хода, решение не является окончательным. Большинство исследователей полагают, что решить головоломку можно за 20 ходов, хотя пока что доказать это никому не удалось.
Источники
править
Любой участник может оформить статью: добавить иллюстрации, викифицировать, заполнить шаблоны и добавить категории.
Любой редактор может снять этот шаблон после оформления и проверки.
Комментарии
Если вы хотите сообщить о проблеме в статье (например, фактическая ошибка и т. д.), пожалуйста, используйте обычную страницу обсуждения.
Комментарии на этой странице могут не соответствовать политике нейтральной точки зрения, однако, пожалуйста, придерживайтесь темы и попытайтесь избежать брани, оскорбительных или подстрекательных комментариев. Попробуйте написать такие комментарии, которые заставят задуматься, будут проницательными или спорными. Цивилизованная дискуссия и вежливый спор делают страницу комментариев дружелюбным местом. Пожалуйста, подумайте об этом.
Несколько советов по оформлению реплик:
- Новые темы начинайте, пожалуйста, снизу.
- Используйте символ звёздочки «*» в начале строки для начала новой темы. Далее пишите свой текст.
- Для ответа в начале строки укажите на одну звёздочку больше, чем в предыдущей реплике.
- Пожалуйста, подписывайте все свои сообщения, используя четыре тильды (~~~~). При предварительном просмотре и сохранении они будут автоматически заменены на ваше имя и дату.
Обращаем ваше внимание, что комментарии не предназначены для размещения ссылок на внешние ресурсы не по теме статьи, которые могут быть удалены или скрыты любым участником. Тем не менее, на странице комментариев вы можете сообщить о статьях в СМИ, которые ссылаются на эту заметку, а также о её обсуждении на сторонних ресурсах.
