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

[worm2]

Нет, у меня сумма произведений пар котангенсов (число слагаемых зависит от искомой величины) должна равняться $n$. Для некоторых $n$ (3,4,5,6) получается $k$ выразить в радикалах.
Решение для круга $k=1/\sin\varphi$, где $\varphi\approx 0.21898$ — одно из решений уравнения $\ctg\varphi=3\pi/2-\varphi$, которое можно сосчитать со скольки угодно знаками.
Вот, например: $1/\sin(0.218979522475626)\approx 4.6033388487517$.

[wrest]

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

Нет, у меня сумма произведений пар котангенсов (число слагаемых зависит от искомой величины)

Да, и какова эта зависимость числа слагаемых от $n$, вы же посчитали уже для первых 30-ти?

[worm2]

Да, посчитал:

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

$$M=M(\varphi,n)=\left\lceil n\left(\frac 1 2-\frac\varphi\pi\right)\right\rceil-1.$$

То есть зависимость не только от $n$, но и от неизвестной $\varphi$. Или, можно сказать другими словами, нужно брать произведения котангенсов до тех пор, пока они положительны. Как только $\varphi+m\frac\pi n$ перевалит через $\frac\pi 2$, его котангенс станет отрицательным. И значит, произведение тоже станет отрицательным. Значит, мы это слагаемое уже не считаем и выдаём значение функции. И сравниваем его с $n$. А дальше методом деления отрезка пополам, или Ньютона...

-- Пн мар 05, 2018 21:58:30 --

Примерно $\lceil0.43n\rceil-1$ слагаемых получается.

[wrest]

Хорошо, теперь надо проверить решение worm2 для многоугольников численно.
Для этого нужен Dmitriy40 который починит алгоритм за Утку в post1291287.html#p1291287 и запрограммирует $n$-угольники.

worm2, как вы думаете, что значит что

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

Примерно $\lceil0.43n\rceil-1$ слагаемых получается.

Ну вот например: $2/k_0 \approx 0,43$ где $k_0 \approx 4,6033$ И тогда будет соответственно $\lceil\dfrac{2n}{k_0}\rceil-1$ слагаемых. Совпадение?

[worm2]

Кажется, мне удалось, продав душу дьяволу, снять проклятье, препятствовавшее моделированию этой задачи на компьютере.
Итак, помимо декартовых координат, на границе вводится координата $s$, равная длине отрезка пути по границе против часовой стрелки от некоторой начальной точки границы (натуральный параметр). При полном обходе озера $s$ скачком меняется от периметра до нуля (это одна из причин проклятья). Можно было бы избавиться от скачка за счёт многозначности, но не похоже, что это что-то облегчает.
Функции $x(s)$ и $y(s)$ задают зависимость декартовых координат точки границы от её натуральной координаты. А там, где $x$ и $y$ употребляются без скобок, это будут координаты Утки (недеюсь, путаницы не возникнет).
Введём вектор-функцию $\vec{r}(x,y,s)=(x(s)-x,y(s)-y)$ — это вектор, направленный от Утки $x,y$ к некоторой точке границы $s$.
Если Утка плывёт к этой точке по прямой, то она, очевидно, преодолевает расстояние $|\vec{r}(x,y,s)|$.
Предположим, что для Утки существует ровно две оптимальных точки на границе озера: $s_{-}(x,y)$ и $s_{+}(x,y)$, такие, что для любой координаты Лисы наилучшим направлением является одно из этих двух: $\vec{r}(x,y,s_{-}(x,y))$ или $\vec{r}(x,y,s_{+}(x,y))$.

Как мы будем определять эту пару точек? Прежде чем ответить на этот вопрос, я повторю ещё раз, что мне удобнее работать с "отражением" Лисы (точкой границы озера, удалённой от позиции Лисы на полпериметра при движении хоть по, хоть против часовой стрелки).
При этом Утка это "отражение" старается догнать, прибыв к границе на минимальном расстоянии от него. А отражение стремится убежать от Утки как можно дальше, желательно на полпериметра (что будет обозначать, что реальная Лиса поймала Утку).
Обозначим через $s_0(x,y)$ наиболее выгодную для Утки позицию отражения, чтобы при движении Лисы по часовой стрелке, а Утки к $s_{-}(x,y)$ достигался тот же самый результат, что и при движении Лисы против часовой стрелки, а Утки к $s_{+}(x,y)$.
Приравниваем:

$$s_0(x,y)-s_{+}(x,y)+k|\vec{r}(x,y,s_{+}(x,y))|=s_{-}(x,y)-s_0(x,y)+k|\vec{r}(x,y,s_{-}(x,y))|.$$

