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

[realeugene]

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

[wrest]

realeugene в сообщении #1291364 писал(а):

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

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

[rockclimber]

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

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

Я должен уточнить: если лиса действует по "простой" стратегии (всегда бежит к ближайшей точке), то утка побеждает всегда, и тут неважно, чему равно $k$.

Ну я вот не представляю как это у вас так получается. Однако

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

В любом случае стратегию нужно проверить, поскольку интуиция нас всех в этой теме уже подводила

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

Все интереснее и интереснее!
Я решил тщательно записать решение и узнал много нового.
Итак, исходим из того, что пруд квадратный, лиса бежит в точку, к которой утка ближе всего. Считается, что зона безопасности - это квадрат со стороной $1/k$. Введем так же понятие равновесного положения. Это положение, когда утка и лиса находятся в таком положении, что лисе не важно, бежать по часовой или против, в любом случае ей бежать одинаковое расстояние. Тогда можно рассмотреть в качестве начальной ситуации положение, когда утка и лиса находятся в углах, утка - в углу квадрата безопасности. Но! Достижимо ли такое положение? Этот вопрос у меня возник, когда я, играя сам с собой за утку, попробовал загнать в угол лису и при этом выйти на диагональ. Начал с позиции "утка в центре, лиса в центре стороны". Теперь внимание на рисунок внизу!
Утка в точке $A$, лиса в точке $B$. Был бы это круг, это было бы равновесное положение. Но в квадрате это не так! Ведь лисе надо бежать не в точку $C$, а в точку $D$! А равновесным положение было бы, только если бы лиса находилась в точке $E$.
Вывод пока такой - нам надо срочно вернуться на шаг назад и пересмотреть наше понимание зоны безопасности и таки сначала идентифицировать ее форму. В том, что это квадрат, я уже не уверен.

[wrest]

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

если не на нём - лиса сдвинулась и надо идти горизонтально/вертикально к какой-то стороне,

А как же арккосинус?

[grizzly]

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

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

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

Я могу предложить Вам два варианта: (а) посмотреть несколько прошлых страниц (хотя там 50% мусора, да); (б) найти самостоятельно решение и убедиться, что оно совпадает с нашим.

[rockclimber]

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

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

А, вот оно что. Я вроде спрашивал недавно, что было на пропущенных мной страницах, мне вроде ответили, что ничего особо интересного. Тогда попозже перечитаю еще раз.

[wrest]

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

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

Мы определяем фигуру безопасности как такую, на границах которой угловые скорости Утки и Лисы равны если Утка и Лиса находятся на диаметре. То есть внутри фигуры безопасности Утка обгоняет Лису по углу. Если вы хотите дать какое-то другое определение, то и форма фигуры изменится. Можно например говорить о "мгновенной фигуре безопасности", которая зависит от взаимного положения Утки и Лисы.
А что же вы Утку на своей картинке на диагональ не поместили? Был бы Лисий конфуз :)

-- 09.02.2018, 14:43 --

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

Я решил тщательно записать решение и узнал много нового.

Вы главное скажите, вы по-прежнему считаете что Лиса всегда догоняет Утку на случай озера в виде квадранта?

[rockclimber]

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

Мы определяем фигуру безопасности как такую, на границах которой угловые скорости Утки и Лисы равны если Утка и Лиса находятся на диаметре. То есть внутри фигуры безопасности Утка обгоняет Лису по углу.

Фигура безопасности в таком виде - бессмысленная вещь, если озеро - многоугольник. Она ни для чего не годится. Соответственно, строить на ней какие-то решения нельзя, они будут ошибочными.
Вспомните, с чего начиналось решение для круга. Утка занимала наиболее выгодное для себя положение, а потом делала рывок к берегу. Я считаю, что надо определять фигуру безопасности подобным же образом - с точки зрения интересов утки, и правильно делать это через введенное мной выше понятие равновесного положения.

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

Вы главное скажите, вы по-прежнему считаете что Лиса всегда догоняет Утку на случай озера в виде квадранта?

Очевидно, если я сейчас считаю ошибочными стартовые условия решения, то и само решение я считаю ошибочным.

[wrest]

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

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

Не для себя, а относительно Лисы. Так вот некоторые считают, что умную Лису не загонишь в угол квадрата просто так, она до какого-то момента будет хладнокровно смотреть как Утка отплывает и плывет уже в зоне где угловая скорость Лисы больше, и только потом рванет с места. ГМТ Утки по достижению которого Лиса срывается и бежит, мы назвали "фигура принятия решения Лисы".

[Dmitriy40]

