2014 dxdy logo

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

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




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

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

 
 
 
 
Сообщение22.08.2007, 14:57 
Аватара пользователя
Если мне не изменяет память, теоретически достаточно 23 хода.

 
 
 
 
Сообщение22.08.2007, 15:00 
Аватара пользователя
Артамонов Ю.Н. писал(а):
Если мне не изменяет память, теоретически достаточно 23 хода.

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

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

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

 
 
 
 
Сообщение22.08.2007, 15:47 
Все-таки пока 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 
Аватара пользователя
Вот в более конкретной книге Л.А. Калужнин, В.И.Сущанский "Преобразования и перестановки" - М.: 1985 на стр 143 написано аккуратнее:
Цитата:
"После более детального анализа был разработан алгоритм, позволяющий раскладывать перестановки в произведение образующих длины не более 52, причем высказано мнение, что можно ограничиться произведениями длины не более 23.
На самом деле оценку длины возможных разложений можно исследовать независимо, без рассмотрения алгоритмов, позволяющих такое разложение осуществлять."

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

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


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

 
 
 
 
Сообщение22.08.2007, 20:18 
Аватара пользователя
: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 
Аватара пользователя
История вопроса от Константина Кнопа:
Кубик Рубика: штурм твердыни

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

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

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

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

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

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

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

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

 
 
 
 
Сообщение27.08.2007, 20:17 
Аватара пользователя
: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