Лиса, Утка и озеро.

[Dmitriy40]

rockclimber в сообщении #1284329 писал(а):

Да просто двигаться в ту сторону, где расстояние по прямой между ней и уткой будет сокращаться.

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

[rockclimber]

wrest в сообщении #1284350 писал(а):

Но поскольку Утка уже за пределами внутреннего круга, её угловая скорость меньше чем угловая скорость Лисы, так что продолжая бежать против часовой стрелки, Лиса непрерывно сокращает угловое расстояние между собой и Уткой.

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

Ваш ход

-- 15.01.2018, 20:04 --

Dmitriy40 в сообщении #1284353 писал(а):

rockclimber в сообщении #1284329 писал(а):

Да просто двигаться в ту сторону, где расстояние по прямой между ней и уткой будет сокращаться.

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

Я тоже думал об этом, но с наскока такую задачу в общем виде не решу, а не с наскока думать лень.

[Dmitriy40]

rockclimber в сообщении #1284355 писал(а):

На шаг обратно влево лиса также отвечает шагом влево - потому что расстояние так опять сокращается.

Здесь неточность: по условию лиса реагирует быстрее утки в $k$ раз, так что может сделать не один, а $k$ шагов, в любую сторону. Ну чтобы не заморачиваться с разными расстояниями для утки и лисы. Это ещё больше усиливает Ваше возражение.

[wrest]

rockclimber в сообщении #1284355 писал(а):

На шаг обратно влево лиса также отвечает шагом влево - потому что расстояние так опять сокращается.

Неа, не сокращается. Именно поэтому Лиса опять шагает вправо. Для Лисы, в её положении после первого шага, шаг Утки обратно по прямой $CD$ в сторону $D$ будет шагом вправо! Как только Утка сделала первый шаг вправо, то всё, она всегда находится справа от Лисы (Лиса смотрит на центр озера).
Вот начальная траектория Утки:

[Sender]

wrest в сообщении #1284350 писал(а):

Sender в сообщении #1284348 писал(а):

А если лиса будет бежать ровно с такой скоростью, чтобы прибыть к месту встречи одновременно с уткой?

Есть ограничения на скорость Лисы: её скорость не больше чем в k раз больше максимальной скорости Утки, максимальная скорость Утки равна единице, радиус озера равен единице.

Хотите сказать, что в ситуации

wrest в сообщении #1284344 писал(а):

Смотрите: Утка, подплыв почти к берегу, разворачивается плывет к центру со своей половинной скоростью, Лиса бежит вокруг, к точке куда направляется Утка, и когда Лиса оказывается напротив, через центр, Утка разворачивается и плывет с полной скоростью к берегу.

лиса не сможет придерживаться описанной стратегии, если её максимальная скорость в k раз больше максимальной скорости утки?

[wrest]

Sender в сообщении #1284364 писал(а):

лиса не сможет придерживаться описанной стратегии, если её максимальная скорость в k раз больше максимальной скорости утки?

Смотря что значит "описанная стратегия". Та которая описана тут:

grizzly в сообщении #1284332 писал(а):

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

- проигрышная. Под "внутренним кругом", надеюсь, все понимают круг радиуса $1/k$

[Dmitriy40]

Dmitriy40 в сообщении #1284353 писал(а):

Помнится тут существует решение со спиральным движением утки, заставляющем лису много-много раз обежать озеро.

Эх, возможно я что-то напутал и спираль нужна лишь во внутреннем круге. Критерия расширения внутреннего круга до внешнего не помню (что вроде бы и даст предельное отношение скоростей), а выводить лень.

[wrest]

Dmitriy40 в сообщении #1284367 писал(а):

Эх, возможно я что-то напутал и спираль нужна лишь во внутреннем круге.

Да. Поэтому события внутреннего круга ("безопасной окружности") мы опускаем, и говорим о начальной (стартовой позиции) как на рисунке:

wrest в сообщении #1284304 писал(а):

На картинке ниже большая окружность - озеро, радиус 1. Малая окружность - "безопасная окружность", радиус $1/k$.
$B$ - начальное положение Лисы,
$C$ - начальное положение Утки,

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

[worm2]

Идея wrest нравится мне всё больше и больше.
Как я её понял: для каждого расстояния утки от центра существует минимаксное "угловое расстояние" между уткой и лисой: минимально возможное для лисы при безупречной игре утки, оно же максимально возможное для утки при безупречной игре лисы. Внутри "круга безопасности" это расстояние равно 180 градусам. А вот для расстояний, больших радиуса "круга безопасности", похоже, стратегия лисы заключается в непрерывном его сокращении. Если она попытается угадать конечную точку маршрута утки и, стремясь туда сразу, будет локально увеличивать угловое расстояние, то он неизбежно пройдёт обратно через 180 градусов. В этот момент утка торжествует: она локально обыграла лису, удалившись от неё на угловое расстояние, невозможное при оптимальной игре лисы (в этот момент утка меняет свой первоначальный план на зеркально противоположный). Поскольку от предыстории результат никак не зависит, то локальный успех увеличивает успех глобальный (т.е. можно применить принцип динамического программирования).
Оптимальную же стратегию за утку я ещё не просёк: у неё больше степеней свободы. Мне пока не ясно, будет ли для неё оптимальной траекторией прямая, или всё-таки кривая похитрее. Ясно только, что встретиться с берегом утке выгодней под каким-то углом, отличным от прямого: для траектории с прямым углом малое отклонение в сторону, противоположную от лисы, даёт прирост финального удаления от лисы такого же порядка малости, но прирост дистанции, которую необходимо проплыть дополнительно — квадратичного порядка малости.