rockclimber
Утка действительно не всегда может выбирать конфигурацию в момент покидания зоны безопасности, тут главнее лиса, всё зависит от её стратегии, выше в теме были парочка когда лиса в угол не попадает пока утка в зоне безопасности. Например: при утке в координатах $(x;y)$ лиса бежит к координате $(kx;-1)$, именно в ту же сторону что и утка, не наоборот, или в любую сторону при $x=0$ и $y>0{,}3$ и продолжает бежать в сторону уменьшения угла между радиус-векторами на утку и лису (здесь лисе из любой точки между B и E бежать в точку D по Вашему рисунку всегда невыгодно) - возможно это вообще оптимальная стратегия лисы. Потому единственной реально достижимой конфигурацией при разумных предположениях является: лиса в $(0;-1)$, утка в $(0;1/k)$. По крайней мере утка в неё гарантированно может попасть при не слишком тупой лисе. Чем лиса тупее - тем больше выбор у утки.

Насчёт формы зоны безопасности, квадрат $1/k$ - объективная фигура, не зависящая от стратегии лисы, как и круг $1/k$ для круглого озера, он получен из тех же соображений. Но в силу центральной асимметрии появляются варианты, с точностью до поворотов и отражений:
1. утка и лиса в центрах сторон;
2. утка в центре стороны, лиса слева в углу;
3. утка справа в углу, лиса слева в углу;
4. утка справа в углу, лиса в центре стороны;
5. утка справа в углу, лиса тоже справа в углу.
Утка разумеется на верхней стороне зоны безопасности. Остальные и все промежуточные варианты вроде не интересны т.к. хуже одного из этих.
Варианты 2, 4 нелогичны для лисы, а утка не может заставить лису к ним придти; вариант 5 нелогичен для утки и она гарантированно может в него не попасть; остаются варианты 1 и 3 - оба с размещением утки и лисы на диаметре. По моим оценкам вариант 3 лисе не выгоден - и она может в него не попасть вне зависимости от действий утки. Потому остаётся лишь один первый основной вариант, достижимый даже при оптимальных для себя действиях и лисы и утки.

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

Утка в точке $A$, лиса в точке $B$. Был бы это круг, это было бы равновесное положение. Но в квадрате это не так! Ведь лисе надо бежать не в точку $C$, а в точку $D$! А равновесным положение было бы, только если бы лиса находилась в точке $E$.

Мне кажется это неполное условие, равновесным положение лисы будет не при равенстве путей лисе до D, а при равенстве путей до D и до точки слева на стороне с высотой точки A (т.е. аналога точки D, но на левой стороне) - вот тогда лисе действительно без разницы куда утка поплывёт, вверх или влево. Вот только я уже приводил стратегию утки (первая выложенная программа, после долгих споров с grizzly, вот это сообщение и пяток ниже), когда выигрывает при k=5,7 в квадрате из точки $(0;1/k)$ куда бы лиса не бежала: плыть или вверх если лиса на диаметре, или по горизонтали в сторону увеличения угла на лису (для исключения повторов - с бесконечно малым углом вверх от горизонтали). Где бы лиса не находилась и куда бы ни бежала - утка выигрывает.

-- 09 фев 2018, 22:57 --

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

ГМТ Утки по достижению которого Лиса срывается и бежит, мы назвали "фигура принятия решения Лисы".

У меня уже давно крепнет подозрение что это ГМТ в случае оптимального поведения лисы с точностью до поворотов вырождается в ровно одну точку - на отрезке $(0;0)-(0;1)$. И условие на неё достаточно простое: равенство путей лисе при движении утки строго вверх и строго вправо/влево по горизонтали в противоположную от лисы сторону. Для всех других многоугольников кроме квадрата надо учитывать не только соседнюю с северной сторону берега, но и более дальние, в том числе с заходом утки снова в зону безопасности (т.е. возможную смену угла между уткой и лисой, хотя последнее кажется можно и не рассматривать т.к. возвращает к начальной конфигурации), тут я ещё не додумал.

И ещё это самое ГМТ зависит от конкретной стратегии лисы! Т.е. надо каждый раз указывать про какую из них идёт речь. Например если лиса "сопровождает" утку пока та в зоне безопасности (при утке в $(x,y)$ лиса бежит в $(x,-1)$ или даже в $(kx,-1)$), то ГМТ уже другое будет. Даже в случаях $(x,-1)$ и $(kx,-1)$ тоже разное (вероятно). Правда условие - ровно то же, осталось лишь его нарисовать.

[worm2]

