2014 dxdy logo

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

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




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

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

 
 
 
 Re: кубик Рубика - 26 ходов
Сообщение12.08.2010, 17:02 
Аватара пользователя
PAV в сообщении #344019 писал(а):
кубик Рубика можно собрать за 20 ходов из любой позиции

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

 
 
 
 Re: кубик Рубика - 26 ходов
Сообщение12.08.2010, 18:23 
по слухам, никакое это не док-во, а просто тупой перебор всех вариантов, осуществлённый за тупо распределённые по многим компьютерам индивидуальные 35 лет. Непонятно зачем. Ну Рубик, ну и что. Какая от этого польза для сельского хозяйства-то (ну т.е. хоть для какой теории)?...

 
 
 
 Re: кубик Рубика - 26 ходов
Сообщение12.08.2010, 20:16 
Аватара пользователя
ewert в сообщении #344030 писал(а):
по слухам, никакое это не док-во, а просто тупой перебор всех вариантов

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

 
 
 
 Re: кубик Рубика - 26 ходов
Сообщение12.08.2010, 20:30 
Аватара пользователя
ewert в сообщении #344030 писал(а):
а просто тупой перебор всех вариантов, осуществлённый за тупо распределённые по многим компьютерам индивидуальные 35 лет.


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

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

 
 
 
 Re: кубик Рубика - 26 ходов
Сообщение13.08.2010, 06:54 
А от обратного пробовали: можно ли за n ходов из собранного кубика получить любую возможную конфигурацию?

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

 
 
 
 Re: кубик Рубика - 26 ходов
Сообщение13.08.2010, 10:05 
Аватара пользователя
Alexu007 в сообщении #344087 писал(а):
Может так и перебирать варианты: брать собранный кубик, делать n случайных ходов и заносить результат в базу данных. И не заморачиваться мудрёными алгоритмами.


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

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

 
 
 
 Re: кубик Рубика - 26 ходов
Сообщение08.11.2010, 01:29 
Я не понял, как искалось решение для конкретной позиции кубика. Вот пришла позиция, требующая для решения 20 ходов, например, superflip позиция (углы правильные, края помещены но перевернутый). Допустим, для решения конкретной позиции запускается поиск в ширину на графе с глубиной 20 шагов. Однако такой алгоритм не сможет найти решения за пару секунд.
Либо действительно, у авторов был очень крутой переборный алгоритм, который даже в худшем случае находил решение для конкретной позиции не более, чем за час? Если и был, то это что - модификация какого-то известного алгоритма?
Из переборных алгоритмов я предложил бы поиск в ширину на графе. Однако при глубине в 20 шагов для плохой позиции он ни за что бы не нашел решения за час.

 
 
 
 Re: кубик Рубика - 26 ходов
Сообщение08.11.2010, 07:12 
Аватара пользователя
А вообще интересен закон распределения сложности позиций:
$\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 
Видел название статьи:"Ученые вывели формулу, которая позволяет собрать знаменитый кубик Рубика из любого положения за 20 ходов. Об информирует The Daily Telegraph."
Так неужели "алгоритм Бога" найден?

 
 
 
 Re: кубик Рубика - 26 ходов
Сообщение11.11.2010, 02:34 
Аватара пользователя
А почему сразу "бога"? Или изобретение Рубика = "богу" :?

 
 
 
 Re: кубик Рубика - 26 ходов
Сообщение11.11.2010, 02:49 
Аватара пользователя
sergey83 в сообщении #372998 писал(а):
Так неужели "алгоритм Бога" найден?

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

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

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

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

 
 
 
 Re: кубик Рубика - 26 ходов
Сообщение16.11.2010, 17:27 
Аватара пользователя
Кстати для ручной сборки метод Ларса Петруса один из самых оптимальных по наименьшему количеству ходов.
Другой плюс метода заключается в том, что в отличии от метода Фридрих этот метод сложнее, поэтому мозги при скоростной сборке всё же работают.

 
 
 
 Re: кубик Рубика - 26 ходов
Сообщение13.06.2011, 21:53 
Тут http://kociemba.org/cube.htm разрабатывается следующая программа: на входе подается кубик, который задает пользователь, а программа выдает оптимальный алгоритм сборки кубика.
Интересно, а в худшем случае, когда для сборки нужно 20 ходов, сколько секунд длится поиск пути сборки кубика на домашнем компьютере?

 
 
 
 Re: кубик Рубика - 26 ходов
Сообщение14.06.2011, 11:49 
creative в сообщении #376011 писал(а):
Кстати для ручной сборки метод Ларса Петруса один из самых оптимальных по наименьшему количеству ходов.
Другой плюс метода заключается в том, что в отличии от метода Фридрих этот метод сложнее, поэтому мозги при скоростной сборке всё же работают.


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

 
 
 [ Сообщений: 49 ]  На страницу Пред.  1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group