задача

[juan_gandhi]

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

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

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

Comments

[kot-ivanovich.livejournal.com]

No, I would be quite happy with 1 different bit and a good random number generator. Well, they all have their periods of course (pun not intended), but it's not really a problem to find one that suffice for the lifetime of a robot.

[malaya-zemlya.livejournal.com]

Periods are important, if the robots are _very_far_.

Two things happen if you have a finite number of bits:

1. With a finite probability both robots get same random number and therefore act in sync and never meet each other. For 1 random bit per robot this probability is, of course, 1/2.

2. If robots have finite memory (a reasonable assumption, i think) then at some point their behavior would cycle. If they are far enough (d > 2^memory size) from each other they won't be able to meet in one cycle. Instead they would get closer (with probability = 1/2) or further apart (also probability 1/2).

In other words, their chances of meeting are not greater than 1/2.

[kot-ivanovich.livejournal.com]

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

[malaya-zemlya.livejournal.com]

Ну, предположим, одному роботу выдан бит 1, другому бит 0. Понятно что, неизвестно, кому какой. Ваши действия?

Я утверждаю, что если расстояние между роботами достаточно велико, то они все равно друг друга найдут с вероятностью <=1/2

[kot-ivanovich.livejournal.com]

Ну, предположим, одному роботу выдан бит 1, другому бит 0. Понятно что, неизвестно, кому какой. Ваши действия?

Ну как хозяин журнала кажется и предполагал – скармливаем этот бит в качестве затравки хорошему генератору случайных чисел (конгруэнтные и мультипликативные не предлагать, а shift-register, например, сойдёт) и устраиваем 1D случайное блуждание (алгоритм будет эффективнее, если шаг небыстро растёт со временем, но не будем лезть в такие детали). 1D случайное блуждание – возвратно, т.ч. они встретятся с вероятностью 1, если проживут достаточное время. Дальше детали – можно, например, оценить вероятность p(L, T), того, что они сумеют встретиться, если расстояние между ними L, а время жизни робота – T. Ну и т.п.

Я утверждаю, что если расстояние между роботами достаточно велико, то они все равно друг друга найдут с вероятностью <=1/2

А если расстояние – световой год, то они не встретятся вобще – сломаются раньше.

[malaya-zemlya.livejournal.com]

Даже если роботы не ломаются, любой псевдо-случайный генератор имеет период, это не даст роботам найти друг друга в общем случае. Ограничение это имеет порядок d_max = O(2^кол-во бит) Если есть ограничение по времени, то максимальное расстояние имеет порядок d_max = O(t^(1/2))

Что важнее, дело вкуса, конечно

Гы. если уж начать учитывать физику, то совсем все просто становится. Если можно кидаться предметами, то все просто, если нельзя - то сдвинуться с места никак не получится.

[kot-ivanovich.livejournal.com]

Поскольку в L = O(2^N) (L – период генератора, N – длина состояния генератора в битах), N находится под управлением программиста – это такое слабое ограничение, что мне о нём было лень думать. Но если Вы настаиваете – пожалуйста. Я брожу с шагом 1 пока не выберу период, возвращаюсь в начало и начинаю бродить с шагом, вдвое большим, чем предыдущий. И т.д. Вероятность того, что они не встретятся, наверное, останется (выполняя случайные танцы можно увернуться друг от друга даже в 1D), но она будет, я думаю, O(2^(-L/x)), где x – некоторое число, а не 1/2.

Ну или, как я уже говорил, можно медленно растить шаг по времени, log(t) точно подойдёт, можно, наверное, и степень подобрать.

[malaya-zemlya.livejournal.com]

Чтобы ходить с шагом x нужно все равно иметь где-то счетчик на log(x) бит.

А доказывается, что вероятность меньше 1/2 так:
Роботы в паре образуют конечный автомат (на 2*x битов). Автомат начинает путешествовать в неизвестной точке d (где d - исходное расстояние между роботами) и ему надо найти 0. Поскольку число доступных битов ограничено, то в какой-то момент состояния обеих роботов зациклятся, при этом они могут оказаться ближе, чем сначала (и тогда в конце концов встречаются), либо нет (тогда встреча им не светит). Для каждого варианта, когда они сближаются, существует вариант, когда они удаляются (роботов меняем местами и запускаем с теми же исходными данными), отсюда вероятность успеха никак не может быть больше 1/2

[kot-ivanovich.livejournal.com]

Oh, dear...

Чтобы ходить с шагом x нужно все равно иметь где-то счетчик на log(x) бит.

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

А доказывается, что вероятность меньше 1/2 так...

Вы не очень прочли, что я написал. ОК, подробнее: перейдя в систему координат одного из роботов, мы получаем процесс случайных блужданий статистически эквивалентный каноническим случайным блужданиям, с шагом 2 и частотой 1/2. Давайте забудем про эти двойки для простоты – такие мелочи нас сейчас не волнуют. Период совместного генератора двух роботов всё равно L (а не L², кстати). Допустим, что исходное расстояние между роботами d = 1. Какова вероятность того, что они разминутся? При L >> 1 это просто вероятность невозврата в начало координат, т.е., кажется, exp(-L^1/2) (тут я мог слегка наврать – нет учебника под рукой, а искать в сети лень). Это не ноль, но это фантастически маленькое число для любого разумного L. А если d > 1 то вероятность всё равно такая же, поскольку по исчерпании цикла я удваиваю шаг. Всё.