Ну, предположим, одному роботу выдан бит 1, другому бит 0. Понятно что, неизвестно, кому какой. Ваши действия?
Ну как хозяин журнала кажется и предполагал – скармливаем этот бит в качестве затравки хорошему генератору случайных чисел (конгруэнтные и мультипликативные не предлагать, а shift-register, например, сойдёт) и устраиваем 1D случайное блуждание (алгоритм будет эффективнее, если шаг небыстро растёт со временем, но не будем лезть в такие детали). 1D случайное блуждание – возвратно, т.ч. они встретятся с вероятностью 1, если проживут достаточное время. Дальше детали – можно, например, оценить вероятность p(L, T), того, что они сумеют встретиться, если расстояние между ними L, а время жизни робота – T. Ну и т.п.
Я утверждаю, что если расстояние между роботами достаточно велико, то они все равно друг друга найдут с вероятностью <=1/2
А если расстояние – световой год, то они не встретятся вобще – сломаются раньше.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2007-08-04 05:19 am (UTC)Ну как хозяин журнала кажется и предполагал – скармливаем этот бит в качестве затравки генератору случайных чисел (конгруэнтные и мультипликативные не предлагать, а shift-register, например, сойдёт) и устраиваем 1D случайное блуждание (алгоритм будет эффективнее, если шаг небыстро растёт со временем, но не будем лезть в такие детали). 1D случайное блуждание – возвратно, т.ч. они встретятся с вероятностью 1, если проживут достаточное время. Дальше детали – можно, например, оценить вероятность p(L, T), того, что они сумеют встретиться, если расстояние между ними L, а время жизни робота – T. Ну и т.п.
А если расстояние – световой год, то они не встретятся вобще – сломаются раньше.