праздные размышления о лифтах
Jan. 31st, 2005 01:33 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaЗадача, порождённая опытом, скорее всего тривиальная.
Два человека договорились встретиться у определённого лифта, курсирующего между двумя этажами. На лестничной площадке есть два лифта, соединяющих эти этажи. Но они забыли договориться, на каком из этажей они встречаются. Один из них пришёл и думает: что если второй уже пришёл и ждёт на другом этаже? Спускается проверить, там второго нет; если он сейчас поедет обратно, что если второй уже пришёл и как раз в это время поедет на другой этаж на параллельном лифте? Что если они разминутся так один раз, а потом ещё и ещё? Ясно, что вероятность этого в реальной жизни ничтожна, но есть ли у них алгоритм, гарантирующий в любом случае, что они встретятся?
Ну, во-первых, ясно, что есть; например, они могут договориться заранее, что будут ждать друг друга на верхнем этаже, независимо от того, на какой из этажей вначале придут. Или что будут пользоваться для проверки определённым лифтом, одним из двух.
Значит, чтобы получить нетривиальную задачу, надо усложнить им жизнь. Предположим, что этажи невозможно отличить друг от друга, они выглядят идентично и совершенно симметрично относительно лифта (например, лифт горизонтальный, или всё это происходит в космическом пространстве, и у них нет возможности определить направление движения как "вверх" или "вниз"). Оба лифта тоже невозможно отличить один от другого (например, пусть площадка будет идеально круглая, и лифты находятся строго напротив друг друга, а то место на окружности, через которое они попадают на площадку, заранее неизвестно и может быть разным для обоих). Время поездки на лифте от одного этажа до другого полагаем для удобства фиксированным и небольшим по человеческим меркам; выйти/войти в лифт и осмотреться вокруг себя на площадке занимает ноль времени. Что тогда?
Всё равно легко; например, они заранее договариваются, что один из них будет стоять на месте, а другой - разъезжать туда-сюда; так они неизбежно встретятся. Поэтому надо ещё усложнить; заставим их следовать одному и тому же детерминированному алгоритму. Или, иными словами и более изощрённо-научно-фантастически, пусть это будет человек и его двойник. Человек должен заранее придумать алгоритм, потом его клонируют, и обе копии делают то же самое, т.к. они не могут отличить оригинал от копии.
Получилось у меня превратить это в сколько-нибудь нетривиальную задачу? Кажется, я сделал её нерешаемой; если они оба приходят в один и тот же момент на разные этажи, у них теоретически нет возможности встретиться.
Попробуем теперь немного упростить: пусть известно, что они приходят вначале на один и тот же этаж (но, как и раньше, ничего не известно о времени прихода; всего лишь то, что оба рано или поздно придут). Есть тогда тривиальное решение, которое я упускаю, или мне удалось сохранить немного сложности? Впрочем, то нетривиальное решение, которое я придумал для этого случая, всё равно не слишком сложное: после прихода каждый сначала ждёт одну минуту, потом едет на другой этаж, ждёт там две минуты, едет обратно, ждёт три итп (кажется, этого достаточно, и не надо использовать геометрический ряд в 1-2-4-8-16-... минут)
Возможно, есть ещё какие-то интересные варианты.
Два человека договорились встретиться у определённого лифта, курсирующего между двумя этажами. На лестничной площадке есть два лифта, соединяющих эти этажи. Но они забыли договориться, на каком из этажей они встречаются. Один из них пришёл и думает: что если второй уже пришёл и ждёт на другом этаже? Спускается проверить, там второго нет; если он сейчас поедет обратно, что если второй уже пришёл и как раз в это время поедет на другой этаж на параллельном лифте? Что если они разминутся так один раз, а потом ещё и ещё? Ясно, что вероятность этого в реальной жизни ничтожна, но есть ли у них алгоритм, гарантирующий в любом случае, что они встретятся?
Ну, во-первых, ясно, что есть; например, они могут договориться заранее, что будут ждать друг друга на верхнем этаже, независимо от того, на какой из этажей вначале придут. Или что будут пользоваться для проверки определённым лифтом, одним из двух.
Значит, чтобы получить нетривиальную задачу, надо усложнить им жизнь. Предположим, что этажи невозможно отличить друг от друга, они выглядят идентично и совершенно симметрично относительно лифта (например, лифт горизонтальный, или всё это происходит в космическом пространстве, и у них нет возможности определить направление движения как "вверх" или "вниз"). Оба лифта тоже невозможно отличить один от другого (например, пусть площадка будет идеально круглая, и лифты находятся строго напротив друг друга, а то место на окружности, через которое они попадают на площадку, заранее неизвестно и может быть разным для обоих). Время поездки на лифте от одного этажа до другого полагаем для удобства фиксированным и небольшим по человеческим меркам; выйти/войти в лифт и осмотреться вокруг себя на площадке занимает ноль времени. Что тогда?
Всё равно легко; например, они заранее договариваются, что один из них будет стоять на месте, а другой - разъезжать туда-сюда; так они неизбежно встретятся. Поэтому надо ещё усложнить; заставим их следовать одному и тому же детерминированному алгоритму. Или, иными словами и более изощрённо-научно-фантастически, пусть это будет человек и его двойник. Человек должен заранее придумать алгоритм, потом его клонируют, и обе копии делают то же самое, т.к. они не могут отличить оригинал от копии.
Получилось у меня превратить это в сколько-нибудь нетривиальную задачу? Кажется, я сделал её нерешаемой; если они оба приходят в один и тот же момент на разные этажи, у них теоретически нет возможности встретиться.
Попробуем теперь немного упростить: пусть известно, что они приходят вначале на один и тот же этаж (но, как и раньше, ничего не известно о времени прихода; всего лишь то, что оба рано или поздно придут). Есть тогда тривиальное решение, которое я упускаю, или мне удалось сохранить немного сложности? Впрочем, то нетривиальное решение, которое я придумал для этого случая, всё равно не слишком сложное: после прихода каждый сначала ждёт одну минуту, потом едет на другой этаж, ждёт там две минуты, едет обратно, ждёт три итп (кажется, этого достаточно, и не надо использовать геометрический ряд в 1-2-4-8-16-... минут)
Возможно, есть ещё какие-то интересные варианты.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2005-01-31 11:37 am (UTC)no subject
Date: 2005-01-31 11:38 am (UTC)no subject
Date: 2005-01-31 11:41 am (UTC)no subject
Date: 2005-01-31 11:44 am (UTC)They also serve who stand and wait.
no subject
Date: 2005-01-31 11:44 am (UTC)no subject
Date: 2005-01-31 11:52 am (UTC)no subject
Date: 2005-01-31 11:53 am (UTC)no subject
Date: 2005-01-31 11:53 am (UTC)no subject
no subject
Date: 2005-01-31 11:55 am (UTC)А бросание монетки в нормальном смысле не даст ничего - только алгоритм с вероятностью, стремящейся к 1.
no subject
Date: 2005-01-31 11:57 am (UTC)no subject
Date: 2005-01-31 11:59 am (UTC)no subject
Date: 2005-01-31 11:59 am (UTC)Если больше, то вариант с 1-2-3 и так далее решает задачу. Нужна всего лишь последовательность, "внутри" которой сколь угодно далеко от начала можно уложить сколь угодно длинный отрезок.
no subject
Date: 2005-01-31 12:01 pm (UTC)no subject
Date: 2005-01-31 12:05 pm (UTC)no subject
Date: 2005-01-31 12:14 pm (UTC)http://www.livejournal.com/community/hitech_tests/3841.html
no subject
Date: 2005-01-31 12:14 pm (UTC)no subject
Date: 2005-01-31 12:19 pm (UTC)no subject
Date: 2005-01-31 12:19 pm (UTC)no subject
Date: 2005-01-31 12:19 pm (UTC)Умеют ли они считать (достаточно знать последовательность чисел, операций не нужно) и могут ли задать лифту в какую сторону ехать и на сколько этажей?
В принципе: куча вариантов этой задачи рассматривается в стандартных курсах "online algorithms" или я что-то неуловила?
no subject
Date: 2005-01-31 12:23 pm (UTC)Варианты наверняка рассматриваются. Это не столько задача, сколько не вполне удавшаяся попытка взять ситуацию из реальной жизни и превратить её в нетривиальную задачу.
no subject
Date: 2005-01-31 12:24 pm (UTC)no subject
Date: 2005-01-31 12:24 pm (UTC):)
no subject
Date: 2005-01-31 12:25 pm (UTC)no subject
Date: 2005-01-31 12:31 pm (UTC)Хотелось бы, чтобы был какой-то способ формально сказать примерно следующее: алгоритм может работать только для случая, когда они приходят на один и тот же этаж, но они не должны об этом "заранее знать", т.е. алгоритм не может этим пользоваться. Но не очень ясно, можно ли такое формализовать. Нельзя ведь просто запретить им стоять на месте, понятно, потому что тогда они могут покататься пару раз для виду и потом замереть.
Может, попробовать посмотреть как алгоритм работает в случае прихода на разные этажи: предположим, алгоритм с этим случаем не справляется, но как он с ним не справляется? Есть алгоритмы, которые рано или поздно "замирают", типа алгоритма "стой на месте", а есть такие, которые бесконечно долго "бегут". Если запретить "замирающие" алгоритмы, и рассматривать только "энергичные", становится ли тогда задача, в случае прихода на один и тот же этаж, нетривиальной?