2014 dxdy logo

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

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




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


29/07/05
8248
Москва
Согласно последним исследованиям, из любого положения можно собрать за 26 ходов.

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

 Профиль  
                  
 
 
Сообщение22.08.2007, 14:57 
Заслуженный участник
Аватара пользователя


07/03/06
1716
Москва
Если мне не изменяет память, теоретически достаточно 23 хода.

 Профиль  
                  
 
 
Сообщение22.08.2007, 15:00 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Артамонов Ю.Н. писал(а):
Если мне не изменяет память, теоретически достаточно 23 хода.

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

 Профиль  
                  
 
 
Сообщение22.08.2007, 15:07 
Заслуженный участник
Аватара пользователя


07/03/06
1716
Москва
Нашел. Видел в этой книжке "Энциклопедический словарь юного математика" сост. Савин.- М.: Педагогика, 1985. - 352 с.
Там на стр. 143 написано:
Цитата:
Имеются принципиально другие схемы сборки. Лучшие из них позволяют обойтись примерно 50 ходами-поворотами, но теоретически из любого состояния кубика можно вернуться в исходное не более чем за 23 хода.

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

 Профиль  
                  
 
 
Сообщение22.08.2007, 15:47 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение22.08.2007, 16:19 
Заслуженный участник
Аватара пользователя


07/03/06
1716
Москва
Вот в более конкретной книге Л.А. Калужнин, В.И.Сущанский "Преобразования и перестановки" - М.: 1985 на стр 143 написано аккуратнее:
Цитата:
"После более детального анализа был разработан алгоритм, позволяющий раскладывать перестановки в произведение образующих длины не более 52, причем высказано мнение, что можно ограничиться произведениями длины не более 23.
На самом деле оценку длины возможных разложений можно исследовать независимо, без рассмотрения алгоритмов, позволяющих такое разложение осуществлять."

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

 Профиль  
                  
 
 
Сообщение22.08.2007, 19:12 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Цитата:
На самом деле оценку длины возможных разложений можно исследовать независимо, без рассмотрения алгоритмов, позволяющих такое разложение осуществлять


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

 Профиль  
                  
 
 
Сообщение22.08.2007, 20:18 
Заслуженный участник
Аватара пользователя


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

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

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

~~~

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

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

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

~~~

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

 Профиль  
                  
 
 
Сообщение23.08.2007, 03:38 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение27.08.2007, 16:53 
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение27.08.2007, 17:24 
Заслуженный участник


31/12/05
1080
geomath писал(а):
Может быть, 23 - это теоретический предел, а 26 - это предел наилучшего на сегодня алгоритма сборки?
Наилучший алгоритм сборки уже существует, и пока не было найдено ни одной позиции, требующей более 20 ходов. 26 - текущий теоретический предел, то есть доказано, что более 26 ходов потребоваться не может.

 Профиль  
                  
 
 
Сообщение27.08.2007, 18:36 
Заслуженный участник
Аватара пользователя


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

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

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

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

 Профиль  
                  
 
 
Сообщение27.08.2007, 19:28 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение27.08.2007, 20:15 
Заслуженный участник


31/12/05
1080
незваный гость писал(а):
Я бы не сказал, что наилучший алгоритм сборки известен. По крайней мере, я нигде не слышал о публикации алгоритма без возвратов. Иначе, существование алгоритма тривиально: полный перебор.
Теоретически - да. Реально полный перебор за разумное время стал осуществим только несколько лет назад. Сейчас это пара минут на трех гигагерцах и трех гигабайтах.

 Профиль  
                  
 
 
Сообщение27.08.2007, 20:17 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
http://kociemba.org/cube.htm
http://kociemba.org/math/optimal.htm

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

tolstopuz писал(а):
Теоретически
Меня интересует теория.

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

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



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

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


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

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