?

Log in

полезно в хозяйстве - Поклонник деепричастий [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:10 pm

а из чего это

существование следует? есть какие-то общие причины?
(Ответить) (Parent) (Thread)
[User Picture]From: francis_drake
2016-07-06 11:35 pm

Re: а из чего это

В тексте поста не хватает пояснения, что в гамильтоновом пути нет петель.
(Ответить) (Parent) (Thread)
[User Picture]From: gegmopo4
2016-07-07 11:47 am

Re: а из чего это

«проводит кубик сквозь все возможные конфигурации, посещая каждую ровно один раз»
(Ответить) (Parent) (Thread)
[User Picture]From: francis_drake
2016-07-07 12:29 pm

Re: а из чего это

Теперь хватает.
(Ответить) (Parent) (Thread)
From: huzhepidarasa
2016-07-10 06:21 am
Royle's conjecture: "All Cayley graphs are Hamiltonian".
(Ответить) (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: utnapishti
2016-07-06 11:21 pm

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

И тут, естественно, доказательство (того, что кгда-нибудь вернёмся к исходному положению) практически элементарное - кажется, нетрудно сформулировать вообще без математических терминов.
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2016-07-07 06:37 am
цимес этой теоремы в "пределах терпения", то есть существование разумной оценки на количество шагов. Это элементарно? Мне например сразу вот так не очень ясно, откуда там пятёрка выскакивает. Семёрка и тройка вроде понятно.
(Ответить) (Parent) (Thread)
[User Picture]From: utnapishti
2016-07-07 09:30 am
Прежде всего, заметь, что, если ты по очереди крутишь две грани с общим ребром (каждую из них всегда в одну и ту же сторону), есть два способа это делать. В одном из них (более естественном анатомически - каждая грань крутится по часовой стрелке, если смотреть на неё снаружи), орбиты собственно кубиков имеют длину 7 и 5 (пар движений) - 7 у срединных, 5 у угловых. (Есть один угловой кубик, у которого оно вовсе 1, что ничему не мешает.) Соответственно, после 35 пар движений все кубики возвращаются на место. По-видимому, угловые при этом провернулись на 120 градусов, поэтому нужно повторить 3 раза, пока всё точно встанет на место.
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2016-07-07 09:41 am
мне это представляется ацки сложным. Таки наверное проще выписать в явном виде обе перестановки (угловых и рёберных) и пересчитать в ней циклы. И заметь ещё: вот углы-то ПО-ВИДИМОМУ повернулись (на самом деле это как раз сразу видно --- тот твой туда-сюдашный уголок, который неподвижная точка таки крутится, то есть он и требует множителя 3, а на остальных тогда можно наплевать, раз хоть про одного знаем, что крутится), а вот из рёберных никто не перекувырнулся? ну раз ответ нечётный, то конечно нет, но если заранее ответа не знать, то задолбаешься за ними следить. Ну и вообще, начали с "элементарно" и договорились до "орбит", хе-хе. Кстати мне "анатомически" больше нравится другой, без неподвижных точек, там такой же ответ?
(Ответить) (Parent) (Thread)
[User Picture]From: utnapishti
2016-07-07 11:31 am
Да чего там аццкого, вот все циклы, что есть.



Про рёберные кубики ты прав, но наверняка там какой-нибудь инвариант несложный; и про угловые тоже прав - я сам это понял, когда шёл с обеда (в смысле, что ТОТ кубик провернётся). Но вот что касается "начали с "элементарно", а договорились до орбит", так я только по поводу того говорил "элементарно", что вернёмся к исходному положению, а не по поводу того, сколько нужно шагов. (Да и орбиты-то тут довольно гнилые, единственное математическое понятиэ, которое тут нужно, это эл-си-эм).

Во втором, кажется, на 5 ничто не делится.
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2016-07-07 11:36 am
эл-си-эм это мы не проходили, это нам не задавали. А, ну про "вернёмся к исходному положению" это конечно элементарно: нарисуем точечками все положения и давай стрелочками их соединять, как пришли туда, где уже бывали, то либо это и есть исходное, либо имеем рисунок: из двух точечек ведут стрелочки в третью, но это противоречие, потому что по стрелочкам можно ж задним ходом ездить.

А с инвариантами такое дело: когда они есть, они все несложные, а когда он нужен, но его не видать, то охрененно сложная задача ;)

Edited at 2016-07-07 11:38 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: utnapishti
2016-07-07 11:46 am
Для тех, кто не проходил эл-си-эм, в данном случае можно соврать, что это просто пэ (ну или пи): 1*3*5*7, оппа! А тем, кто ищет во всём высший смысл, предложим подумать, нет ли какой-нибудь особенной причины, по которой это произведение первых идущих подряд нечётных чисел! - "А может быть, для кубика 4х4х4 это будет 1*3*5*7*9*11 ???"
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2016-07-07 12:47 pm
ты меня своей математической ересью не путай, для 4-кубика будет ровно то же, что и для стандартного кубика
(Ответить) (Parent) (Thread)
[User Picture]From: utnapishti
2016-07-07 12:57 pm
Oh, Herr Krämer, hier entsteht wohl grad' eine Verallgemeinerung!
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2016-07-07 01:05 pm
Ну чо, пиши статью, не забудь указать благодарность уютной жежешечке на предоставленную коллаборативную платформу и моей конторе за предоставление средств на пропитание одного из автороф
(Ответить) (Parent) (Thread)
[User Picture]From: utnapishti
2016-07-07 01:12 pm
хе-хе, статья то маааленькая (это намёк на мультфильм про говорящую рыбу, если что)
думаю, примерно двумя словами можно обойтись
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2016-07-07 02:20 pm
смотри, научная задача. Типа дана матрица NxM записанная в одномерный массив по строкам. А хочется её иметь записанной в тот же массив по столбцам. Дальше три варианта (а) дополнительной памяти дано O(NM) но с малой константой (б) её дано ровно NM бит + O(1) и наконец (в) её дано просто O(1). Все три варианта абсолютно тривиальны, но имеется реферируемый математический журнал (из матскинета), который в 200х году про это опубликовал статью каких-то испанских овощей. Так что вот.
(Ответить) (Parent) (Thread)
[User Picture]From: gaz_v_pol
2016-07-07 12:44 pm
Подумал над Вашей задачей. А правильно ли будет понимать, что длина периода разная в зависимости от того, поворачиваем ли мы верхнюю грань направо или налево? Вроде бы получается 63 и 105, если я не ошибся при подсчете без кубика.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2016-07-07 02:30 pm
Без кубика это слишком сложно для меня :) но да, я помню что период разный в этих двух случаях, только не помню, действительно ли 63.
(Ответить) (Parent) (Thread)
[User Picture]From: gaz_v_pol
2016-07-23 02:41 pm
До кубика так и не добрался, но ехал долго в электричке и проверил еще раз в уме -- вроде бы правильно, 63 и 105. Естественно, в уме надо не 63 действия делать (это вряд ли кто-то в уме способен сделать), а только:

7 для угловых кубиков, игнорируя, что происходит с боковыми (и тогда видно, что через 9 таких операций угловые вернутся на круги своя)

(теперь эту первую часть можно забыть)

9 для боковых кубиков, игнорируя, что происходит с угловыми (и тогда видно, что через 7 таких итераций боковые вернутся в исходное положение)
(Ответить) (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: norian
2016-07-06 11:03 pm
то есть нужно не только гарантировать все комбинации, а избежать их повторения

это сложнее, да :о))


(Ответить) (Parent) (Thread)
[User Picture]From: avva
2016-07-06 11:09 pm
Да. Я забыл это упомянуть? Упс :) сейчас исправлю.
(Ответить) (Parent) (Thread)
[User Picture]From: occuserpens
2016-07-07 02:41 am
Потому как Гамильтоновский
(Ответить) (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: occuserpens
2016-07-08 01:09 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: musatych
2016-07-08 06:00 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)