2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 
Сообщение28.08.2007, 14:09 
Аватара пользователя


15/11/06
2689
Москва Первомайская
tolstopuz писал(а):
Наилучший алгоритм сборки уже существует, и пока не было найдено ни одной позиции, требующей более 20 ходов. 26 - текущий теоретический предел, то есть доказано, что более 26 ходов потребоваться не может.

Эти слова я понял так, что 26 - это рекорд, который, не исключено, можно улучшить и до 23 (про 20 говорить не буду).

Предположим, у нас есть алгоритм, гарантирующий сборку кубика не более чем за 50 ходов. Если нам совсем не повезет, то мы соберем кубик за 50 ходов, а если очень повезет, то за 26 ходов или даже за 23 хода (про 20 я уж и не говорю). В одном случае неопределенность результата = (50 - 26)/(50 + 26) = 0.316, т.е. около 1/пи, в другом же случае она = (50 - 23)/(50 + 23) = 0.370 ~ 1/е. А поскольку пи встречается чаще, чем е, то и 26 больше похоже на абсолютный рекорд, чем 23. :)

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


17/10/05
3709
:evil:
Если повезет, мы соберем кубик за 0 шагов, а если не повезет — за 26. Или 23. Или 20. Но соотношение всё равно равно $0/x = 0$ :lol: Так как 0 встречается куда чаще, чем $\pi$ или $e$ вместе взятые. :P

 Профиль  
                  
 
 
Сообщение29.08.2007, 14:23 
Аватара пользователя


15/11/06
2689
Москва Первомайская
незваный гость писал(а):
:evil:
Если повезет, мы соберем кубик за 0 шагов, а если не повезет — за 26. Или 23. Или 20. Но соотношение всё равно равно $0/x = 0$ :lol: Так как 0 встречается куда чаще, чем $\pi$ или $e$ вместе взятые. :P

Маленькая поправочка: (50 - 0)/(50 + 0) = 1, а не 0. Тогда вот что: чтобы этого не было, будем рассматривать не произвольные состояния кубика, а только абсолютно наихудшие.

Рассмотрим состояние кубика, наихудшее с точки зрения его сборки по заданному алгоритму. Наверное, это будет состояние с максимальной энтропией. Почему бы в таком случае их все не перебрать и не установить для данного алгоритма наихудший результат? Или их слишком много? А не может ли оказаться, что по результату все они одикаковы и достаточно проверить лишь одно из этих состояний?