Последние 3 недели я только и делаю в свободное время, что думаю над этой задачей.
Прогресс чудовищно медленный.
Еле-еле разобрал случай, когда озеро — (бесконечный) угол, меньший развёрнутого. Для конечных озёр, являющихся выпуклыми многоугольниками, это даёт локально оптимальную стратегию, когда Утка находится относительно близко от одной стороны или от одной вершины угла (относительно далеко от других вершин). Как отсюда синтезировать локально оптимальный алгоритм (не говоря уже о глобально оптимальном) для всего многоугольного озера — совершенно непонятно. Но квадрат, кажется, удалось добить (хотя строгого доказательства у меня нет, я пока что не надеюсь его получить даже для угла).

Если интересно, я могу выложить решение для угла. Но пока напишу только про квадрат. Итак, критическая скорость Лисы

$$k=\sqrt{\frac{35+5\sqrt{41}}{2}}\approx 5.788593.$$

Да, на предыдущем допросе я называл другое число: 5.786... Это не ошибка округления. Это решение другого уравнения, которое в радикалах у меня не выразилось. Прошлые выкладки я потерял, поэтому не знаю, то ли там была ошибка при преобразованиях выражений, то ли я вообще изначально опирался на не совсем правильные посылки.



Угол на рисунке $\varphi = \arcsin(1/k)$. В вычислениях часто встречается его котангенс $\ctg\varphi=\sqrt{k^2-1}=(5+\sqrt{41})/2\approx 5.7015$, это число где-то в теме уже упоминалось. Углы $\varphi$ откладываются от диагоналей квадрата во все стороны (на рисунке эти лучи изображены зелёным цветом), точки их пересечения образуют красный квадрат, который и является фигурой принятия решения (сокращённо ФПР). На первом этапе Утка старается достичь её границы так, чтобы лиса была "ровно с противоположной стороны" (где именно — поясню ниже), а на втором этапе Утка плывёт только по прямой, а Лиса — с максимальной скоростью только в одну сторону (отклонение от этой стратегии даёт выигрыш сопернику).

1 этап.
Утка плывёт к границе $M$ ФПР так, чтобы к моменту её достижения Лиса была в противоположной ей точке $M_3$, которая строится так: через $M$ параллельно ближайшей диагонали проводится прямая, которая перекает ближайший зелёный луч в точке $M_1$; далее $M_1$ проецируется на ближайшую сторону озера, получая $M_2$; наконец, $M_2$ отражается относительно центра, получая $M_3$. Можно считать, что вместо Лисы $M_3$ Утка соревнуется с её отражением $M$ по данной схеме, которое бегает по границе ФПР, причём Утка стремится не убежать от него, а, наоборот, попасть точно в отражение.

"Это всё, конечно, хитро придумано", — скажете вы с сарказмом, — "но как быть со скоростью этого вашего отражения? Ну-ка, посчитайте-ка её, она окажется гораздо больше единицы! Как же бедная Утка при таком раскладе сможет догнать отражение Лисы?".

Действительно, максимальная скорость отражения легко считается: $k'=\dfrac{\sqrt{2}k}{\sqrt{k^2-1}+1}\approx 1.22$. Кого я хотел обмануть?
Всё дело в том, что я, как уже писал, на углах собаку съел. И владею тайным знанием: если половина угла, в который плывёт Утка, меньше "угла скорости" (а в нашем случае это так: $\varphi'=\arcsin(1/k')\approx0.96>\pi/4$), то, оказывается, Утка может поймать отражение! Правда, это верно для бесконечного угла. Но в данном случае легко показать, что Утка загоняет отражение в угол (или догоняет его раньше): сначала она просто наглым образом плывёт по направлению к отражению. Рано или поздно проекция Утки на ось абсцисс или на ось ординат совпадёт с проекцией на ту же ось отражения. После того, как Утка "схватила" эту проекцию, она продолжает её "держать", на это скорости хватает с запасом. Избыток скорости используется для неограниченного приближения к жертве по другой оси. Отражение либо выбегает из угла, и Утка ловит его на границе, либо остаётся в вершине, где Утка бесконечно к ней приближается.

