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

[Dmitriy40]

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

Например, в квадрате со стороной $1$ утка может двигаться по окружности радиуса ${2}/{\pi k}$. Эта окружность будет местами вылезать из квадрата $1/k$.

Вот этого момента не понял. Я рассматривал фигуру движения утки с угловой скоростью лисы. Причём разумеется как можно дальше от центра в каждой точке. Похоже Вы предлагаете рассматривать лишь вписанную окружность в мою фигуру, но как тогда она может выступать за квадрат неясно.
Рассмотрим граничные точки в квадрате со стороной $2$ ("радиусом" $1$) и начнём с центра стороны для лисы. Утка может переместится в точку противоположную лисе на расстоянии $1/k$ от центра и не далее. При малом смещении лисы утка конечно может плыть и по окружности, но выгоднее (в смысле увеличения расстояния от центра) плыть по прямой, сохраняя угловую скорость лисы. Повторяя рассуждение придём именно к квадрату со стороной $2/k$ - это и есть фигура безопасности.
В чём здесь ошибка или где здесь для утки окружность большего радиуса чем $1/k$?

-- 31.01.2018, 16:35 --

А, понял, Вы похоже посчитали время оборота утки и лисы и приравняли их. А это точно можно назвать фигурой безопасности? Ведь в окрестностях некоторых точек утка не сможет находиться продолжительное время, именно всех что выступают за квадрат, там угловая скорость утки меньше угловой скорости лисы и та не вернётся назад, а продолжит бег. Т.е. равновесие неустойчиво (в смысле малых сдвигов лисы, утка уже не может их нивелировать).

-- 31.01.2018, 16:39 --

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

[rockclimber]

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

А это точно можно назвать фигурой безопасности?

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

-- 31.01.2018, 17:56 --

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

[wrest]

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

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

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

[Geen]

Мда...

Если утка уже "близко" к берегу, а лиса "неподалёку", то без потери общности берег можно "спрямить" и решать следующую задачу. Пусть озеро занимает верхнюю полуплоскость, утка находится в точке с координатами $(0,h)$, а лиса - $(-a,0)$. Скорость утки $1$, а лисы $V$. В какой точке $(d,0)$ утке надо вылезать на берег, чтобы максимизировать расстояние до лисы в этот момент?
Задача решается довольно просто. Пусть $r$ - расстояние между уткой и лисой в момент вылезания утки. Тогда $r=(a+d)-V\sqrt{h^2+d^2}$. Максимум достигается при $\frac{dr}{dd}=1-\frac{Vd}{\sqrt{h^2+d^2}}=0$. То есть, при $d=\frac{h}{\sqrt{V^2-1}}$.
Таким образом, выход утки на берег составляет с касательной к берегу угол $\cos\alpha=1/V$.
Очевидно, что к точке "высадки", в некоторой области около берега, утка должна двигаться по прямой. Назовём обобщённой эволютой огибающую семейства прямых, образующих заданный угол с заданной кривой. Она обобщает эволюту в смысле произвольности (но фиксированности) угла пересечения прямых с заданной кривой. Тогда, можно надеяться, что движение утки по прямой происходит от соответствующей обобщённой эволюты до берега.

[rockclimber]

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

Неочевидно, т.к. в случае многоугольников, хоть треугольника, хоть квадрата, таких "проекций" больше одной

Слово "очевидно" относилось к тому, куда надо бежать лисе. Очевидно ;), если таких точек несколько, лисе имеет смысл бежать к ближайшей. А даже если и не к ближайшей - все равно к одной из.

[Geen]

Для окружности обе обобщённые эволюты совпадают и являются окружностью радиуса $1/V$.
Для эллипса картинка и код приводились.

[wrest]

Geen
Для озера-полуплоскости рассуждения понятны, но вот переход к конечному озеру непонятен.
Допустим, берег имеет форму окружности (или эллипса) "в целом", но сам берег не очень гладкий, тогда Утке для принятия решения куда плыть действительно надо будет как-то спрямлять его. Тут правда может нарушиться условие выпуклости, но допустим оно не нарушается. Ну не знаю, допустим это какой-то вписанный в эллипс 8-ми угольник или 10-угольник, с равными сторонами.
И кстати, а что ваш метод дает для квадрата?

[Geen]

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

но вот переход к конечному озеру непонятен.

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

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

но сам берег не очень гладкий

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

может нарушиться условие выпуклости

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

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

И кстати, а что ваш метод дает для квадрата?

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

Кстати, набросал вчера страничку http://www.k-labs.ru/dms/fdl.html

[EUgeneUS]

Geen в сообщении #1289061 писал(а):

Кстати, набросал вчера страничку http://www.k-labs.ru/dms/fdl.html

Классно!

Возникли вопросы (у меня пока нет ответов ).
1. Если утка находится на эволюте, то по какому критерию она должна стартовать к берегу или попытаться выбрать другую точку на эволюте.
1.1. Для круглого озера очевидно: когда лиса находится на противоположной стороне озера - угол между радиус вектором лисы и утки равен $\pi$.

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

3. При каких условиях (всегда ли?) утка может "загнать лису" в наихудшее положение?

[Geen]

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

Все ли точки эволюты равнозначны?

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

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

При каких условиях (всегда ли?) утка может "загнать лису" в наихудшее положение?

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

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

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

Должно быть безразлично (в исходной формулировке игры). Но бесконечное путешествие по эволюте надо как-то запретить "правилами".

-- 01.02.2018, 11:50 --

Кстати, полагаю понятно, что построение эволют это лишь только первый этап решения...

[EUgeneUS]

Geen в сообщении #1289072 писал(а):

Должно быть безразлично (в исходной формулировке игры). Но бесконечное путешествие по эволюте надо как-то запретить "правилами".

Бесконечное путешествие утки можно запретить таким правилом: в какой-то момент времени t утка обязана принять решение "плыть к берегу", t - любое конечное. Понятно, приняв такое решение, утка плывет к берегу по известно какой прямой с максимальной скоростью.
Оптимально для утки принимать такое решение, а) находясь на эволюте, б) когда лиса в наихудшем положении.

Отсюда вопрос: каков критерий того, что "лиса в наихудшем для неё" положении?

[Geen]

(Оффтоп)

Geen в сообщении #1289061 писал(а):

Кстати, набросал вчера страничку http://www.k-labs.ru/dms/fdl.html

Пара технических моментов. Кнопка в правом верхнем углу страницы (без текста) инвертирует палитру (применяется почти ко всем моим страницам) - если не нравится чёрный фон.
Параметры эллипса можно загнать в УРЛ (кнопка под блоком параметров) - если надо сослаться на какой-то конкретный их набор.

-- 01.02.2018, 13:04 --

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

Отсюда вопрос: каков критерий того, что "лиса в наихудшем для неё" положении?

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

Собственно, можно дальше анализировать игру постепенно усложняя картинку, или попытаться описать все типы областей сразу...
Я бы предложил первый способ (для второго я слабоват ).
Можно начать, к примеру, с http://www.k-labs.ru/dms/fdl.html#el_1.125_2_p_m_1_

[wrest]

Geen в сообщении #1289083 писал(а):

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

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

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

[worm2]

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

каков критерий того, что "лиса в наихудшем для неё" положении?

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

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

[Geen]

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

Эволюта развалится на две "полуэволюты", и чего?

На четыре - будут ещё две "точки" в бесконечности...