Российская Информационная Сеть
English   Контакты
Политика  Общество  Экономика  Деловые  Наука  Hi-Tech  Культура  Шоу-бизнес  Спорт  Происшествия  Криминал  Скандалы  Пикантные  Зарубежные  ИноСМИ
ТОП-дайджест  Хроника  Эксклюзив  Фоторепортажи  Личное мнение  Погода  Комментарии  Поиск  RSS  Интернет-радио  
 Топ 20 сегодня Топ 20 сегодня 
Трамп раскритиковал военную политику КитаяТрамп раскритиковал военную политику Китая
Эш Картер прибыл с визитом в ЯпониюЭш Картер прибыл с визитом в Японию
далее топ дня...
 Фотожурнал: фото-топ за месяц, галерея всех фото Фотожурнал 
 Новости партнеров
 Топ новости разделов сегодня Топ новости разделов 
Трамп раскритиковал военную политику КитаяТрамп раскритиковал военную политику Китая
Производство никеля и кобальта может быть экологичнымПроизводство никеля и кобальта может быть экологичным
В Москве объявили лауреатов премии ГаленаВ Москве объявили лауреатов премии Галена
Морская авиация получила первый арктический Ми-8Морская авиация получила первый арктический Ми-8
В Китае разрабатывают технологию распознавания лицВ Китае разрабатывают технологию распознавания лиц
В аварии на трассе Ханты-Мансийск - Тюмень погибли 12 человекВ аварии на трассе Ханты-Мансийск - Тюмень погибли 12 человек
Город Аль-Каяра задыхается в дымуГород Аль-Каяра задыхается в дыму
Трамп раскритиковал военную политику КитаяТрамп раскритиковал военную политику Китая
Дружба с экс-возлюбленными вызывает психические расстройстваДружба с экс-возлюбленными вызывает психические расстройства
Кит Харингтон сыграет в фильме "Смерть и жизнь Джона Ф. Донована"Кит Харингтон сыграет в фильме "Смерть и жизнь Джона Ф. Донована"
далее...
 Личное мнение Личное мнение 

 Новости о знаменитостях Знаменитости 
Новость: 22 июля 09:00: Родион Газманов устроил "Самый яркий день"Родион Газманов устроил "Самый яркий день"

Новость: 25 августа 18:48: Бывший солист A`Studio запускает новый проектБывший солист A`Studio запускает новый проект


 Заплатим за ваше мнение!
Получайте до 1,5 долларов за каждую заполненную анкету!



 Новости общества Новости общества 
10 августа, 14:54

Кубик Рубика теперь можно "взломать" за 26 ходов

Новости общества: Кубик Рубика теперь можно "взломать" за 26 ходов
Дэниел Канкл - специалист в области вычислительной техники Северо-Восточного университета в г. Бостон, доказал, что 26 ходов достаточно, чтобы собрать кубик Рубика, в каком бы состоянии он ни находился. Это на один ход меньше предыдущего рекорда.

В процессе "взлома" кубика он разработал несколько алгоритмов, которые вполне можно применить для решения таких сложных задач, как составление графиков авиарейсов и расчет укладки структуры белков.

Приблизительно число возможных комбинаций кубика составляет 43 триллиона. Даже суперкомпьютер не сможет проверить все возможные комбинации в поисках самого быстрого решения с любого начального состояния кубика в разумный период времени. Поэтому Канкл и его помощник Джин Куперман (Gene Cooperman) придумали несколько остроумных математических и вычислительных алгоритмов, чтобы сделать эту задачу выполнимой.

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

Затем они взялись за более простую задачу: они начали рассматривать лишь те комбинации, которые можно было решить, применяя только полуобороты - без четверть-оборотов. Оказалось, что таким способом можно собрать около 15 000 из триллиона комбинаций.

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

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

Эти наборы были составлены таким образом, что ряд ходов, превращающий одну комбинацию из набора в одну из специальных комбинаций, также превращал другую комбинацию этого набора в специальную. В итоге у них получилось 1,4 триллиона таких наборов - т.е. им требовалось решить лишь 1,4 триллиона задач, что намного меньше, чем первоначальные 43 триллиона, но все равно - пугающее количество.

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

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

Спустя 63 часа вычислений, суперкомпьютер обнаружил, что для превращения любой случайной комбинации в специальную, которую можно собрать лишь при помощи полуоборотов, требуется не более 16 ходов. А так как эти специальные комбинации решаются не более чем за 13 ходов, получалось, что таким способом любую комбинацию кубика Рубика можно собрать за 29 ходов.

Но для нового рекорда это решение не подходило. В прошлом году Сильвиу Раду из Лундского технологического института в Швеции доказал, что любая комбинация кубика Рубика может быть решена не более чем за 27 ходов. Канкл и Куперман понимали, что для нового рекорда им потребуется исключить три хода.

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

Они представили результаты своей работы 29 июля на Международном симпозиуме по вопросам символьных и алгебраических вычислений в г. Ватерлоо, пров. Онтарио, Канада.

