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

[geomath]

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.

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

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

[geomath]

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

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

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

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

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

[geomath]

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

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

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

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

geomath писал(а):

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

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

[tolstopuz]

geomath писал(а):

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

Кубик Рубика не состоит из "квадратиков". Забавно наблюдать за начинающими, которые собирают из "квадратиков" одну грань, а потом выясняют, что все кубики этой грани надо опять переставлять.

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

[geomath]

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

: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-ходовое) состояние устроено по-другому: на каждой грани по восемь квадратиков одного цвета и один квадратик другого. Не знаю, в чем тут дело...

[PAV]

geomath писал(а):

Не знаю, в чем тут дело...

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

[geomath]

PAV писал(а):

А дело в том, что...

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

[PAV]

geomath писал(а):

действительно близкие состояния недостижимы

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

[geomath]

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

[tolstopuz]

geomath писал(а):

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

Нет. Пять (центр и углы) одного и четыре других.

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

[geomath]

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

[geomath]

PAV писал(а):

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

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

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

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

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

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

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