Преследование на плоскости (стр. 2 из 3)

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

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

Пусть теперь убегающий игрок сменил направление. Иначе говоря он перешел к другой окружности Апполония (обозначим её А2). Пусть А точка в которой сменил направление убегающий игрок и В точка в которой сменил направление догоняющий игрок. Тогда отрезок АВ конец пути по траектории на А1 и начало пути по траектории А2. Следовательно любой отрезок на траектории А1 параллелен АВ и в то же время любой отрезок на траектории А2 также параллелен АВ. Таким образом, параллельность отрезков соединяющих соответствующие точки на траектории убегающего и догоняющего игроков сохраняются и при смене направления движения.

Один кролик и несколько лис

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

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

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

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

В такой постановке ответ почти очевиден. Кролик гарантированно встретится с хотя бы одной лисой, если любая прямая по которой он движется пересечёт хотя одну окружность Апполония. То есть имеет место следующая ситуация:

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

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

Радиус окружности Апполония:

Для того чтобы получить радиус построим формулу описывающую окружность.

Обозначения:

P – Преследователь

E – Убегающий игрок

O – Центр окружности Апполония

M – Точка встречи

Выберем систему координат таким образом, чтобы её начало было в центре окружности Апполония и E=(0,0); P=(0, – b)

Очевидно, что |EM|/V_e= |PM|/V_p

Или, что тоже самое |EM|* V_p = |PM|* V_e

Тогда |EM| = Öx² + y² и |PM| = Ö x² + (y +b)²

Подставим в предыдущую формулу и получим

V_pÖx² + y² = V_eÖ x² + (y +b)²

Возведём в квадрат обе части уравнения, сгруппируем и получим следующее уравнение

x² + (y – (bV_e²)/(V_p² – V_e²))² = (V_eV_pb/(V_p² – V_e²))²

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

R = V_eV_pb/(V_p² – V_e²)

Из этого же уравнения можно определить и координаты преследователя и убегающего игрока

Знание этих величин, и скоростей позволяет решить целый ряд задач. Например следующую:

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

4. Преследование на плоскости с одним преследователем

В данной игре существует оптимальная стратегия и для преследователя и для убегающего игрока. Оптимальной стратегией для преследователя будет стратегия параллельного сближения, а для убегающего игрока движение по прямой EA где Е начальная точка убегающего игрока и А точка Апполония.

Оптимальность стратегии для убегающего очевидна, так как начальная точка преследователя находится на той же самой прямой. Действительно суть стратегии параллельного сближения в том, что

А) Преследователь изменяет направление движения в тот же самый момент когда направление движения меняет убегающий игрок.

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

Из этих двух пунктов и следует оптимальность выбранной стратегии. А теперь определим оптимальное время преследования для такой игры.

Известно, что точка встречи – это точка Апполония. Известно, также что оба игрока движутся по прямой, следовательно, для определения времени встречи существенно важны не абсолютные значения скоростей, а то насколько скорость преследователя больше скорости убегающего игрока. Поэтому мы можем перейти к эквивалентной задаче, в которой убегающий игрок стоит на месте, а преследователь движется со скоростью равно V_p – V_e

В этой задаче преследователь должен пройти расстояние между его начальным положением и начальным положением убегающего. Мы уже обозначали это расстояние через b тогда оптимальное время преследование будет дано следующим выражением t=b/(V_p – V_e).

5 Игра с линией жизни

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

Теорема: В игре с линией жизни убегание невозможно только в том случае, когда линия жизни не пересекается с окружностью Апполония. При этом форма линии жизни несущественна.

Теорема очевидна и в доказательстве не нуждается.

Задача «о крысе загнанной в угол»

Из названия уже ясно, что речь идёт о игре в которой участвуют два игрока действующих внутри некоторого угла. Эта игра не исследована исчерпывающе. Хорошо известны только некоторые частные случаи, например преследование в прямом угле.

Теорема. Пусть убегающий игрок находится в вершине угла а преследователь на биссектрисе

Обозначим скорость убегающего игрока через V_e тогда, если скорость преследователя V_p = Ö2 V_e, то оптимальное время преследования t = b / V_e