2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 4, 5, 6, 7, 8, 9, 10 ... 27  След.
 
 Re: Лиса, Утка и озеро.
Сообщение23.01.2018, 17:21 
Заслуженный участник


09/02/06
4382
Москва
Оптимальная стратегия для утки.
Вначале выходит на точку отстоящую на $\frac{1}{k}$ от центра (радиус озера 1, скорость утки 1. скорость лисы - k), противоположную от лисы.
Далее скорость утки всегда направлено под углом $\psi : \ \sin\psi=\frac{1}{kr}$ к ближайшей точке окружности, здесь r - величина удаления от центра.
Лиса не поймает утку, если $k < k_{\max}=\frac{1}{\cos \alpha}$, где $\alpha$ находится из трансцендентного уравнения:
$$\tg \alpha -\alpha =\pi.$$

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение23.01.2018, 19:22 


05/09/16
11469
Руст в сообщении #1286826 писал(а):
Лиса не поймает утку, если $k < k_{\max}=\frac{1}{\cos \alpha}$, где $\alpha$ находится из трансцендентного уравнения:
$$\tg \alpha -\alpha =\pi.$$

Из этого уравнения находится угол около $77,5$ градусов и $k_{max}\approx 4,603$
Это же значение $k_{max}\approx 4,603$ находится из рассмотрения движения Утки по прямой (касательной к кругу безопасности) как решение уравнения
$\sqrt{1-\dfrac{1}{k_{max}^2}}=\dfrac{\dfrac{3\pi}{2}-\arcsin \dfrac{1}{k_{max}}}{k_{max}}$

Значит вот это:
Руст в сообщении #1286826 писал(а):
скорость утки всегда направлено под углом $\psi : \ \sin\psi=\frac{1}{kr}$ к ближайшей точке окружности, здесь r - величина удаления от центра.
должно быть прямой линией, так?
А непохоже.

Можете изложить решение, ибо имеются фундаментальные сомнения, в связи с тем что прямая всегда короче кривой, в правильности выбранной вами для Утки траектории?

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение23.01.2018, 19:45 
Заслуженный участник


20/08/14
11067
Россия, Москва
Хоть формула для $k_{\max}$ даёт то же самое число, но вот вид кривой вызывает сомнения. Я её численно промоделировал для $k=4{,}6$, получилось что утка совершает поворот на $180°$, проходя при этом дистанцию $2{,}191$ единиц. Но лиса при этом проходит $360°$ окружности, что для неё составляет лишь $6{,}2832$ единиц длины, что очевидно меньше чем $2{,}191 \cdot 4{,}6=10$. Т.е. лиса успевает в точку встречи намного раньше утки. Беда однако.
PS. Числа длины путей округлил.
PPS. Код на PARI/GP:
Код:
{k=4.6; r=1/k; x=0; y=r; l=0.0; dl=0.0001;\\dl - шаг итераций пути утки, при этом выдаёт 2МБ текста
while(r<1,
   if(x==0,a=Pi/2;if(y<0,a=3*a),a=atan(y/x));if(x<0,a+=Pi);\\a - угол в текущую точку
   aa=a+acos(1/k/r);\\aa - угол траектории в следующую точку из текущей
   x+=cos(aa)*dl; y+=sin(aa)*dl; r=sqrt(x^2+y^2); l+=dl;\\новые координаты и радиус и путь утки
   print("r=",r,", L=",l,", a=",a*180/Pi,", aa=",aa*180/Pi,", x,y=",x,",",y);
);}
Его выдача:
Используется синтаксис Text
r=0.217391304, L=0.000000000000, a=90.0000000, aa=90.0000000, x,y=0,0.217391304
r=0.217491304, L=0.000100000000, a=90.0000000, aa=90.0000000, x,y=0,0.217491304
r=0.217591258, L=0.000200000000, a=90.0000000, aa=91.7375340, x,y=-3.03210420E-6,0.217591258
r=0.217691167, L=0.000300000000, a=90.0007984, aa=92.4572899, x,y=-7.31956951E-6,0.217691166
...
r=0.646223652, L=0.851600000, a=180.005047, aa=250.346131, x,y=-0.646223635,-0.000151100533
...
r=0.999999899, L=2.19080000, a=269.748330, aa=347.192193, x,y=-0.00429485150,-0.999990676
r=1.00002164, L=2.19090000, a=269.753922, aa=347.198063, x,y=-0.00419733731,-1.00001283


-- 23.01.2018, 19:52 --

