Обсуждение:Математика кубика Рубика

Stannic 01:58, 20 июля 2013 (UTC)

35 лет CPU...

Очень смущает из источника: «With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik’s Cube™, and shown that no position requires more than twenty moves. We consider any twist of any face to be one move (this is known as the half-turn metric.)» — смахивает на журналистский перл (или пиар от Google - во! какие мы щедрые, 35 лет работы своих компьютеров не пожалели!), я бы понял, если бы была указана трудоемкость задачи в количестве инструкций процессора, а так — непонятно, 35 лет… Чего? 10 процессоров или 10000 процессоров? Д.Ильин 15:23, 21 июля 2013 (UTC).

Меня больше смущает фраза о том, что они "по существу решили каждую позицию". Использованный алгоритм не решает каждую позицию, т.к. их слишком много, и нужно было бы гораздо больше ресурсов. Они разбили все конфигурации на классы и работали с целыми классами. Это можно найти в публикациях Рокики по 25, 23, 22 ходам.

Трудоёмкость в количестве инструкций нигде не указана.

Этот сайт был создан участниками группы. Там выложен исходный код. Все остальные источники, по существу, брали информацию оттуда, причём с искажениями и журналистскими перлами.

По крайней мере, мне не удалось найти более авторитетных источников :) Stannic 15:44, 21 июля 2013 (UTC)

Уж было собрался писать авторам вопрос, но решил сперва внимательно прочитать источник, кое-что прояснилось:

How We Did It

How did we solve all 43,252,003,274,489,856,000 positions of the Cube? We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each. We reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering.

We did not find optimal solutions to each position, but instead only solutions of length 20 or less. We wrote a program that solved a single set in about 20 seconds.

We used about 35 CPU years to find solutions to all of the positions in each of the 55,882,296 sets.

55882296 pos sets * 20 s = 1117645920 s;

1117645920 s / 3.1e7 s/y = ~36 y.

Предположим, Google отслюнил от щедрот своих им сутки:

1117645920 s / 86400 s = ~13000 процессоров — вполне реально.

С уважением, Д.Ильин 16:56, 21 июля 2013 (UTC).

Алгоритм Бога

Нетрудно доказать теорему, что он в полнопереборном виде существует.

• Схема доказательства:

1. Порождаем все конфигурации (вершины графа) из запутанной.
2. Проверяем, в порожденных нет ли собранной, если так, останавливаемся с сообщением.
3. Из каждой порожденной вершины порождаем новые вершины, если вершина уже была порождена ранее - вычеркиваем ее из списка вершин, и проверяем, нет ли среди порожденных собранной, есть - конец.
4. Перейти на 2.
   

Д.Ильин 19:14, 25 июля 2013 (UTC).

Близкая по духу теорема существует для шахмат. К сожалению, количество вариантов оказывается слишком большим даже в случае КР, не говоря уже о шахматах.

• Число конфигураций КР: ~ 4·10¹⁹
• Число шахматных позиций: ~ 10⁴³

По мнению некоторых авторов (например, Джойнера), алгоритм Бога должен быть практичным. Иначе можно было бы использовать огромную таблицу поиска размером в 4·10¹⁰ Гбайт, в которой для каждой конфигурации КР была бы записана длина оптимального решения (или оптимальный ход в данной конфигурации).

Практичный алгоритм Бога мог бы представлять собой формулу или простую стратегию, как в Ханойской башне или в крестиках-ноликах. Для КР такой стратегии пока нет.

Stannic 20:27, 25 июля 2013 (UTC)

---

Писать , что алгоритм Бога неизвестен - неправильно. В упоминании полнопереборного алгоритма мной - это очевидно.

Полнопереборный алгоритм обладает свойствами:

1. Останавливается при решении.
2. Конструктивен.
3. Находит число Бога.
4. При дополнении алгоритмом анализа кратчайших путей на графе - найдет все решения.

Не знаю, есть ли в АИ эта теорема для КР, но она тривиальна, можно сослаться на более общую теорему Цермело для игр с полной информацией.

Совершенно иной вопрос, существует ли практичный алгоритм Бога для сборки КР. Критерии практичности размыты. Для строгости, нужно ввести функцию ПРАКТИЧНОСТЬ АЛГОРИТМА на счетном множестве конечных кодов алгоритмов.

Сомневаюсь, что при разумных критериях практичности (память, время) эта функция будет вычислимой, думаю, даже полувычислимой тоже не будет.

Д.Ильин 09:46, 26 июля 2013 (UTC).

---