[wrest]

worm2 в сообщении #1284375 писал(а):

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

Да, именно об этом я и говорю. Поскольку за пределами "круга безопасности" угловая скорость Лисы больше чем угловая скорость Утки, то стратегия Лисы -- сокращать угол между ней и Уткой до нуля, после чего судьба Утки предрешена, а значит Лисе надо бежать на максимальной скорости в ту сторону, по которую находится Утка в данный момент времени от прямой соединяющей Лису и центр озера. В начальной/стартовой позиции, если Утка вдруг решила поплыть прямо к берегу, направление бега Лиса может выбрать случайно.
Как только Утка заплывает обратно в "круг безопасности", Лиса останавливается (это всем облегчает жизнь: Утке для выхода на стартовую позицию, Лисе чтобы не тратить энергию на бесполезную беготню).

-- 15.01.2018, 19:54 --

worm2 в сообщении #1284375 писал(а):

Оптимальную же стратегию за утку я ещё не просёк:

Ну в целом её стратегия обратна стратегии Лисы: увеличивать угол (или, что тоже самое, замедлять его уменьшение) продвигаясь к берегу до момента когда Лиса уже никак не успевает её поймать, затем плыть прямо к берегу. Так что в "классическом" случае когда $k=4$ Утке не нужно выходить на точку именно $1/4$ т.к. это требует бесконечной спирали, а можно начать плыть прямо к берегу немного раньше, в конечный момент времени. Нарисованная мной траектория Утки не оптимальна, и в этом собственно вопрос задачи - какая оптимальна.

[Dmitriy40]

worm2 в сообщении #1284375 писал(а):

Оптимальную же стратегию за утку я ещё не просёк: у неё больше степеней свободы. Мне пока не ясно, будет ли для неё оптимальной траекторией прямая, или всё-таки кривая похитрее.

Мне вот тоже упорно кажется что есть траектория пооптимальнее. Может быть плыть всегда под прямым углом к направлению на лису. Или не под прямым, а как-то связанным с $k$. Ну и тут очевидно получится та спираль (или эвольвента? в общем что-то кривое ), о которой отложилось в голове.

wrest
Совет: в начале утке можно плыть строго от лисы. А как только та сдинется в любую сторону - в сторону увеличения угла между ними. Это приводит к Вашему же решению, просто не нужна та оговорка про первый шаг (в случайном направлении) и мгновенный разворот.

[wrest]

Dmitriy40 в сообщении #1284383 писал(а):

Совет: в начале утке можно плыть строго от лисы. А как только та сдинется в любую сторону

Лиса сдвинется в какую-то сторону в первый момент времени: в ту же сторону, что и Утка, если Утка поплывет в какую-то сторону, и в случайную сторону, если Утка поплывет прямо на берег.

Dmitriy40 в сообщении #1284383 писал(а):

Это приводит к Вашему же решению, просто не нужна та оговорка про первый шаг (в случайном направлении) и мгновенный разворот.

Ну за малостию дифференциала положения Утки, это все равно. Но да, тов. rockclimber будет трудней теоретизировать :)

Слышите, rockclimber? Первым ходом Утка ходит прямо на Север!

-- 15.01.2018, 20:14 --

Dmitriy40 в сообщении #1284383 писал(а):

Может быть плыть всегда под прямым углом к направлению на лису.

Тогда, как мне кажется, начиная прямо со стартовой точки, Утка будет плыть по "безопасной окружности" вечно.

[Dmitriy40]

wrest в сообщении #1284387 писал(а):

Тогда, как мне кажется, начиная прямо со стартовой точки, Утка будет плыть по "безопасной окружности" вечно.

Ну да, прямой угол не подходит. Может быть решение задачи уже давно найдено в теории наведения ракет? Там тоже есть некий угол прицеливания, он тоже связан с отношением скоростей, и там уже доказана оптимальность (по разным критериям) всех возможных стратегий. Это я про угол/траекторию утки.

[Geen]

1. Утке надо, по хорошему, запретить уменьшать радиус - иначе циклы и бесконечая игра.
2. Лисе всё равно куда плывёт утка - ей надо уменьшать угол с максимальной скоростью.
3. Утке надо плыть так, чтобы её угловая скорость относительно лисы была "максимальна".
4. Помнится, уже была такая задача

[wrest]

Dmitriy40 в сообщении #1284394 писал(а):

Может быть решение задачи уже давно найдено в теории наведения ракет?

Да нет, тут должно быть всё проще. Самая короткая траектория из точки А в точку Б - прямая. Любая криволинейность могла бы понадобиться Утке только для того, чтобы управлять направлением движения Лисы, а вернее - её положением. И это применимо внутри "круга безопасности", поскольку там угловая скорость Утки больше чем угловая скорость Лисы.
Но поскольку мы договорились облегчить обоим животным жизнь, то у нас Лиса просто стоит на месте если Утка внутри "круга безопасности", и бежит на максимальной скорости в сторону сокращения угла между Лисой и Уткой если Утка выплыла из "круга безопасности". Такая стратегия Лисы кажется оптимальной. Тогда, очень похоже на то, что траектория Утки которую я показал в первом посте и есть глобальный максимум в этой задаче, т.к. наклониться больше чем на 90 градусов к окружности и не пересечь её Утка не может. Максимум -- 90 градусов, т.е. касательная, и этот случай как раз разобран в стартовом посте.