wrest
Замена $\arccos$ на $\arcsin$ в формуле угла (как поправлено в сообщении) даёт движение утки по прямой указанной Вами в самом первом сообщении (с постоянным $y$). Т.е. выходит что эта страшная формула траектории даёт ту самую прямую, которую сильно проще получить геометрически ...

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение23.01.2018, 20:23 
Заслуженный участник


09/02/06
4382
Москва
Да, это получается прямой линией.
Пусть утка находится на расстоянии $r\ge \frac{1}{k}$ и направление скорости имеет угол $\psi$ с радиус вектором.
Тогда за время $\Delta t$ она удаляется от центра на расстояние $\Delta r =\Delta t \cos \psi$ и угол отклонения от лисы увеличивается на
$\Delta \phi =\Delta t \sin \psi /r -k\Delta t$. Здесь вычли уменьшение угла за счет скорости Лисы.
Угол скорости $\psi$ оптимально, если $\frac{\Delta r}{\Delta \phi}$ максимально. Отсюда получается указанное соотношение.

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение23.01.2018, 23:04 


05/09/16
11469
Руст
Спасибо. А что насчет эллипса скажете?

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение24.01.2018, 09:57 


05/09/16
11469
Dmitriy40 в сообщении #1286884 писал(а):
Т.е. выходит что эта страшная формула траектории даёт ту самую прямую, которую сильно проще получить геометрически ...

По сути мы имеем "мгновенную" стратегию Утки, т.е. можем рассматривать $k$ не как константу, а как функцию от времени $k(t)=v(t)$, по сути текущую скорость Лисы. Тогда вопрос. Если Лиса знает что у Утки вот такая стратегия, может Лиса догнать Утку или хотя бы сделать так что Утка не доплывет до берега?
Из
Руст в сообщении #1286894 писал(а):
угол отклонения от лисы увеличивается на
$\Delta \phi =\Delta t \sin \psi /r -k\Delta t$. Здесь вычли уменьшение угла за счет скорости Лисы.
Угол скорости $\psi$ оптимально, если $\frac{\Delta r}{\Delta \phi}$ максимально.

следует что если например Лиса остановилась, то есть $k(t)\Delta t=0$, то $\psi(t)=0$
Это значит, что пока Лиса стоит, Утка плывет вдоль радиуса?
Что будет если $k(t)>k_{max}$? По идее, тогда Утка должна двигаться удаляясь от берега?

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение24.01.2018, 10:40 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Наверное, нужно ещё раз напомнить про критерий успешности для Утки.
Если, например, у Утки критерий — минимизация времени доплытия до берега при условии, что Лиса её не ловит, то все рассуждения в этой теме нужно выкинуть и решать задачу заново.
Так что давайте лишний раз чётко заявим, что у Утки тот же критерий, что и у Лисы — расстояние между животными в момент достижения Уткой берега (Лиса пытается его минимизировать, а Утка — максимизировать).
Так вот, оптимальной траекторией для Утки после достижения "окружности безопасности" будет прямая, являющаяся касательной к этой окружности только если Лиса ведёт себя оптимально, т.е. несётся с максимальной скоростью в одном и том же направлении (в каждый момент времени сокращающем расстояние до Утки).

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

Правда, когда Вы пишете:
wrest писал(а):
... если $k(t)>k_{\max}$?
то как-то совсем уж сильно ломаете исходную задачу, и уточнение в скобках в моём предыдущем предложении о том, что Лиса тут же вернётся к меньшей скорости $k_{\max} < k(t)$ становится каким-то неестественным. Но если всё-таки его придерживаться (а если не его, то нужно что-то другое предположить явно, например, что Утке $k(t)$ известно заранее), то получается, что Утка просто перевычисляет мгновенную цель на берегу и мгновенный вектор скорости направляет к этой точке (если Лиса возвращается к оптимальной стратегии, то мгновенный вектор сохраняется, и Утка снова плывёт по прямой). Особняком стоит случай, когда Утка и Лиса оказываются на одном диаметре (разумеется, с противоположных от центра сторон): в этот момент Утка не знает, в какую сторону Лиса побежит в следующий момент (локально любое направление оптимально), поэтому в этот (и только в этот) момент Утке выгоднее плыть по этому же диаметру к берегу (это будет её стратегией в течение ненулевого времени, если Лиса остановится на диаметре), тут же меняя свою стратегию, как только Лиса сходит с диаметра.

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение24.01.2018, 11:16 


05/09/16
11469
worm2 в сообщении #1287049 писал(а):
Лиса тут же вернётся к меньшей скорости $k_{\max} < k(t)$ становится каким-то неестественным. Но если всё-таки его придерживаться (а если не его, то нужно что-то другое предположить явно, например, что Утке $k(t)$ известно заранее)

