?

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 ]

праздные размышления о лифтах [янв. 31, 2005|01:33 pm]
Anatoly Vorobey
Задача, порождённая опытом, скорее всего тривиальная.

Два человека договорились встретиться у определённого лифта, курсирующего между двумя этажами. На лестничной площадке есть два лифта, соединяющих эти этажи. Но они забыли договориться, на каком из этажей они встречаются. Один из них пришёл и думает: что если второй уже пришёл и ждёт на другом этаже? Спускается проверить, там второго нет; если он сейчас поедет обратно, что если второй уже пришёл и как раз в это время поедет на другой этаж на параллельном лифте? Что если они разминутся так один раз, а потом ещё и ещё? Ясно, что вероятность этого в реальной жизни ничтожна, но есть ли у них алгоритм, гарантирующий в любом случае, что они встретятся?

Ну, во-первых, ясно, что есть; например, они могут договориться заранее, что будут ждать друг друга на верхнем этаже, независимо от того, на какой из этажей вначале придут. Или что будут пользоваться для проверки определённым лифтом, одним из двух.

Значит, чтобы получить нетривиальную задачу, надо усложнить им жизнь. Предположим, что этажи невозможно отличить друг от друга, они выглядят идентично и совершенно симметрично относительно лифта (например, лифт горизонтальный, или всё это происходит в космическом пространстве, и у них нет возможности определить направление движения как "вверх" или "вниз"). Оба лифта тоже невозможно отличить один от другого (например, пусть площадка будет идеально круглая, и лифты находятся строго напротив друг друга, а то место на окружности, через которое они попадают на площадку, заранее неизвестно и может быть разным для обоих). Время поездки на лифте от одного этажа до другого полагаем для удобства фиксированным и небольшим по человеческим меркам; выйти/войти в лифт и осмотреться вокруг себя на площадке занимает ноль времени. Что тогда?

Всё равно легко; например, они заранее договариваются, что один из них будет стоять на месте, а другой - разъезжать туда-сюда; так они неизбежно встретятся. Поэтому надо ещё усложнить; заставим их следовать одному и тому же детерминированному алгоритму. Или, иными словами и более изощрённо-научно-фантастически, пусть это будет человек и его двойник. Человек должен заранее придумать алгоритм, потом его клонируют, и обе копии делают то же самое, т.к. они не могут отличить оригинал от копии.

Получилось у меня превратить это в сколько-нибудь нетривиальную задачу? Кажется, я сделал её нерешаемой; если они оба приходят в один и тот же момент на разные этажи, у них теоретически нет возможности встретиться.

Попробуем теперь немного упростить: пусть известно, что они приходят вначале на один и тот же этаж (но, как и раньше, ничего не известно о времени прихода; всего лишь то, что оба рано или поздно придут). Есть тогда тривиальное решение, которое я упускаю, или мне удалось сохранить немного сложности? Впрочем, то нетривиальное решение, которое я придумал для этого случая, всё равно не слишком сложное: после прихода каждый сначала ждёт одну минуту, потом едет на другой этаж, ждёт там две минуты, едет обратно, ждёт три итп (кажется, этого достаточно, и не надо использовать геометрический ряд в 1-2-4-8-16-... минут)

Возможно, есть ещё какие-то интересные варианты.
СсылкаОтветить

Comments:
[User Picture]From: cousin_it
2005-01-31 11:37 am
Если оба приходят на один этаж, то им достаточно просто сидеть и ждать.
(Ответить) (Thread)
[User Picture]From: avva
2005-01-31 11:44 am
Мда, я не выспался :(

They also serve who stand and wait.
(Ответить) (Parent) (Thread)
[User Picture]From: cousin_it
2005-01-31 11:38 am
Чуть-чуть интереснее задача становится, если они все же клоны, но имеют право бросать монетку.
(Ответить) (Thread)
[User Picture]From: bromozel
2005-01-31 11:41 am
Тогда все просто. Любой одинаковый алгоритм, но после нахождения монетки все надо делать быстрее в два раза.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: tananda_
2005-01-31 11:52 am
Есть варианты: Мобильная связь!
(Ответить) (Thread)
[User Picture]From: avva
2005-01-31 11:54 am

Собственно, в "реальной жизни" так и случилось (ну, почти; один набирал номер второго как раз в тот момент, когда второй вышел из лифта после проверки другого этажа и увидел первого).
(Ответить) (Parent) (Thread)
From: tat_sat
2005-01-31 11:53 am
Пусть оба следуют одному алгоритму: ждать случайное количество секунд (минут) на этаже, затем ехать на другой и так пока не встретятся.
(Ответить) (Thread)
[User Picture]From: jerom
2005-01-31 12:19 pm
Это не даёт вероятности встречи равной еденице.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: ypq
2005-01-31 11:59 am
почему-то мне это с первого взгляда напомнило ethernet (csma/cd)...
(Ответить) (Thread)
[User Picture]From: vyhuhol
2005-01-31 12:19 pm
Ага :)
(Ответить) (Parent) (Thread)
[User Picture]From: vyhuhol
2005-01-31 12:14 pm
(Ответить) (Thread)
[User Picture]From: avva
2005-01-31 12:24 pm
Спасибо, забавно ;)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: bionika_j
2005-01-31 12:14 pm
хорошо что я не езжу в лифте...:\
(Ответить) (Thread)
From: ex_ex_annut
2005-01-31 12:19 pm
Непоняла условие задачи?
Умеют ли они считать (достаточно знать последовательность чисел, операций не нужно) и могут ли задать лифту в какую сторону ехать и на сколько этажей?