Согласен, что алгоритм Бога без доп. требований практичности/эффективности известен. Немного поправил статью. Спасибо за замечание.

Не думаю, что нужно специально вводить строгое понятие практичности, по-моему, это ясно из контекста. Но добавил примеры в статье Алгоритм Бога. Stannic 20:49, 26 июля 2013 (UTC)

Set covering

См. цитату выше. Как правильно перевести? Поглощение множества или покрытие множества? Д.Ильин 05:07, 27 июля 2013 (UTC).

Думаю, покрытие множества. Stannic 10:25, 27 июля 2013 (UTC)

Другие головоломки

Добавил раздел Математика кубика Рубика#Другие головоломки с информацией по некоторым головоломкам, для которых в данное время известны нетривиальные результаты. Числа Бога для некоторых «простых» головоломок находятся в Алгоритм Бога#Примеры.

Статья сильно разрослась, не уверен, что это хорошо. Можно было бы вынести некоторые части в отдельные статьи, например, нотацию Сингмастера — в статью о нём; алгоритм Тистлетуэйта в статью о Тистлетуэйте, как в англовики (en:Morwen Thistlethwaite). Но тогда потеряется контекст.

Как Вы считаете — вынести или оставить всё как есть?

Stannic 00:28, 28 июля 2013 (UTC)

Я считаю, - оставить как есть, но другие коллеги могут считать иначе. Поэтому предлагаю вынести статью на рецензирование, после рецензирования можно будет подумать - ее в КХС.

Д.Ильин 05:15, 28 июля 2013 (UTC).

Рецензирование статьи Математика кубика Рубика

Здесь находятся завершившиеся обсуждения. Просьба не вносить изменений.

Планирую выставить на КХС, нужна любая конструктивная критика. Stannic 12:29, 28 июля 2013 (UTC)

Дополнение: Добавил раздел «Граф Шрайера». Главным образом интересуют замечания по нему и описанию алгоритмов Тистлетуэйта и Коцембы. Stannic 17:14, 30 июля 2013 (UTC)

• Закрыл по собственному желанию. — Stannic 00:03, 8 августа 2013 (UTC)

Void Cube

Может, на русский перевести: "Вырезанный куб"? или: "Куб с полостями"? Или иначе? Д.Ильин 13:44, 28 июля 2013 (UTC).

На русскоязычных форумах чаще употребляется оригинальное название, например [1], или Войд Куб. Наверно, правильнее оставить оригинальное название: ВП:ОРЗАГ

Та же ситуация (неясно, как переводить и нужен ли перевод названия) с Rubik's Revenge. Stannic 14:00, 28 июля 2013 (UTC)

Доказательство для метрики FTM

"Первый ход можно сделать 6 ⋅ 3 = 18 способами (любую из шести граней можно повернуть на один из трёх углов — 180°, ±90°)"

Я, видимо, что-то не понял - всего граней в кубике 9 — 6 лицевых и 3 средних. Первый ход можно сделать 27 способами, следующие ходы — 24 способами, о каких 18 и последующих 15 идёт речь? Но пусть 18 и 15

"Количество различных последовательностей из $n$ ходов будет равно $18\cdot 15^{n-1}$" — это понятно, число перестановок из $n$ ходов.

"Число последовательностей длины, не превосходящей $n$, равно $18\cdot (1+15+\ldots +15^{n-1})$" — а вот это непонятно, число перестановок, не большее $n$ не может быть больше числа перестановок $n$. А по формуле получается больше. Или я неправильно понял термин "Число последовательностей длины", хотя по смыслу это разные комбинации разных ходов, т.е. перестановка. И по формуле это перестановка — $n!$ = $18$(первый ход)$\cdot 15^{n-1}$(последующие ходы). АФ32 (обс.) 21:16, 13 апреля 2017 (UTC)

Граней шесть, как и у любого куба. В метрике FTM (она же HTM, face turn = поворот грани, half turn = полуповорот/поворот на 180°) за один ход считается поворот любой грани на любой угол, т.е. ходов 18. Ваш вариант называется slice turn metric - в STM поворот любого из средних слоёв тоже считается за один ход.

Последовательности ходов длины n - это просто строчки в нотации Сингмастера, например L F2 R' U B U L2 (в этом примере длина равна 7). Факториал неприменим, так как в последовательности ходов один и тот же ход может встречаться больше одного раза или не встречаться вообще. stannic 22:06, 9 мая 2017 (UTC)

Про «цепочки ходов длины n» см. также стр. 55 в «Кванте». stannic 22:19, 9 мая 2017 (UTC)