Алгоритмы без обратной связи (с сайта А.В.Шаповалова)

[Dendr]

Rak so dna в сообщении #1613871 писал(а):

полиция всегда догонит вора

Мне не дает тут покоя один момент: допустим, у угонщика есть бинокль. Он отъезжает от перекрестка на условное расстояние (например, на 1 планковскую длину) и следит за полицейскими - ему везет, и они гонятся не за ним. Как только они возвращаются и меняют направление, он спешит обратно в центр и тут же едет на другой луч и повторяет свои действия. Если все участники выбирают направление каждый раз случайно, то можно говорить о матожидании времени погони, но о том, что его поймают "наверняка" - как-то уже сомнительно.

[Rak so dna]

Dendr я про то, что процитировано, то бишь начальную задачу (для перекрёстка, я ничего количественно не оценил). А так да, в случае перекрёстка, видимо, надо уточнить, что вор тупо едет по одному из направлений.

Как вариант, можно, с учётом вашего варианта, поставить вопрос так:
Есть перекресток с тремя направлениями и полицией в центре. Полиция точно знает на каком расстоянии от неё сейчас вор, но не знает направления. При каких условиях (соотношения скоростей и расстояние) вор точно будет пойман?

[TOTAL]

Dendr в сообщении #1613873 писал(а):

Rak so dna в сообщении #1613871 писал(а):

полиция всегда догонит вора

Мне не дает тут покоя один момент: допустим, у угонщика есть бинокль. Он отъезжает от перекрестка на условное расстояние (например, на 1 планковскую длину) и следит за полицейскими - ему везет, и они гонятся не за ним. Как только они возвращаются и меняют направление, он спешит обратно в центр и тут же едет на другой луч и повторяет свои действия.

Полицейские одного из своих оставляют в засаде на перекрёстке. Спеши, милок, обатно в ценр, быстрее оприходуют.

[Rak so dna]

Rak so dna в сообщении #1613722 писал(а):

Коль уж все задачи ТС в той или иной степени решены, предлагаю доказать это:

Rak so dna в сообщении #1613676 писал(а):

если скорость вора меньше скорости полиции, то полиция может поймать вора и в случае перекрёстка с любым конечным количеством дорог.

Из центра перекрёстка по всем направлениям запускаем свои виртуальные копии со скоростями меньшими нашей, но большими скорости вора. Через некоторое (любое) время начинаем по очереди догонять свои копии. Очевидно, что мы их все догоним сколько угодно раз, но одна из них неизбежно обгонит вора, а значит и мы тоже.

Rak so dna в сообщении #1613880 писал(а):

Как вариант, можно, с учётом вашего варианта, поставить вопрос так:
Есть перекресток с тремя направлениями и полицией в центре. Полиция точно знает на каком расстоянии от неё сейчас вор, но не знает направления. При каких условиях (соотношения скоростей и расстояние) вор точно будет пойман?

Тут у меня получилось (внимательно не проверял), что если скорость вора более чем в три раза меньше скорости полиции — она его поймает.

[Dendr]

Rak so dna в сообщении #1613880 писал(а):

Есть перекресток с тремя направлениями и полицией в центре. Полиция точно знает на каком расстоянии от неё сейчас вор, но не знает направления. При каких условиях (соотношения скоростей и расстояние) вор точно будет пойман?

Я верно понимаю, что дороги считаются прямыми и с углом $120^o$ между ними? А полицейские знают численное значение максимальной скорости вора? Она, очевидно, меньше их скорости, иначе они его никогда не поймают.

И у меня получилось, что любая положительная разница (отличная от бесконечно малой) дает преимущество полицейским.

Пусть полицейские едут по одному из лучей с максимальной скоростью от центра. Если угонщик на этом луче и на его дальнем конце, что то расстояние обязательно будет сокращаться вплоть до нуля (в момент поимки). Если оно увеличивается, значит надо ехать назад, и вор точно не на этом луче. Таким образом, начальным положением в задаче можно считать положение: полицейские на перекрестке, знают расстояние до вора, но не уверены, на котором из двух лучей он находится.
Полицейские рассчитывают время, через которое вор вернется в центр, если начнет движение в этот самый момент, и начинают двигаться по одному из лучей под вопросом, не дольше половины этого времени. Но они так же, как и в первом случае, быстро узнают, что вор не на их луче, и вернутся в центр раньше, чем туда вернется он, после чего повернут на третий луч, и рано или поздно его догонят.

[Rak so dna]

Dendr полиция знает максимальную скорость вора и первоначальное расстояние до него. В процессе погони она, естественно, ничего про расстояние уже не знает.