(напомню, что $k$ — это соотношение скоростей Лисы и Утки). Здесь и дальше у меня упрощённая запись, не учитывающая тот факт, что координата $s$ может пройти через ноль, и поэтому для пройденного от $s_1$ до $s_2$ против часовой стрелки расстояния формула $s_2-s_1$ будет не всегда верна.
Получаем:

$$s_0(x,y)=\frac{s_{+}(x,y)+s_{-}(x,y)+k(|\vec{r}(x,y,s_{-}(x,y))|-|\vec{r}(x,y,s_{+}(x,y))|)}{2}$$

и результат (на сколько отражение убегает от Утки):

$$F(x,y,s_{-},s_{+})=\frac{s_{-}-s_{+}+k(|\vec{r}_{-}|+|\vec{r}_{+}|)}{2}.$$

Позднее дополнение 2: формула исправлена, ранее в числителе было $s_{+}-s_{-}+k(\dots)$

Теперь всё готово для того, чтобы определить оптимальную пару точек $s_{-},s_{+}$ по $(x,y)$. Эта пара должна минимизировать

$$F(x,y,s_{-},s_{+}) \to \min\limits_{s_{-},s_{+}}$$

при дополнительном условии:

$$\left(\frac{\vec{r}(x,y,s_{-})}{|\vec{r}(x,y,s_{-})|}+\frac{\vec{r}(x,y,s_{+})}{|\vec{r}(x,y,s_{+})|}, \vec{r}(x,y,s_0)\right) \geqslant 0.$$

Это условие — самое трудное для понимания. Оно означает, что двигаясь попеременно то по одному направлению $\vec{r}_{-}$, то по другому $\vec{r}_{+}$, т.е. по биссектрисе между ними, Утка приближается к оптимальному положению отражения $s_0$ (по крайней мере, не отдаляется от него).
Если оно нарушается, минимум часто получается меньше (и программа, разумеется, в него "сваливалась"), но это решение бессмысленно, т.к. двигаясь попеременно в разные стороны относительно $s_0$, Лиса заставляет Утку выбирать то одно, то другое направление, т.е. двигаться по биссектрисе, при этом отдаляясь от отражения (и приближаясь к Лисе). Это уже упоминалось, например, здесь:

Я в сообщении #1290907 писал(а):

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

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

Увы, так не получается. Для круглого озера радиуса 1, если Утка находится в центре, а Лиса бежит против часовой стрелки из точки (1, 0), то по гипотезе получается, что Утка должна плыть к точке $(\cos\varepsilon, -\sin\varepsilon)$, где $\varepsilon$ — бесконечно маленький положительный угол, а когда Лиса, видя такой поворот, повернёт обратно, получается, что Утка должна плыть к точке $(\cos\varepsilon, +\sin\varepsilon)$. Т.е. фактически Утка должна плыть прямиком в лапы Лисы.

Позднее дополнение 1:
Дополнительное условие неточно. Лиса может заставить Утку двигаться не только по биссектрисе, но и по любому направлению между $\vec{r}_{-}$ и $\vec{r}_{+}$. Поэтому нужно его усилить, сделав вместо одного сложного условия два простых: $\left(\vec{r}(x,y,s_{-}), \vec{r}(x,y,s_0)\right) \geqslant 0$ и $\left(\vec{r}(x,y,s_{+}), \vec{r}(x,y,s_0)\right) \geqslant 0$.

Позднее дополнение 3:
На самом деле в программе проверялось даже не такое условие, а вот такое: угол между направлением от $\vec{r}(x,y,s_{-})$ до $\vec{r}(x,y,s_{+})$ (против часовой стрелки) не должен превышать развёрнутого. Оно немного слабее, чем условия, указанные в позднем дополнении 1, но, как мне подсказывает интуиция, именно такое условие — самое правильное. Его, к тому же, проще проверять, потому что не надо вычислять $s_0$, а достаточно проверить другой угол, между касательными к тем сторонам, на которые плывёт Утка, этот угол не должен превышать $2\varphi$.

Определив оптимальные направления, определяем и сам минимум:

$$G(x,y) = \min\limits_{s_{-},s_{+}}F(x,y,s_{-},s_{+}).$$

