ПОПУЛЯРНЫЕ НОВОСТИ

 Фото: Инопланетяне в открытую изучают МКС
 Фото: На Марсе оказалась голова загадочной скульптуры
 Фото: В России нашли оккультный нацистский сундук с останками инопланетян
 Фото: В Словакии с неба слышится зловещий рев
 Фото: Странный НЛО замечен сразу же после грозы

НОВОСТИ СМИ

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

Интересные новости / Разные интересные новости
25.08.2007 79

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

Общее число возможных комбинаций у классического кубика Рубика (3 х 3 х 3 клетки) составляет 43 квинтиллиона (миллиарда миллиардов).

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

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

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

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

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



Не зря, значит, нас удивляют рекорды — читайте, к примеру, о 11-секундной сборке кубика.

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

Свои выкладки соавторы представили на международном симпозиуме по символьным и алгебраическим вычислениям (ISSAC 2007), прошедшем недавно в канадском городе Ватерлоо (Waterloo).


 

 Источник: www.membrana.ru

Комментарии отражают мнения их авторов, и не обязательно точку зрения интернет - портала esoreiter.ru. Просим посетителей портала воздержаться от оскорблений, ругани и вульгарных выражений.

Интернет - портал esoreiter.ru оставляет за собой право удалять комментарии без предварительного уведомления и/или предыдущих объяснений.

Минидом для путешествий




НОВОСТИ СМИ

ФОТО ДНЯ

И такое бывает...

ГОРОСКОП НА СЕГОДНЯ

21.03 - 20.04
24.09 - 23.10
21.04 - 20.05
24.10 - 22.11
21.05 - 21.06
23.11 - 21.12
22.06 - 22.07
22.12 - 20.01
23.07 - 23.08
21.01 - 20.02
24.08 - 23.09
21.02 - 20.03
2003-2016 "Факты о невероятном"

Материалы данного сайта предназначены для лиц 18 лет и старше (18+)

Авторские права на материалы, размещенные на сайте, принадлежат авторам статей. Все права защищены и охраняются законом РФ. При использовании материалов с сайта ссылка на первоисточник обязательна. Если вы считаете, что публикация того или иного материала на нашем сайте нарушает законные права правообладателя, свяжитесь с нами.

Рейтинг@Mail.ru