Теперь Канкл и Куперман намереваются снизить количество максимальных ходов до 25. Они полагают, что при помощи своего метода "грубой силы" (brute-force) им удастся перебрать все комбинации, требующие 26 ходов, и найти более быстрое решение.

Даже если это у них получится, место для улучшения еще останется. Большинство исследователей считает, что для решения любой комбинации кубика Рубика достаточно всего лишь 20 ходов, однако, никто этого еще не доказал.
[Читать все комментарии] [Напечатать новость]
http://www.diggreader.ru
  Комментарии к новости 
[Добавить комментарий]

Комментариев к этой новости пока нет. Добавьте первым свой комментарий!
[Добавить комментарий]
 Хроника новостей: Новости общества Хроника новостей 
В Москве объявили лауреатов премии Галена

2 декабря 15:39
Спальные кварталы в Подмосковье останутся без жителей

1 декабря 16:56
В России проходит Всероссийская акция "Стоп ВИЧ/СПИД"

30 ноября 16:55
В Якутии в эксплуатацию ввели сразу 3 котельные

30 ноября 14:00
В Канзасе в парке были обнаружены монстры и Санта-Клаусы

30 ноября 13:19
Активисты ОНФ инициировали прокурорскую проверку недостроев

28 ноября 15:14
В Калининграде 300 моряков Балтийского флота получили квартиры

25 ноября 14:34
В Краснодарском крае открыли 3-уровневую дорожную развязку

24 ноября 16:53
В Приморье жители разрушенного поселка обратились в прокуратуру

24 ноября 15:52
Витамин D не помогает предотвратить болезни

24 ноября 13:02
В Башкирии живому человеку выписали свидетельство о смерти

18 ноября 16:00
Рыбный рынок в Сиэтле стал источником плотоядных бактерий

18 ноября 12:53
Библейская плита была продана за $850 тыс

18 ноября 11:46
В Якутии реконструируют федеральную трассу "Колыма"

17 ноября 16:47
Красноярские хирурги впервые провели операции по пересадке печени и сердца

16 ноября 16:55
На Урале аномальные морозы

15 ноября 14:34
Российские призывники будут питаться в ресторанах

11 ноября 16:55
В Китае найдены останки крылатого динозавра

11 ноября 13:33
В Хибинах открывается туристический сезон

10 ноября 16:50
На центральную Россию обрушились снегопады

10 ноября 15:25
В Минске программист создал роботизированный протез

8 ноября 16:49
На Россию обрушился мощный циклон

8 ноября 14:13
По Красной площади сегодня прошла техника времен ВОВ

7 ноября 17:06
В Ростове-на-Дону простились с великим клоуном Олегом Поповом

7 ноября 15:11
Полиция нашла в сумке женщины детеныша коалы

7 ноября 13:41
Магадан остался без снега

2 ноября 16:52
В Кемеровской области открыли новый железнодорожный вокзал

2 ноября 15:57
В Свердловской области семья пытается выжить в полуразрушенном бараке

2 ноября 15:17
Транспортная прокуратура проверяет свалки бытовых отходов

1 ноября 17:02
Врачи удалили опухоль у 7-месячной девочки

1 ноября 16:06
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25 >> 1856
 Главная новость дня Главная новость дня 
В аварии на трассе Ханты-Мансийск - Тюмень погибли 12 человек В аварии на трассе Ханты-Мансийск - Тюмень погибли 12 человек
 
 Эксклюзив Эксклюзив 
Пора ли продавать акции Apple? Пора ли продавать акции Apple?
 
  Топ новостей Опросы 
 Фоторепортажи: новости с подборкой фотографий Фоторепортажи 
Во время съемок Обитель зла 6 погиб техник
Кенни Уэст выпустил новый альбом
Эльбрус Джанмирзоев попал в смертельное ДТП
Скончался певец Дэвид Боуи
Все участницы Дом-2 идут работать в эскорт-услуги
 Новости партнеров
 Новости дня Новости дня 
 
Новость: В Узбекистане подводят итоги внеочередных президентских выборовВ Узбекистане подводят итоги внеочередных президентских выборов
 
Новость: Пожар в ночном клубе Окленда унес жизни 33 человекПожар в ночном клубе Окленда унес жизни 33 человек
 
Новость: В аварии на трассе Ханты-Мансийск - Тюмень погибли 12 человекВ аварии на трассе Ханты-Мансийск - Тюмень погибли 12 человек
 
Новость: Премьер-министр Италии Ренци покидает постПремьер-министр Италии Ренци покидает пост
 
Новость: Победу на президентских выборах в Австрии одержал Александр Ван дер БелленПобеду на президентских выборах в Австрии одержал Александр Ван дер Беллен
 
Новость: Кит Харингтон сыграет в фильме "Смерть и жизнь Джона Ф. Донована"Кит Харингтон сыграет в фильме "Смерть и жизнь Джона Ф. Донована"
 
  Copyright © RIN 2000-
* Обратная связь
Контактная информация  
Политика  Общество  Экономика  Деловые  Наука  Hi-Tech  Культура  Шоу-бизнес  Спорт  Происшествия  Криминал  Скандалы  Пикантные  Зарубежные  ИноСМИ