?

Log in

No account? Create an account
полезно в хозяйстве - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

полезно в хозяйстве [июл. 7, 2016|12:39 am]
Anatoly Vorobey
[Tags|]

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

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

Если один поворот занимает одну секунду, то в среднем кубик будет полностью собран за время, равное примерно 50 возрастам Вселенной на сегодняшний день.

[вообще-то интересная штука, с программистской точки зрения. Даже *проверить*, что это действительно гамильтонов цикл, кажется не очень простой задачей, хоть автор и попытался ее упростить своей нотацией. Наивные подходы, что приходят мне в голову, требуют очень много памяти]
СсылкаОтветить

Comments:
[User Picture]From: vladimir000
2016-07-06 09:53 pm
Мне как-то казалось, что существование такого цикла практически очевидно. Или он его построил и в это мдостижение?
(Ответить) (Thread)
[User Picture]From: avva
2016-07-06 10:07 pm
Достижение и в том, что построил, но в общем-то даже существование не кажется мне столь уж очевидным. Я не знаю, было ли оно доказано до этого построения.
(Ответить) (Parent) (Thread)
From: a_shen
2016-07-06 10:05 pm

кстати, более стандартное наблюдение,

но тоже не всем известное, если по очередь поворачивать правую грань, потом верхнюю, потом снова так же повернуть правую, потом снова верхнюю, то вполне в пределах человеческого терпения всё вернётся...
(Ответить) (Thread)
[User Picture]From: avva
2016-07-06 10:10 pm

Re: кстати, более стандартное наблюдение,

Я этим занимался на скучных уроках в школе. Помню, что период был неожиданный, кажется, 105 (собственно, 3x5x7, так что логично, но *тогда* мне эта мысль не была доступна).
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: norian
2016-07-06 10:13 pm
существуют последовательности, которые поворачивают центральные кубики граней или угловые кубики, не меняя положение остальных - собссно, так кубик и собирается в самом простом и не самом эффективном случае, насколько я помню

задача сводится к перебору всех положений этих кубиков, то есть множества известных последовательностей поворотов

(Ответить) (Thread)
[User Picture]From: avva
2016-07-06 10:22 pm
Мне непонятно, как, пользуясь таким методом, вы обеспечите непосещение дважды одного и того же положения кубика - такие повторы вполне могут случаться в процессе того, как, поворачивая кубик, вы временно меняете положение/ориетнацию других.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: occuserpens
2016-07-07 02:37 am
Если этот цикл такой здоровый, может быть, у него есть криптографическая ценность?
(Ответить) (Thread)
[User Picture]From: freedom_of_sea
2016-07-07 06:17 am

Шпионы с колодами карт были, шпионы с кубиками рубика в качестве шифроблокнотов.

(Ответить) (Parent) (Thread)
[User Picture]From: alaev
2016-07-07 05:28 am
- Наивные подходы, что приходят мне в голову, требуют очень много памяти

А как выглядят эти подходы?
(Ответить) (Thread)
[User Picture]From: xaxam
2016-07-07 05:59 am
>>> Даже *проверить*, что это действительно гамильтонов цикл, кажется не очень простой задачей, хоть автор и попытался ее упростить своей нотацией.

И это только "Р", а найти его - огого какой "NP"!
(Ответить) (Thread)
[User Picture]From: freedom_of_sea
2016-07-07 06:14 am

Почему он назыаается гамильтонов?

(Ответить) (Thread)
[User Picture]From: a_konst
2016-07-07 09:04 am
Простите, что Вас сдерживает от того, чтобы вбить в гугл "гамильтонов цикл"?
(Ответить) (Parent) (Thread)
[User Picture]From: david_2
2016-07-07 06:48 am
"Если один поворот занимает одну секунду, то в среднем кубик будет полностью собран за время, равное примерно 50 возрастам Вселенной на сегодняшний день"

"Хе, и я так могу" (с) Промокашка.
(Ответить) (Thread)
[User Picture]From: winpooh
2016-07-07 07:14 am
Простой расчёт показывает, что для кубика 2x2x2 (3.6 млн. состояний) понадобится дней 40-50. Вполне проверяемо.
(Ответить) (Thread)
From: (Anonymous)
2016-07-07 07:01 pm
В термодинамике есть аналогичная теорема о возвращении.
(Ответить) (Thread)
[User Picture]From: prionik
2016-07-12 12:06 am
Если долго мучиться то что-нибудь получится(с) народное
(Ответить) (Thread)