Как устроено состояние с максимальной энтропией? В таком состоянии на каждой грани должно быть по полтора квадратика каждого цвета. Понятно, что это невозможно, однако состояние с максимальной энтропией, думаю, будет близко к этому. Наверное, так: на каждой грани будет по два квадратика трех разных цветов и по одному квадратику трех других цветов. Верно? А может, и неверно: я покрутил, покрутил кубик наугад, долго крутил... и ни разу такого состояния не получил! Впрочем, если подбросить монету 100 раз, то вряд ли получишь в точности 50 орлов и 50 решек, хотя это и наиболее вероятный результат среди всех такого рода пар. :(

 Профиль  
                  
 
 
Сообщение31.08.2007, 13:46 
Аватара пользователя


15/11/06
2689
Москва Первомайская
незваный гость писал(а):
Меня интересует теория.

Мне кажется, что кубик Рубика - это неплохая, причем обратимая, модель для термодинамики. Поэтому не может ли термодинамика сказать нам что-то интересное про кубик Рубика?

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


17/10/05
3709
:evil:
geomath писал(а):
Рассмотрим состояние кубика, наихудшее с точки зрения его сборки по заданному алгоритму. Наверное, это будет состояние с максимальной энтропией.

Как устроено состояние с максимальной энтропией? В таком состоянии на каждой грани должно быть по полтора квадратика каждого цвета.

Как бы еще это доказать? А то за морем телушка — полушка.

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


31/12/05
1346
geomath писал(а):
Как устроено состояние с максимальной энтропией? В таком состоянии на каждой грани должно быть по полтора квадратика каждого цвета. Понятно, что это невозможно, однако состояние с максимальной энтропией, думаю, будет близко к этому.
Кубик Рубика не состоит из "квадратиков". Забавно наблюдать за начинающими, которые собирают из "квадратиков" одну грань, а потом выясняют, что все кубики этой грани надо опять переставлять.

А наихудшее из найденных состояний (единственное известное, требующее 20 ходов) - это переворот всех двенадцати кубиков на ребрах. Заметьте, довольно-таки упорядоченное состояние.

 Профиль  
                  
 
 
Сообщение03.09.2007, 15:02 
Аватара пользователя


15/11/06
2689
Москва Первомайская
незваный гость писал(а):
:evil:
geomath писал(а):
Рассмотрим состояние кубика, наихудшее с точки зрения его сборки по заданному алгоритму. Наверное, это будет состояние с максимальной энтропией.

Как устроено состояние с максимальной энтропией? В таком состоянии на каждой грани должно быть по полтора квадратика каждого цвета.

Как бы еще это доказать? А то за морем телушка — полушка.

В лекциях Босса, в томе про вероятность, в параграфе ПРИНЦИП МАКСИМУМА ЭНТРОПИИ есть такая задачка. Имеется город, разбитый на районы. Каждый горожанин в каком-то районе живет и в каком-то работает. Требуется оценить пассажиропотоки.

Разве это не похоже на кубик Рубика?!

Пусть $x_{ij}$ - пассажиропоток из района $i$ с числом житетей $L_i$ в район $j$ с числом рабочих мест $W_j$, а $p_{ij} = x_{ij}/N$ - доля жителей, живущих в районе $i$ и работающих в районе $j$, от числа $N$ всех горожан. При этом $\sum\limits_i L_i = N$ и $\sum\limits_j W_j = N$. Тогда, максимизируя энтропию $-\sum\limits_{ij} p_{ij}\ln p_{ij}$ при ограничениях $\sum\limits_j p_{ij} = L_i$ и $\sum\limits_i p_{ij} = W_j$, получим, что $p_{ij} = (L_i/N)(W_j/N)$ и соответственно $x_{ij} = (L_iW_j)/N$.

В случае КАК БЫ кубика все $L_i$ и $W_j$ равны $9$, а $N = 54$, откуда все $x_{ij} = 3/2$.

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

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


29/07/05
8248
Москва
geomath писал(а):
Не знаю, в чем тут дело...


А дело в том, что в данной задаче считать наихудшим состоянием. Вы же при сборке кубика имеете возможность совершать преобразования только некоторых определенных типов, которые действуют сразу на определенную группу квадратиков. Этим все и определяется. Вот если рассмотреть примитивный кубик, где можно менять местами любые два квадратика, не трогая другие, то тут наихудшим было бы достаточно сильно "перемешанное" состояние, имеющее действительно высокую энтропию. В данном же случае Вам нужно перейти от одного достаточно регулярного состоянию к другому регулярному. Но любое преобразование, которым мы пользуетмся, сразу же регулярность нарушает...

 Профиль  
                  
 
 
Сообщение03.09.2007, 15:50 
Аватара пользователя


15/11/06
2689
Москва Первомайская
PAV писал(а):
А дело в том, что...

Во-первых, даже в случае пассажиропотоков каждый отдельный пассажир тоже не ездит сам по себе, а двигается в потоке других пассажиров, например, в поезде метро... Во-вторых, решение, которое получилось (полтора квадратика), физически невозможно, поэтому я предлагал не его, а близкое к нему. Однако, по tolstopuzу, близкое решение вроде бы совсем и не близкое... Что же, получается, действительно близкие состояния недостижимы?

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


29/07/05
8248
Москва
geomath писал(а):
действительно близкие состояния недостижимы


Близкие по какой метрике?

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


15/11/06
2689
Москва Первомайская
Если по полтора квадратика каждого цвета на каждой грани невозможны, то по два квадратика трех цветов и по одному квадратику трех других цветов на каждой грани - это близкое к тому состояние, а по восемь квадратиков одного цвета и по одному другого - это далекое состояние. Не знаю только, достижимо ли такое близкое состояние...

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


31/12/05
1346
geomath писал(а):
Правда, tolstopuz говорит, что наихудшее (20-ходовое) состояние устроено по-другому: на каждой грани по восемь квадратиков одного цвета и один квадратик другого.
Нет. Пять (центр и углы) одного и четыре других.

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

 Профиль  
                  
 
 
Сообщение03.09.2007, 17:11 
Аватара пользователя


15/11/06
2689
Москва Первомайская
Да, я сказал глупость. Конечно, пять одного и четыре других. Хорошо. А по два "квадратика" трех цветов и по одному трех других цветов - это состояние за сколько ходов собирается? Вообще оно достижимо?

 Профиль  
                  
 
 
Сообщение04.09.2007, 15:42 
Аватара пользователя


15/11/06
2689
Москва Первомайская
PAV писал(а):
Близкие по какой метрике?

Близкие по энтропии.

Я посчитал энтропию трех состояний:

- по полтора квадратика каждого цвета на каждой грани (невозможное состояние),
- по два квадратика трех цветов и по одному квадратику трех других цветов на каждой грани (возможно, недостижимое состояние) и
- все реберные кубики перевернуты (состояние, достистижимое хотя бы за 20 ходов).

Если я не ошибся, то получилось соответственно: 5.17, 5.09 и 4.46 бит. В этом смысле второе состояние близко к первому, а третье - далеко от первого.

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


17/10/05
3709
:evil:

Уже только 25?
Tomas Rokicki Twenty-Five Moves Suffice for Rubik's Cube

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

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



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

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


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

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