Эта функция $G$ — в точности та же, что и в этом сообщении. Обозначение $F$ похоже, там все направления были известны и рассматривалась зависимость $F$ от неизвестной $s$, которую мы здесь определили как $s_0$.
Фигура принятия решения является одной из линий уровня $G$.
Целью программы было определение $G$ во всех точках внутри озера. Алгоритм перебирал точки на прямоугольной сетке и для каждой точки перебирал всевозможные пары сторон, к которым Утка могла плыть под известно каким углом (т.о. перебирались всевозможные пары $s_{-}$, $s_{+}$), проверялись условия, вычислялись $F$, потом находился минимум.
К большинству сторон не было пути под нужным углом, но всё равно сложность алгоритма получается квадратичная от числа сторон. Так что картинок в сверхвысоком разрешении у меня не получилось.

Вот что у меня получилось для эллипса с полуосями 0.8 и 1 и скоростью $k=10$ (очевидно, что это слишком большое $k$, не критическое. До определения критического значения $k$ ещё далеко):

Самое интересное место в увеличенном виде:

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

[worm2]

Кажется, получилось найти критическую скорость для эллипсов.
Сначала картинки. Эллипсы с соотношениями сторон 1:2 и 4:5, со своими областями принятия решения:

Для эллипса 1:2 критическая скорость получилась примерно 6.984, для эллипса 4:5 — 5.167.
Как обычно, все расчёты я проводил не с критическими скоростями $k$, а с критическими углами $\varphi$: $k = 1/\sin\varphi$. Уравнение на критический угол получилось на удивление простым (я вообще не ожидал, что у меня будут шансы его получить в замкнутом виде):

$$\frac{(1-e^2)\ctg\varphi}{\sqrt{1-e^2\cos^2\varphi}}=\int\limits_{\arctg\frac{\tg\varphi}{\sqrt{1-e^2}}}^{3\pi/2}\sqrt{1-e^2\sin^2\theta}\,d\theta\,,$$

где $e$ — эксцентриситет эллипса. Интеграл справа имеет простой физический смысл: это просто длина дуги эллипса, выраженная через угол $\theta$ (стандартный параметр эллипса, немножко испорченный тем, что я ось эллипса располагаю вертикально, а не горизонтально, как принято). Да, я знаю, что этот интеграл имеет название (неполный эллиптический 2-го рода) и какое-то стандартное обозначение, но в разных местах видел его немножко разное определение, да и у меня параметризация нестандартная, так что не стал это обозначение писать, чтобы самому не запутаться и других не запутать.

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

Повторюсь, что ключевыми для решения задачи являются линии уровня функции $G$ (см. предыдущее сообщение). Я сначала их только наблюдал на цветных картинках, а потом сообразил, что их можно довольно просто построить: если зафиксировать пару направлений $s_-, s_+$ (здесь и далее см. обозначения в предыдущем сообщении), то линия уровня $F(x, y, s_-, s_+) = \operatorname{const}$ (а это возможный кандидат; линии уровня $G$ целиком состоят из частей таких прямых-кандидатов) — это прямая, перпендикулярная биссектрисе угла между отрезками озера, на которых лежат точки $s_-, s_+$. В случае, если $s_-$ и $s_+$ лежат на одном отрезке границы озера, линия уровня $F$ будет параллельна этой границе. В гладком случае угол, от которого нам нужна биссектриса — это угол между касательными к границе озера в точках $s_-$ и $s_+$. Описанное в этом абзаце легко показать геометрически, даже без тригонометрии, но я пока не буду.

Итак, построив всевозможные линии уровня $F = \operatorname{const}$, мы получаем их огибающую — линию уровня $G = \operatorname{const}$, которая является границей пересечения некоторого (в многоугольном случае — конечного, в криволинейном — бесконечного) множества полуплоскостей, т.е. выпуклой по определению фигуры — кандидата в ФПР (фигуру принятия решения).

Как нам определить конкретную линию уровня, ограничивающую именно ФПР для критического значения скорости? Ну, я уже писал, что границей ФПР (ГФПР) является уровень $G(x,y) = P/2$, где $P$ — периметр озера. Только до сих пор не заострял внимание на том, что функция $G$ (так же, как и $F$) строится исходя из известного значения $\varphi$, т.е. на самом деле является функцией трёх аргументов: $G(x, y, \varphi)$, и нам нужно, варьируя $\varphi$, определить, какая из линий уровня $G(x, y, \varphi)=P/2$ является ГФПР. Нужно понять, каков критерий, по которому мы можем сказать, что да, линия уровня для вот этого $\varphi$ — ГФПР для критической скорости?

