2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: кубик Рубика - 26 ходов
Сообщение12.08.2010, 16:52 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Согласно сообщениям СМИ, получено 20 ходов

кубик Рубика можно собрать за 20 ходов из любой позиции

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение12.08.2010, 17:02 
Модератор
Аватара пользователя


11/01/06
5660
PAV в сообщении #344019 писал(а):
кубик Рубика можно собрать за 20 ходов из любой позиции

Официальный вебсайт этого доказательства: http://www.cube20.org/

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение12.08.2010, 18:23 
Заслуженный участник


11/05/08
32166
по слухам, никакое это не док-во, а просто тупой перебор всех вариантов, осуществлённый за тупо распределённые по многим компьютерам индивидуальные 35 лет. Непонятно зачем. Ну Рубик, ну и что. Какая от этого польза для сельского хозяйства-то (ну т.е. хоть для какой теории)?...

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение12.08.2010, 20:16 
Модератор
Аватара пользователя


11/01/06
5660
ewert в сообщении #344030 писал(а):
по слухам, никакое это не док-во, а просто тупой перебор всех вариантов

Вполне себе computer-assisted proof.

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение12.08.2010, 20:30 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
ewert в сообщении #344030 писал(а):
а просто тупой перебор всех вариантов, осуществлённый за тупо распределённые по многим компьютерам индивидуальные 35 лет.


Судя по табличке на сайте, задача исследуется уже не менее 15 лет. Последние продвижения продолжаются уже лет 5.

Неужели Вы полагаете, что это сдерживалось только машинным временем? И что желающие найти ответ не могли набрать несколько сотен машин, выйти на какой-нибудь кластер или воспользоваться помощью интернет-пользователей, и не получить этот ответ за месяц?

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение13.08.2010, 06:54 


24/05/09

2054
А от обратного пробовали: можно ли за n ходов из собранного кубика получить любую возможную конфигурацию?

Может так и перебирать варианты: брать собранный кубик, делать n случайных ходов и заносить результат в базу данных. И не заморачиваться мудрёными алгоритмами.

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение13.08.2010, 10:05 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Alexu007 в сообщении #344087 писал(а):
Может так и перебирать варианты: брать собранный кубик, делать n случайных ходов и заносить результат в базу данных. И не заморачиваться мудрёными алгоритмами.


Разумеется, такой метод известен, но с его помощью можно решить только довольно простые задачи. Если бы его можно было здесь применить, то задача была бы решена уже давно. На сайте решения указано, сколько всего существует комбинаций: $43,252,003,274,489,856,000$.
Это количество нереально занести ни в какую базу данных. Перебрать все преобразования до 20 шагов тоже нереально долго.

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

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение08.11.2010, 01:29 


03/06/10
152
Я не понял, как искалось решение для конкретной позиции кубика. Вот пришла позиция, требующая для решения 20 ходов, например, superflip позиция (углы правильные, края помещены но перевернутый). Допустим, для решения конкретной позиции запускается поиск в ширину на графе с глубиной 20 шагов. Однако такой алгоритм не сможет найти решения за пару секунд.
Либо действительно, у авторов был очень крутой переборный алгоритм, который даже в худшем случае находил решение для конкретной позиции не более, чем за час? Если и был, то это что - модификация какого-то известного алгоритма?
Из переборных алгоритмов я предложил бы поиск в ширину на графе. Однако при глубине в 20 шагов для плохой позиции он ни за что бы не нашел решения за час.

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение08.11.2010, 07:12 
Заблокирован
Аватара пользователя


17/06/09

2213
А вообще интересен закон распределения сложности позиций:
$\begin{array}{|c|c|} \text{Сложность позиции} & \text{Количество позиций}\\
\hline
0 & 1\\
1 & 18\\
2 & 243\\
3 & 3,240\\
4 & 43,239\\
5 & 574,908\\
6 & 7,618,438\\
7 & 100,803,036\\
8 & 1,332,343,288\\
9 & 17,596,479,795\\
10 & 232,248,063,316\\
11 & 3,063,288,809,012\\
12 & 40,374,425,656,248\\
13 & \text{около } 531,000,000,000,000\\
14 & \text{около }7,000,000,000,000,000\\
15 & \text{около }91,000,000,000,000,000\\
16 & \text{около }1,100,000,000,000,000,000\\
17 & \text{около }12,000,000,000,000,000,000\\
18 & \text{около }29,000,000,000,000,000,000\\
19 & \text{около }1,500,000,000,000,000,000\\
20 & \text{около }300,000,000\\
21 & 0\\
\hline
\end{array}$
Пик приходится на сложность 18 ходов. А количество 20-ходовых позиций вообще падает резко до 300 000 000 - такое же как 7-ходовых. Позиций, требующих 21 ход нет ни одной.
Интересно, а можно ли такой закон получить аналитически?

-- Пн ноя 08, 2010 08:28:55 --

Логнормированный график выглядит следующим образом:
Изображение

т.е. состоит четко из двух прямых линий, откуда следует, что зависимость строго степенная.
Средний коэффициент увеличения количества позиций с ростом сложности у меня получился $13.2$, точнее, он изменяется плавно от $13.33$ до $13.07$. Затем (там где "шапочка") пробегает значения $12$, $11$, $2.4$ после чего очень быстро падает: $\dfrac{1}{19}$, $\dfrac{1}{5\cdot10^9}$

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение10.11.2010, 01:23 


03/06/10
152
Видел название статьи:"Ученые вывели формулу, которая позволяет собрать знаменитый кубик Рубика из любого положения за 20 ходов. Об информирует The Daily Telegraph."
Так неужели "алгоритм Бога" найден?

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение11.11.2010, 02:34 
Заблокирован
Аватара пользователя


17/06/09

2213
А почему сразу "бога"? Или изобретение Рубика = "богу" :?

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение11.11.2010, 02:49 
Модератор
Аватара пользователя


11/01/06
5660
sergey83 в сообщении #372998 писал(а):
Так неужели "алгоритм Бога" найден?

"Число Бога" - найдено. "Алгоритм Бога", который бы мог быть применим человеком, - нет.

-- Wed Nov 10, 2010 18:49:40 --

age в сообщении #373358 писал(а):
А почему сразу "бога"?

Такое уж у него традиционное название.

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение16.11.2010, 17:27 
Аватара пользователя


01/04/10
910
Кстати для ручной сборки метод Ларса Петруса один из самых оптимальных по наименьшему количеству ходов.
Другой плюс метода заключается в том, что в отличии от метода Фридрих этот метод сложнее, поэтому мозги при скоростной сборке всё же работают.

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение13.06.2011, 21:53 


03/06/10
152
Тут http://kociemba.org/cube.htm разрабатывается следующая программа: на входе подается кубик, который задает пользователь, а программа выдает оптимальный алгоритм сборки кубика.
Интересно, а в худшем случае, когда для сборки нужно 20 ходов, сколько секунд длится поиск пути сборки кубика на домашнем компьютере?

 Профиль  
                  
 
 Re: кубик Рубика - 26 ходов
Сообщение14.06.2011, 11:49 


21/07/10
555
creative в сообщении #376011 писал(а):
Кстати для ручной сборки метод Ларса Петруса один из самых оптимальных по наименьшему количеству ходов.
Другой плюс метода заключается в том, что в отличии от метода Фридрих этот метод сложнее, поэтому мозги при скоростной сборке всё же работают.


Люди, у которых есть мозги, обычно не занимаются скоростной сборкой кубика:)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 49 ]  На страницу Пред.  1, 2, 3, 4  След.

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group