2 этап.
Попав в противоположную Лисе точку ФПР, Утка продолжает следить за тем, с какой стороны Лиса будет находится от противоположной ей точки. Если Лиса уходит вправо (против часовой стрелки), Утка плывёт по направлению $N_1$. Если Лиса уходит от противоположной точки по часовой стрелке, Утка плывёт по направлению $N_2$. Пока Утка находится внутри "малого" треугольника (с зелёными бёдрами и красным основанием), противоположность определяется по тому же алгоритму: через позицию Утки параллельно диагонали проводится прямая до пересечения с зелёным лучом, затем получившаяся точка проецируется на ближайшую сторону квадрата, и наконец, отражается относительно начала координат. Однако как только Утка выплывает за пределы "малого" треугольника и попадает в "большой" (с зелёными бёдрами и чёрным основанием, являющимся границей озера), стратегия меняется. Противоположная точка здесь определяется по-другому: зелёный луч не используется, текущая позиция Утки сразу проецируется на ближайшую границу и затем отражается относительно начала координат. Кроме того, в "большом" треугольнике меняется направление Утки, когда Лиса находится по часовой стрелке от противоположной точки: в этом случае Утка плывёт не в направлении $N_2$, а в направлении ближайшей стороны, только угол откладывается в другую сторону (параллельно $MN_3$, хотя изнутри "малого" треугольника Утка никогда не должна плыть в направлении $N_3$, только $N_1$ или $N_2$, направление на $N_3$ разрешается после выхода в "большой" треугольник). Впрочем, это описание стратегии Утки "на все случаи жизни", в случае же, когда Лиса двигается оптимально, Утка сохраняет исходное направление движения, выбранное после выхода за пределы ФПР. Во всех случаях любая исходная точка $M$ на ФПР гарантирует одинаковое расстояние от Утки до Лисы к моменту достижения Уткой берега (нулевое, если $k$ равно критическому значению).

Есть небольшая вероятность того, что критическое значение $k$ можно увеличить. На эту мысль наталкивает то обстоятельство, что на первом этапе у Утки есть существенный запас скорости. Если его попытаться уменьшить, то ситуация усложняется. ФПР превращается из квадрата в восьмиугольник: уголки срезаются параллельно осям координат. На этих новых маленьких сторонах скорость отражения значительно больше (равна исходной скорости Лисы $k$), вследствие чего точно "поймать" отражение Утка не сможет: на срезанных углах отражение сможет оторваться. Но насколько? Я подозреваю, что увеличение будет настолько большим, что уменьшение расстояния до границы озера на втором этапе не сможет это компенсировать. Рассчитать точно пока не умею.

[worm2]

Общее решение для правильного $n$-угольника по вышеописанной схеме даёт следующее уравнение на $\varphi=\arcsin(1/k)$:

$$\sin\left(\varphi+\frac\pi n\right)\left(\cos\frac\pi n\cos\varphi-n\sin\frac\pi n\sin\varphi\right)=\sin\varphi\cos\varphi$$

при дополнительном условии $\varphi>\dfrac{\pi(n-4)}{2n}$ (при невыполнении этого условия Утка не может выйти на границу ФПР ровно в противоположной от Лисы точке).
К сожалению, дополнительное условие нарушается уже при $n=5$, что делает схему пригодной только для квадрата и треугольника. Для треугольника получается критическое значение $k = 3\sqrt{2}+\sqrt{10}\approx 7.4049$.

[Dmitriy40]

worm2
Как-то сложно сформулированы условия для утки, давайте для проверки упростим. Начальное состояние: лиса в середине нижней стороны, утка в верхней вершине красного квадрата. Опишите/нарисуйте траекторию утки на втором этапе при движении лисы по часовой стрелке с максимальной скоростью?

На мой взгляд утка должна двигаться по прямой или в $N_3$ или в $N_2$, без разницы, при этом лиса настигает утку при $k>5{,}7015$. Это и является нижней границей на $k$ для лисы. Т.е. из такого начального состояния для утки нет выигрышной стратегии при $k>5{,}7015$. Вы же утверждаете что таковая есть вплоть до $k \approx 5{,}788593$, ок, так приведите траекторию утки, хотя бы для $k=5{,}72$ (точно) из точки $(0,0{,}28)$ (точно).

[grizzly]

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

На мой взгляд утка должна двигаться по прямой или в $N_3$ или в $N_2$, без разницы, при этом лиса настигает утку при $k>5{,}7015$.

Что-то опять не так с арифметикой. Мне кажется, что по данному вопросу это уже третий заход :)

Пусть Утка плывёт от точки $(0;0.2984)$ до соответствующей точки $N_3'$. Считаем. Координаты $N_3'$: по иксу $(1-0.2984)/5.7015=0.1231$; по игреку 1. Считаем расстояние (путь) от Утки до $N_3'$: $\sqrt{(1-0.2984)^2+0.1231^2}=0.7123$. Путь Лисы: $4+0.1231=4.1231$. Делим $4.1231/0.7123=5.7884$. Всё с точностью 4 значащих цифры.

[Geen]

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

при этом лиса настигает утку при $k>5{,}7015$

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