В принципе: куча вариантов этой задачи рассматривается в стандартных курсах "online algorithms" или я что-то неуловила?
(Ответить) (Thread)
[User Picture]From: avva
2005-01-31 12:23 pm
Считать умеют. Этажей всего два, лифт едет от одного к другому без вариантов; можно считать, что лифт всегда наготове.

Варианты наверняка рассматриваются. Это не столько задача, сколько не вполне удавшаяся попытка взять ситуацию из реальной жизни и превратить её в нетривиальную задачу.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: mi_b
2005-01-31 12:37 pm
я думаю, что не вероятностного решения, т.е. за конечное время с вероятностью 1, для общей ситуации нет - непонятно, что помешает им кататься вслед друг за другом с небольшим сдвигов во времени.

Вероятностное, кажется, тривиально - собственно, если просто на каждом этаже бросать монетку и ехать вверх/вниз, то для любого числа этажей найдется время, такое, что вероятаность невстречи меньше любого наперед заданного эпсилон.
(Ответить) (Thread)
From: ex_ex_annut
2005-01-31 12:54 pm
Для детерминированного точно нет
Просто в силу симметрии
Ваш алгоритм дает исходя из теукщего состояния и истории (не имеет в данной задаче значения) время t через которое поменять состояние
Допустим два человека прибывает на разные этажи в один момент времени t_0
алгоритм в силу симметричности произведит одинаковые времена t_1
в t_0 + t_1 они поменяют состояния
условия (включая историю) опять симметричные и для перемены состояния оба героя произведут один и тот же t_2
и так далее
(Ответить) (Parent) (Thread)
[User Picture]From: proxor
2005-01-31 12:56 pm
вот ежели они приходят к лифтам в одно и тоже время, то можно решить так:
оба начинают кататься по этажам с интервалом минута,
но:
один катается через один этаж, а другой через два (циклически, пример для 5 этажного дома: первый приходит на первый этаж, второй на второй. для первого 1-2-3-4-5, для второго 2-4-1-3-5)

не более чем через 2Н пересекутся %))

(Ответить) (Thread)
From: ex_ex_annut
2005-01-31 12:58 pm
Авва говорил что нет "коммуникаций" и они симметричные - как выбрать кто минута, а кто две
иначе тривиально, конечно
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: kyookineko
2005-01-31 02:55 pm

Так у классика алгоритм уже описан :)

- Звучит страшно путано.
- Ну, это все довольно просто, лишь бы осилить теорию, - успокоил
Марвина Вальдец. - А теперь, чтобы гарантировать успех, нам надо выбрать
оптимальный принцип поиска. Самоочевидно, что, если оба будут активно
искать, вероятность того, что вы найдете друг друга, резко уменьшится.
Представьте себе, что двое ловят друг друга по бесконечным многолюдным
анфиладам универсального магазина; и сравните такой метод с
усовершенствованной стратегией, когда один ищет, а другой стоит на месте
и спокойно ждет, пока его найдут. Математически это формулируется
чрезвычайно сложно, вам придется поверить мне на слово. С наибольшей
вероятностью вы разыщете девушку или она разыщет вас, если кто-то один
будет разыскивать, а другой - позволит себя разыскать. Народная мудрость
так и гласит.
- Так что же будем делать?
- Я ведь вам твержу! - вскричал Вальдец. - Один должен искать, другой
- ждать. Поскольку мы не в состоянии держать поступки Кэти под
контролем, придется исходить из того, что она, следуя своему инстинкту,
разыскивает вас. Поэтому вы должны подавить свои инстинкты и ждать, тем
самым позволив ей вас найти.
- Ждать? Только и всего? - переспросил Марвин.
- Вот именно. - И вы серьезно думаете, что она меня найдет?
- Ручаюсь жизнью.
(Ответить) (Thread)
From: dmpogo
2005-01-31 04:10 pm
Da, my s docher'ju dogovorilis' eshe w dalekom detstwe - elsi
poterjaemsja - ona stoit na meste.

Kazhetsja uzhe pora peredogowariwat'sja :(
(Ответить) (Thread)