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

 Новости о знаменитостях Знаменитости 
Новость: 25 августа 09:35: Новый пляжный хитНовый пляжный хит

Новость: 29 июля 16:01: Звездная Coca-Cola - самый яркий летний хит на Europa Plus LiveЗвездная Coca-Cola - самый яркий летний хит на Europa Plus Live


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

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

17 апреля 12:04
Глава МЧС извинился перед родителями детей, погибших в "Зимней вишне"

2 апреля 12:04
Путин принял отставку Тулеева

1 апреля 10:04
Титов рассказал, о чем Путин говорил с кандидатами в президенты

19 марта 20:04
Путин призвал кандидатов в президенты к диалогу

19 марта 18:04
Посольство России пообещало обеспечить работу избирательных участков на Украине

17 марта 02:04
В Москве прощаются с Олегом Табаковым

15 марта 10:04
Собчак рассказала, зачем хотела поехать в Крым

13 марта 04:04
Путин подписал закон о повышении МРОТ

7 марта 17:04
Заключить под стражу предпринимателей теперь станет сложнее.

7 марта 08:00
В ДНР и ЛНР издали приказы о соблюдении "абсолютного перемирия" с 5 марта

4 марта 14:04
НАК раскрыл подробности предотвращенного в Москве теракта на 1 сентября

28 февраля 13:04
Кадыров ответил на запрет въезда в Латвию

26 февраля 11:04
В ЦИК прокомментировали ноту протеста Киева из-за выборов в Крыму

23 февраля 23:04
В Минобороны опровергли сообщения об атаке на авиабазу Хмеймим

13 февраля 19:04
Саратовские власти выплатят по миллиону рублей семьям погибших при крушении Ан-148

12 февраля 09:04
В МЧС назвали наиболее вероятные сценарии войны с Россией

10 февраля 04:04
В Воронеже похоронили погибшего в Сирии летчика Романа Филипова

8 февраля 18:04
Инспекторам ДПС запретили составлять протоколы на судей

8 февраля 17:04
Пилот второго Су-25 рассказал, как прикрывал майора Филипова в его последнем бою

7 февраля 03:04
Погибший в Сирии летчик получил звание Героя России

6 февраля 17:04
Названы проблемы, которые больше всего беспокоили россиян в 2017 году

6 февраля 05:04
Суд отменил арест врача Елены Мисюриной

5 февраля 17:04
Погибшего в Сирии пилота представили к званию Героя России

5 февраля 14:04
В Госдуме сообщили о работе спецназа в районе, откуда боевики сбили Су-25

4 февраля 14:04
ЦИК завершил прием подписей от кандидатов в президенты

31 января 19:04
Путин попросил прощения у российских олимпийцев

31 января 17:04
Путин пошутил о том, что его не включили в "кремлевский доклад"

30 января 16:04
Песков назвал "кремлевский доклад" фактически списком врагов США

30 января 13:04
Ежемесячные выплаты льготникам вырастут с февраля

29 января 12:04
 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 >> 1864
 Главная новость дня Главная новость дня 
Трамп отказался от встречи с Ким Чен Ыном
 
 Эксклюзив Эксклюзив 
Как провести полезный онлайн вебинар Как провести полезный онлайн вебинар
 
  Топ новостей Опросы 
 Фоторепортажи: новости с подборкой фотографий Фоторепортажи 
Актера Шайа ЛаБаф арестовали за драку с полицейским
Брэд Питт появился на публике в жуткой одежде (видео)
Пугачева затмила невесту Никиты Преснякова (фото, видео)
Опубликованы ранние снимки Дэвида Боуи (фото)
Первые кадры со свадьбы внука Пугачевой (фото)
 Новости партнеров
 Новости дня Новости дня 
 
  Copyright © RIN 2000-
* Обратная связь
Контактная информация  
Политика  Общество  Экономика  Деловые  Наука  Hi-Tech  Культура  Шоу-бизнес  Спорт  Происшествия  Криминал  Скандалы  Пикантные  Зарубежные  ИноСМИ