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

 Новости о знаменитостях Знаменитости 
Новость: 16 июля 18:13: Новости проекта "Дом-2": один из участников расплакался из-за изменыНовости проекта "Дом-2": один из участников расплакался из-за измены

Новость: 16 июля 18:13: Новости проекта "Дом-2": один из участников расплакался из-за изменыЛимузин Ельцина выставлен на продажу


 Заплатим за ваше мнение!
Получайте до 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
  Комментарии к новости 
[Добавить комментарий]

Комментариев к этой новости пока нет. Добавьте первым свой комментарий!
[Добавить комментарий]
 Хроника новостей: Новости общества Хроника новостей 
Глава Минобра считает что Россия может гордиться своей системой образования

8 ноября 11:19
Увеличен штраф за непропуск пешеходов

31 октября 10:19
Круговые перекрёстки теперь надо проезжать по новому

30 октября 18:23
Путин дал команду на старт ракет

27 октября 10:22
Путин принял российскую команду WordSkills

25 октября 10:27
Армия США пристально наблюдает за строительством Крымского моста

24 октября 09:22
Неожиданные преимущества регулярного потребления горячей питьевой воды

20 октября 19:06
Наконец-то граждане смогут стами штрафовать нарушителей ПДД

20 октября 09:03
Инспектора ГИБДД перестанут отнимать права у водителей

18 октября 12:50
Депутат Госдумы предлагает отменить новогодние каникулы

18 октября 12:41
McDonald`s испытывает необычный способ заставить посетителей общаться между собой

17 октября 12:56
Курильщикам запретят курить у подъездов

17 октября 09:39
Непропуск пешехода будет стоить водителю 2500 руб/

11 октября 11:06
Роскомнадзор заблокировал крупнейший сайт c онлайн фильмами

11 октября 10:49
Урок шахмат введут в российских школах

10 октября 15:14
Развеян миф о влиянии спиннеров на детскую психику

3 октября 07:59
Ликвидированы командиры боевиков, напавших на наших военных

27 сентября 09:57
Почему спать лучше голым

26 сентября 11:24
МВД будет штрафовать по видео нарушения ПДД

25 сентября 16:22
Путин неожиданно посетил офис Яндекса

22 сентября 10:16
Синоптики прогнозируют теплую погоду до начала октября

21 сентября 08:44
Ренат Акчурин: российская кардиология на уровне европейской

20 сентября 09:33
Российские программисты взяли три золотых медали на олимпиаде

19 сентября 17:10
Как стать хорошим собеседником

18 сентября 10:19
Корабли ВМС Китая зашли на российскую морскую базу

18 сентября 08:33
11 российских ВУЗов вошли в мировой рейтинг

14 сентября 09:46
Путин высказал претензии губернатору Владимирской области

13 сентября 10:03
Продолжительность жизни Россиян удлинилась на полгода

12 сентября 08:56
10 сентября в России прошли выборы

11 сентября 16:11
Парень 9 лет каждый день делал селфи и сделал из этого видео

9 сентября 16:07
 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 >> 1863
 Главная новость дня Главная новость дня 
Выжившие в ДТП в Марий-Эл находятся в тяжёлом состоянии Выжившие в ДТП в Марий-Эл находятся в тяжёлом состоянии
 
 Эксклюзив Эксклюзив 
Пора ли продавать акции Apple? Пора ли продавать акции Apple?
 
  Топ новостей Опросы 
 Фоторепортажи: новости с подборкой фотографий Фоторепортажи 
Егор Холявин рискует своей жизнью ради пластики
Шестилетняя модель выросла и стала сенсацией на Неделе Моды в Нью-Йорке
Катя Жужа покидает Сейшельские острова
Николас Кейдж сломал ногу во время съемок
Шестилетняя модель выросла и стала сенсацией на Неделе Моды в Нью-Йорке...
 Новости партнеров
 Новости дня Новости дня 
 
Новость: Девочка 3-х лет, выжившая в авиакатастрофе, уже катается по больницеДевочка 3-х лет, выжившая в авиакатастрофе, уже катается по больнице
 
Новость: Выжившие в ДТП в Марий-Эл находятся в тяжёлом состоянииВыжившие в ДТП в Марий-Эл находятся в тяжёлом состоянии
 
  Copyright © RIN 2000-
* Обратная связь
Контактная информация  
Политика  Общество  Экономика  Деловые  Наука  Hi-Tech  Культура  Шоу-бизнес  Спорт  Происшествия  Криминал  Скандалы  Пикантные  Зарубежные  ИноСМИ