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

[rockclimber]

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

[Geen]

Вообще, игры обычно исследуются с конца...

[wrest]

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

Я вот даже картинку нарисовал. Думаю, идея понятна, хотя ее еще можно оптимизировать.

Конечно, можно. Если спрямить траекторию Утки

Смотрите: и на Утку и на Лису наседает ВРЕМЯ. Двигаясь от точки $C$ по криволинейной траектории, утка тратит какое-то время до точки $D$ на берегу. Двигаясь по прямой от точки $C$ до точки $D$, Утка тратит меньше времени, что для неё лучше.

-- 16.01.2018, 13:20 --

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

Что-то меня сейчас осенило: а разве это не одна и та же стратегия получается?

Конечно, одна, я об этом писал на 1 странице темы, выделил жирным:

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

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

-- 16.01.2018, 13:22 --

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

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

Я не отказался, я на этой идее настаиваю. Этот момент, когда надо начать двигаться по прямой, -- это второй момент. То есть начиная с момента $t=t_0$ где $t_0$ стремится к нулю справа.

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

[grizzly]

wrest
Что если с точки C на последнем рисунке Утка повернёт на юго-запад? Ровно настолько, что если Лиса начнёт возвращаться, то она пройдёт развёрнутый угол в тот момент, когда Утка будет за пределами внутреннего круга. Такое ощущение, что утка способна заставить Лису бегать по кругу (а Утка при этом будет удаляться от центра).

[wrest]

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

Такое ощущение, что утка способна заставить Лису бегать по кругу (а Утка при этом будет удаляться от центра).

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

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

[EUgeneUS]

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

Конечно, можно. Если спрямить траекторию Утки

У меня дежавю.
Помнится обсуждали аналогичную задачу, только там, АФАИР, был маяк и убегающий корабль\лодка.

1. Ровно тем же простым соображением пришли к выводу, что траектория утки\лодки должна быть отрезком прямой.
2. Простыми соображениями пришли к выводу, что этот отрезок прямой должен быть касательным к кругу безопасности.

[Dmitriy40]

Движение утки по прямой не оптимально по крайней мере в конце. Об этом говорил worm2, я взял и проверил численно.
Радиус озера равен $1$. Относительная скорость лисы $k=4{,}6$. Утка находится по координатам $(x,y)=(0, 0{,}9)$, лиса смещена вправо от будущей точки встречи на расстояние по окружности в $L=k(1-0{,}9)=0{,}46$, если утка продолжит движение строго прямо, то они встретятся в координатах $(0, 1)$. Предположим теперь что утка однократно отклоняется от прямого движения и отворачивает чуть влево и лисе придётся пробежать на $\delta=0{,}01$ больше, т.е. не $L\ne0{,}46$, а уже $L=0{,}47$. Вопрос какова длина прямого пути утки в новую точку встречи и меньше ли он $(1-y)+\delta/k=0{,}1+0{,}01/4{,}6\approx0{,}102174$? Считаем, путь утки оказывается $S\approx 0{,}10045$ - т.е. он меньше чем есть у неё времени до встречи с лисой. Т.е. она успевает в новую точку встречи раньше лисы.
Формулой указанный прямой путь утки выражается $S=\sqrt{(\cos\delta-y)^2+(\sin\delta)^2}$, где $y$ координата утки, $\delta$ предполагаемое увеличение пути лисы. Условие выигрыша утки: $S<\delta/k+L=\delta/k+(1-y)k$. Координаты новой точки встречи: $(x,y)=(-\sin\delta, \cos\delta)\ne(0,1)$ (в общем-то очевидно).
Итого, как минимум в конце утке выгоднее убегать от лисы по некоей непрямой траектории. Как worm2 и сказал.
Вид оптимальной траектории так и не знаю, но что-то нравится мне эвольвента ... без обоснований, просто нравится (прямым углом между чем-то там).

[rockclimber]

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

[wrest]

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

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

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

[rockclimber]

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

Движение утки по прямой не оптимально по крайней мере в конце.

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

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

Любая непрямая траектория длиннее чем прямая.

Непрямая траектория позволяет уменьшить разницу угловых скоростей - и тут уже надо считать.

[wrest]

EUgeneUS в сообщении #1284579 писал(а):

Помнится обсуждали аналогичную задачу, только там, АФАИР, был маяк и убегающий корабль\лодка.

Мне, кстати, тоже припомнается что-то такое с лодкой, и то ли это у Перельмана, то ли у Маковецкого, то ли у Гарднера было именно в формулировке с лодкой. А вот где было - не помню. Типа озеро круглое, посредине маяк, его угловая скорость такая-то, надо от маяка доплыть до берега (или от берега до маяка) не попав в луч маяка.

-- 16.01.2018, 14:05 --

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

Непрямая траектория позволяет уменьшить разницу угловых скоростей - и тут уже надо считать.

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

[Dmitriy40]

wrest
Я не спорю что кривая длиннее прямой. Но при любом взаимном положении утки и лисы (как минимум при приближении к берегу) утка может немного увеличить свой запас времени чуть отвернув с прямой траектории в сторону от лисы. Если посмотреть на расчёт, то в него не входит положение лисы, лишь увеличение её пути. Т.е. из любого положения (для достаточно больших $y$) существует другая прямая, кроме предыдущей, дающая преимущество утке во времени до новой точки встречи.

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

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

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

[EUgeneUS]

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

Я прямым вычислением показал, что сделав рывок не по кратчайшей траектории, утка увеличит свой запас времени.

Так утка\лодка и не движется по кратчайшей траектории к берегу. Утка\лодка стартует по касательной к кругу безопасности и приходит отнюдь не в ближайшую точку берега.

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

[wrest]

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

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

Это, повторюсь, означает только одно: существует единственная оптимальная траектория, и она - прямая.
Почему оптимальна именно касательная к "кругу безопасности"? Потому, что еще сильнее повернуть Утка не может, т.к. тогда она заплывает в "круг безопасности" после чего игра обнуляется, Лиса останавливается, а когда Утка из него выплывает, то Лиса, возможно, бежит уже в другую сторону (к Утке).

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

(раз его можно улучшить всего лишь однажды довернув в сторону в конце пути и продолжив движение по новой прямой).

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

Если Утка плывет по синей прямой как на рисунке выше, а Лиса бежит по красной дуге, то с Лисой в точку $D$ они прибывают одновременно. Числа у вас есть, попробуйте ;)

P.S. На самом деле ваши пояснения зародили во мне некоторые сомнения, но я думаю что прав, и числа все расставят по местам...

[EUgeneUS]

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