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

[PAV]

Согласно последним исследованиям, из любого положения можно собрать за 26 ходов.

http://hitech.newsru.com/article/22Aug2007/rubegg

[juna]

Если мне не изменяет память, теоретически достаточно 23 хода.

[PAV]

Артамонов Ю.Н. писал(а):

Если мне не изменяет память, теоретически достаточно 23 хода.

Не думаю. Если бы это было теоретически доказано (что, скорее всего, дает и алгоритм), то его бы и пытались улучшать. Маловероятно, что при проведении подобного исследования авторы не знали об этом результате.

[juna]

Нашел. Видел в этой книжке "Энциклопедический словарь юного математика" сост. Савин.- М.: Педагогика, 1985. - 352 с.
Там на стр. 143 написано:

Цитата:

Имеются принципиально другие схемы сборки. Лучшие из них позволяют обойтись примерно 50 ходами-поворотами, но теоретически из любого состояния кубика можно вернуться в исходное не более чем за 23 хода.

С одной стороны, источник еще тот, с другой, раньше книги писали качественно.

[tolstopuz]

Все-таки пока 26.
http://www.neu.edu/nupr/news/0507/rubik.html
http://www.ccs.neu.edu/home/gene/papers/rubik.pdf

[juna]

Вот в более конкретной книге Л.А. Калужнин, В.И.Сущанский "Преобразования и перестановки" - М.: 1985 на стр 143 написано аккуратнее:

Цитата:

"После более детального анализа был разработан алгоритм, позволяющий раскладывать перестановки в произведение образующих длины не более 52, причем высказано мнение, что можно ограничиться произведениями длины не более 23.
На самом деле оценку длины возможных разложений можно исследовать независимо, без рассмотрения алгоритмов, позволяющих такое разложение осуществлять."

P.S. Мало того, что книжки одного года, еще и текст на одинаковых страницах.

[PAV]

Цитата:

На самом деле оценку длины возможных разложений можно исследовать независимо, без рассмотрения алгоритмов, позволяющих такое разложение осуществлять

Однако такая оценка почти наверняка окажется завышенной. А поскольку тут уже, вероятно, почти приблизились к точному ответу, то уже приходится давать или алгоритм, или перебор.

[незваный гость]

Источник всех переводов: http://www.sciencenews.org/articles/20070811/mathtrek.asp

В конце несколько любопытных фраз: что Kunkle и Cooperman хотят снизить до 25, что большинство исследователей считает, что достаточно 20.

То, что у этих ребят есть шанс для улучшения, понятно: они использовали довольно жесткие промежуточные стадии. Собственно, это беда и всех алгоритмов ручной сборки — стадии. А к тому же не очевидна оптимальность самих стадий — лишь простота.

~~~

Помнится, я видел заметку (опубликованную в начале 80х) о «британском ученом» собиравшем кубик по-моему за 26 шагов. Его способ был существенно компьютерным — использовались инварианты, которые человеку не отследить, Запомнилось ключевое слово «спуск через подгруппы».

P.S. Стал на сети искать и нашел … Someone

P.P.S. Видимо, общий источник информации — статья И. Константинова «А все-таки, как его собрать?» в «Наука и жизнь» №2, 1982. Там же дается имя: М. Тэйстлетуайт, специалист по прикладной математике из Лондона. (q.v. http://www.rubiks.ru/club2.html)

~~~

Как всегда, Википедия дает интересную информацию: см. секцию Upper bounds. В частности, имя Morwen B. Thistlethwaite и описание его алгоритма.

[maxal]

История вопроса от Константина Кнопа:
Кубик Рубика: штурм твердыни

[geomath]

Что-то я не понял про 23 и 26. Может быть, 23 - это теоретический предел, а 26 - это предел наилучшего на сегодня алгоритма сборки? Когда-то, как цитировал Артамонов Ю.Н., наилучшим было 50, а теперь - 26. Правильно?

[tolstopuz]

geomath писал(а):

Может быть, 23 - это теоретический предел, а 26 - это предел наилучшего на сегодня алгоритма сборки?

Наилучший алгоритм сборки уже существует, и пока не было найдено ни одной позиции, требующей более 20 ходов. 26 - текущий теоретический предел, то есть доказано, что более 26 ходов потребоваться не может.

[незваный гость]

Я бы не сказал, что наилучший алгоритм сборки известен. По крайней мере, я нигде не слышал о публикации алгоритма без возвратов. Иначе, существование алгоритма тривиально: полный перебор.

Кроме того, существует две метрики — метрика поворотов (поворот на 180 градусов — одно движение) и метрика четвертей (поворот на 180 градусов — два хода).

На мой взгляд, результаты выглядят таким образом: в метрике поворотов найдены позиции, про которые доказано (Michael Reid), что они не могут быть решены менее, чем за 20 ходов. Кроме того, есть алгоритм (Daniel Kunkle, Gene Cooperman), решающий любую позицию за гарантированные 26 ходов.

Плюс, есть хороший переборный алгоритм (Richard Korf), находящий оптимальные решения. К сожалению, об их длине ничего не известно.

[PAV]

В ссылке, которую привел maxal, сказано про программу Герберта Коцембы (Herbert Kociemba), для которой еще не найдено ни одной позиции, которую бы эта программа не сумела собрать за 20 ходов.

[tolstopuz]

незваный гость писал(а):

Я бы не сказал, что наилучший алгоритм сборки известен. По крайней мере, я нигде не слышал о публикации алгоритма без возвратов. Иначе, существование алгоритма тривиально: полный перебор.

Теоретически - да. Реально полный перебор за разумное время стал осуществим только несколько лет назад. Сейчас это пара минут на трех гигагерцах и трех гигабайтах.

[незваный гость]

http://kociemba.org/cube.htm
http://kociemba.org/math/optimal.htm

Добавлено спустя 55 секунд:

tolstopuz писал(а):

Теоретически

Меня интересует теория.