Я наверное нечетко написал. Ясно, что если Утка уже почти у берега а Лиса на другой стороне озера, то Утка успеет к берегу даже если скорость Лисы много больше чем $4,603$, и даже знаем куда Утке надо плыть: по касательной к "кругу безопасности".
То есть, $k_{max}$ является функцией координат Лисы и Утки.

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение24.01.2018, 11:33 
Заслуженный участник
Аватара пользователя


01/09/13
4318
wrest в сообщении #1287062 писал(а):
и даже знаем куда Утке надо плыть: по касательной к "кругу безопасности".

Не вполне верно - в такой формулировке на эллипс не обощить...

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение26.01.2018, 19:58 
Заслуженный участник


09/02/06
4382
Москва
Можно обобщить на центрально симметричный контур озера. Правда в случае не выпуклости возникают много разных нюансов.
Поэтому ограничусь с центрально симметричным выпуклым контуром, куда относится эллипс. Существует к раз уменьшенный контур, где может плыть утка и выйти на противоположный от лисы точку от лисы. Оптимальной для утки стратегией является выход из некоторой точки малого контура по прямой на большой контур.
Для эллипса это выход по касательной от большой оси малого контура.
.

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение27.01.2018, 01:36 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Руст в сообщении #1287663 писал(а):
Оптимальной для утки стратегией является выход из некоторой точки малого контура по прямой на большой контур.

А доказательство? (а то мне это утверждение кажется ложным)...

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение27.01.2018, 02:31 
Заслуженный участник


20/08/14
11067
Россия, Москва
Возникает ещё вопрос может (и будет ли) лиса бежать в новую более близкую точку к утке если при этом она временно от утки удаляется? В более простом случае - нет, не будет, лиса непрерывно минимизирует расстояние до утки по прямой и тогда для достаточно вытянутого эллипса утка может выйти на малую полуось эллипса безопасности (тут похоже ошибся и эллипс безопасности будет повёрнут на 90° относительно основного и может даже пересекать основной, или вообще превратится в астроиду, считать надо) и потом просто плыть по прямой малой полуоси эллипса - любое смещение лисы будет увеличивать расстояние до утки и лиса так и останется неподвижной. При любом конечном соотношении скоростей.
Т.е. есть некая зависимость и от других параметров фигуры, кроме выпуклости и центральносимметричности.

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

-- 27.01.2018, 02:52 --

Насколько я понимаю уже при отношении осей эллипса больше $\sqrt{2}$ утка может спокойно плыть прямо из центра по малой полуоси эллипса - лисе никуда сдвигаться невыгодно, любой её сдвиг увеличивает расстояние до утки, так она и останется в неподвижности. От соотношения скоростей не зависит.

-- 27.01.2018, 03:23 --

Для квадрата аналогично, утке можно двигаться прямо из центра к середине противоположной от лисы стороне. Лиса останется неподвижной.
Это верно вообще для любой фигуры с радиусом кривизны в месте расположения лисы более удвоенного расстояния от центра до лисы. Что отсекает вообще все многоугольники.
Интересно что за кривая будет в предельном случае, у которой радиус кривизны линейно возрастает от расстояния до центра в диапазоне от одной до двух малой полуоси . При этом лиса будет сдвигаться в сторону в зависимости от мгновенного положения утки, но до точки поворота/срыва дойдёт лишь в момент выхода утки на берег.

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение31.01.2018, 05:47 


05/12/17
2
Лиса бежит по берегу, а утка плывёт по озеру, утка может плыть как хочет, может по прямой поплыть, путь, как хорда к окружности

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение31.01.2018, 10:16 


05/09/16
11469
Dmitriy40 в сообщении #1287713 писал(а):
В более сложном случае - лиса оптимизирует не мгновенное расстояние по прямой до утки, а перемещается в наиболее близкую точку из всех возможных

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

Dmitriy40 в сообщении #1287713 писал(а):
Для квадрата аналогично, утке можно двигаться прямо из центра к середине противоположной от лисы стороне. Лиса останется неподвижной.

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

 Профиль  
                  
 
 Re: Лиса, Утка и озеро.
Сообщение31.01.2018, 11:02 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Dmitriy40 в сообщении #1287713 писал(а):
Для квадрата аналогично, утке можно двигаться прямо из центра к середине противоположной от лисы стороне. Лиса останется неподвижной.

Но если скорость лисы, скажем, в 10 раз больше, то лиса выигрывает при старте в любую сторону если утка в центре....

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 404 ]  На страницу Пред.  1 ... 4, 5, 6, 7, 8, 9, 10 ... 27  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group