Для этого вспомним, какой смысл имеет значение функции $G$. Это размер выигрыша Лисы (проигрыша Утки) при условии, что к моменту выхода Утки на ГФПР Лиса находится в максимально невыгодной для себя (и максимально выгодной для Утки) позиции. Подробно это расписано в первом этапе решения для квадрата. $\varphi$ должно быть таким, чтобы Утка сумела "попасть" во "второе отражение Лисы" (для квадрата это точка $M$ на рисунке в упомянутом сообщении), которое бегает уже по ГФПР с вычисляемой специальным образом скоростью $v_{\rm{fox}, 2}$. Для квадрата эта скорость была постоянной на ГФПР, мы её умножали на синус половины угла ФПР (для квадрата это $\sin \pi/4=\sqrt{2}/2$) и сравнивали со скоростью Утки (единица). В качестве $\varphi$ бралось минимальное значение, для которого $v_{\rm{fox}, 2}\sin \pi/4 \leqslant 1$.

Для эллипса (точнее, я сейчас говорю про произвольный выпуклый многоугольник, в т.ч. приближающий эллипс) ситуация сложнее: во-первых, на каждом отрезке ГФПР скорость своя, во-вторых, углы тоже все разные. Не могу сказать, что у меня есть исчерпывающее решение этой задачи, но что-то весьма правдоподобное есть. Упрощённо, критерий звучит так: должна существовать прямая (которую я буду называть опорной), проекция на которую скоростей $v_{\rm{fox}, 2, i}$ на всех отрезках ГФПР по модулю не превосходит 1. На самом деле критерий сложнее (в некоторых случаях допустимы проекции, большие единицы), но для центрально-симметричных озёр описанный критерий я пока считаю точным. Достаточность увидеть довольно легко: как и в случае с квадратом, Утка сначала "ловит" проекцию "второго отражения Лисы" на опорную прямую, используя избыток скорости для приближения к "второму отражению" в направлении, перпендикулярном опорной прямой.

Но довольно теории. Численное моделирование показало, что дно и крышка "бочонка" всё более и более уплощаются при приближении проекции к единице, а также обнаружило любопытный факт: предельные отрезки дна и крышки, если их продлить до пересечения с границей озера, пересекут её под углом $\pi/2-\varphi$. Ну, то есть под каким надо углом Т.е. если утка попадает на ГФПР в её прямой части, то она дальше двигается по этой прямой влево или вправо, до границы озера. Вроде бы получилось как-то это теоретически обосновать, в результате чего задача резко упростилась, и получилась формула из начала поста. Хотя пробелов в рассуждениях у меня хоть отбавляй, вполне возможно, что где-то что-то упустил.

Пока на этом всё. Несмотря на внезапное озарение с эллипсом, общий случай покрыт мраком.

P.S. Вот здесь должен быть виден "бочонок" (я уже вставил критическое значение). Но не виден Много лишних "запрещённых" линий, которые мешают его увидеть. Линии уровня функции $G$ из этого рисунка, к сожалению, не видны.

P.P.S. У меня уже раздвоение личности. Одна часть меня обвиняет другую в графомании, "горшочек, не вари". Вторая часть видит, что нужно ещё писать и писать, чтобы разжевать до понятного состояния.

[wrest]

worm2
Я надеюсь, у вас же бочонок переходит в окружность когда эллиптическое озеро переходит в круглое? Просто вот эллипс 4:5 на картинке это уже "близко" к окружности, а бочонок на той же картинке вполне такой себе явный.

[grizzly]

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

а бочонок на той же картинке вполне такой себе явный.

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

[worm2]

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

Я надеюсь, у вас же бочонок переходит в окружность когда эллиптическое озеро переходит в круглое?

Я пока не умею рассчитывать теоретически длину прямого участка. Могу только проводить эксперименты, которые показывают, что всё-таки переходит, хотя и очень неохотно. Вот, например, эллипс 999:1000 :

Разрешение рисунка 500x500 точек, так что на нём сплюснутость незаметна даже при тщательном исследовании. А вот отличие бочонка от окружности хорошо видно невооружённым глазом (благодаря растеризации видно, но всё-таки).

[vvsss]

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

[wrest]

vvsss в сообщении #1348211 писал(а):

Считаю, что утка меняет направление не на 180 градусов, а симметрично относительно радиуса, содержащего точку утки.

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

[vvsss]

Подскажите, пожалуйста на какой странице полное решение для круглого озера.

[arseniiv]

Вряд ли кто-то помнит. Кому-то за вас придётся листать тему для ответа на этот вопрос. Потому конструктивно начать искать самому, а не ждать тех, кто помнит или кому будет не лень листать.

UPD: ого, удача на вашей стороне.

[wrest]

vvsss
Вот тут: post1286894.html#p1286894