кубик Рубика - 26 ходов

[PAV]

Согласно сообщениям СМИ, получено 20 ходов

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

[maxal]

PAV в сообщении #344019 писал(а):

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

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

[ewert]

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

[maxal]

ewert в сообщении #344030 писал(а):

по слухам, никакое это не док-во, а просто тупой перебор всех вариантов

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

[PAV]

ewert в сообщении #344030 писал(а):

а просто тупой перебор всех вариантов, осуществлённый за тупо распределённые по многим компьютерам индивидуальные 35 лет.

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

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

[Alexu007]

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

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

[PAV]

Alexu007 в сообщении #344087 писал(а):

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

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

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

[sergey83]

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

[age]

А вообще интересен закон распределения сложности позиций:
$\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}$

[sergey83]

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

[age]

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

[maxal]

sergey83 в сообщении #372998 писал(а):

Так неужели "алгоритм Бога" найден?

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

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

age в сообщении #373358 писал(а):

А почему сразу "бога"?

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

[creative]

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

[sergey83]

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

[alex1910]

creative в сообщении #376011 писал(а):

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

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