Преследование на плоскости
Учебно-исследовательская работа
«Преследование
на плоскости»
Введение
Заключается задача в очень простой вещи. Есть
преследователи, один или группа, и есть некто, кто пытается от них убежать. А
нам важно понять – это очень просто убегать и догонять или это можно делать
множеством способов отличающихся друг от друга эффективностью. И трудно ли
найти наиболее эффективный (или оптимальный) способ погони или наоборот
бегства.
Прежде чем приступать к анализу рассмотрим
ситуацию, которая на первый взгляд кажется простой. Пусть некоторый кусок
плоскости ограждён забором в форме окружности и в этом загоне лис пытается
поймать кролика который бегает несколько быстрее лиса. Очевидно, что у лиса не
было бы никаких шансов, если бы кролик имел возможность бежать по прямой. В
этом случае при любой стратегии поведения лиса расстояние между ними бы только
увеличивалось. Стена может быть причиной по которой кролику придётся
развернуться и побежать в сторону лиса и здесь для лиса возникает уникальная
возможность поймать кролика.
Однако эта возможность реальна только для очень
специальной формы площадки и при не очень умном поведении кролика. Но и при
самой простой форме – окружности у лиса есть интересная возможность не отстать
от кролика даже при существенном различии в скоростях. Покажем, как он может
это осуществить.
Предварительное замечание. Цель кролика находиться как можно дальше от лиса. Из этого
следует, что при необходимости смены направления кролик должен осуществлять эту
перемену так, чтобы его направление движения составляло не острый угол с
направлением движения лиса (иначе он начнёт сближение). Необходимость же смены
направления возникает при угрозе столкновения со стенкой. Максимально тупой
угол кролик может обеспечить себе, двигаясь вдоль стенки. Отсюда следует, что
при заборе имеющим форму окружности оптимально для кролика бежать по окружности
как можно большего радиуса, то есть вдоль стены.
Как же в этом случае вести себя лису. Предположим, что у лиса скорость в два раза меньше. Тогда
если он будет бежать по окружности центр которой будет совпадать с центром
окружности кролика но длина её будет в два раза меньше, то за одно и тоже время
и кролик и лис оббегут полную окружность и следовательно в каждый момент
времени расстояние между ними будет равно разности Rк – Rл то есть
независимым от времени. Что и требовалось доказать.
Интересный вопрос. Итак, мы выяснили, что один лис может не отстать от
кролика, не означает ли, что группа лисиц (и может быть даже не очень большая)
в состоянии кролика поймать.
Данный пример был призван показать, что задача
не тривиальна и нуждается в тщательном исследовании, которым мы далее и
займёмся. А для начала сформулируем ещё раз цель исследования:
Главная цель: Выяснить, существует ли оптимальная стратегия как для
убегающего, так и для догоняющего и если да то, как её построить. А оптимальная
стратегия – это такая стратегия, которая гарантирует наилучший результат
независимо от поведения противника
Для того чтобы построить какую-либо теорию, мы
должны строго описать основные понятия и объекты, а также сформулировать
какие-то основные утверждения которые будут служить аппаратом для получения
нового знания.
Игра на преследование, убегающий игрок,
группа преследователей – Это основные
понятия, их смысл ясен интуитивно.
Простое движение. Простым движением называется такое движение, при котором
расстояние пройденное игроком является линейной функцией от времени s(t)=kt. Для тех,
кто хорошо изучал физику эта формула возможно ассоциируется с равномерным,
прямолинейным движением. Однако это совсем не обязательно. Данная формула может
описывать движение, в котором вектор (а наша формула скалярная, а не векторная)
скорости с течением времени меняет направление, но не меняет своего модуля.
Игра на преследование с простым движением. Такая игра – это игра в которой движение любого игрока – это
простое движение
Решение игры. Найти решение игры – значит определить оптимальную
стратегию для всех участников игры и найти оптимальное время преследования.
Оптимальное время преследования. Время T преследования называется оптимальным если выполняются
следующие условия:
1.
При любом поведении убегающего игрока
существует способ поведения преследователей гарантирующий встречу хотя бы
одного из преследователей с убегающим игроком не позже времени T.
2.
Для убегающего игрока существует способ
поведения, гарантирующий невозможность встречи с преследователями раньше
времени T.
Гарантированное время преследования. Если для времени Т выполнено только первое из условий
описанных для оптимального времени преследования, то время Т это
гарантированное время преследования.
Игра с линией жизни. Пусть область, в которой происходит игра представляет собой
выпуклую область. Её граница называется линией жизни, а игра соответственно
игрой с линией жизни, если цель убегающего игрока – достичь линии жизни, а цель
преследователей соответственно не допустить этого события.
Множество достижимости – это область плоскости каждую точку которой игрок может
достичь не позже чем за время Т двигаясь по какой-либо траектории по закону
простого движения.
Зоны убегания и зоны встречи. Зона убегания – это множество точек плоскости в которых для
убегающего игрока есть траектория убегания от преследователей. Соответственно
зона встречи – это множество точек в которых не существует траектории убегания.
Утверждение первое: Множество достижимости представляет собой круг.
Доказательство: Ясно, что самая удаленная точка
множества достижимости (удалённая от исходной) это точка до которой игрок
движется по прямой. Построим множество всех прямых проходящих через исходную
точку. В силу однородности свойств плоскости движение вдоль одной из этих
прямых ничем не отличается от движения вдоль другой прямой из чего следует, что
на каждой из прямых самая удалённая точка множества достижимости находится на
одинаковом расстоянии от исходной точки. А геометрическое множество точек
находящихся на одинаковом расстоянии от некоего центра называется окружностью.
В свою очередь геометрическое место точек ограниченных окружностью называется
кругом, что и требовалось доказать.
Утверждение второе. Пусть убегающий игрок находится в некоторой точке, которую
мы назовём исходной. Построим все возможные прямые через исходную точку. Пусть
далее преследователь зная направление движения убегающего игрока, движется по
прямой обеспечивающей встречу за минимальной время. Тогда множество всех точек
встречи представляет собой окружность.
Обозначения:
P – Преследователь
E – Убегающий игрок
A – Точка Апполония
M – Точка встречи
Эта окружность называется окружностью
Апполония, а точка А (самая удалённая точка на прямой PE) называется точкой
Апполония.
Доказательство: Обозначим через vp – скорость
преследователя, а через ve скорость убегающего игрока, тогда ve*|EM|=vp*|PM|. Выберем на
плоскости систему координат x0y таким образом, чтобы E(0)=(0,0), P=(0, – b), тогда
|EM|= Ö x2+y2 |PM|= Ö x2+(y+b)2
Подставив это выражение в первое соотношение
получаем
ve*Ö x2+y2=vp*Ö x2+(y+b)2.
Возведём обе части в квадрат и получим
ve2* [x2+y2]=vp2*[x2+(y+b)2]
(ve2 – vp2)*x2 + (ve2 – vp2)*y2 – 2*b*vp2*y = b2*vp2
Разделим это выражение на (ve2 – vp2) сгруппируем.
Получим следующее:
x2 + (y – b*vp2/(ve2
– vp2))2 = (ve*vp*b)2/(ve2 – vp2)2
Это и есть уравнение окружности, что и
требовалось доказать.
Окружность Апполония и точка Апполония
представляют собой очень важные объекты, имеющие самое серьёзное применение в
теории преследования на плоскости. С их помощью можно оценивать различные
величины, характеризующие процесс преследования и получать траектории движения
игроков. Приведём в подтверждение несколько маленьких теорем.
Теорема 1: Пусть убегающий игрок и
преследователь перемещаются по своим полупрямым. Их положение зависит от
времени. Обозначим его через P(t), E(t) тогда любой отрезок [P(t), E(t)] параллелен
отрезку [P(0), E(0)]. На рисунке внизу эти отрезки выделены:
Теорема 2: Пусть убегающий игрок движется по
прямой пересекающей окружность Апполония в точке М, движение начинается из
точки Е со скоростью V. Тогда преследователь не может встретится с убегающим
раньше чем за время равное |EM| / V
Значение этой теоремы трудно переоценить, так
как она утверждает, что окружность Апполония – это геометрическое место точек в
которых происходит гарантированная встреча при оптимальном поведении обоих
игроков. Не раньше и не позже. А так как оптимальное время преследования одна
из главных целей анализа теории, то становится ясным, почему нужно уметь
строить окружность Апполония
А теперь рассмотрим пример стратегии погони. Цель
стратегии параллельного сближения заключается в том, чтобы обеспечить
преследователю максимальное сближение с убегающим игроком. Ниже на картинке
показаны возможные траектории преследователя и убегающего игрока при
использовании стратегии параллельного преследования.
Обратите внимание, что отрезки соединяющие
точки, в которых произошла смена направления движения, параллельны друг другу.
Этот факт и дал название стратегии.
Почему именно так. Рассмотрим какой-либо участок движения на котором оба
участника погони движутся по прямым. Их поведение оптимально, это означает, что
они движутся к точке встречи расположенной на соответствующей окружности
Апполония (обозначим её А1) и это означает (см. выше), что любые два отрезка
соединяющие положение убегающего и догоняющего параллельны.
Пусть теперь убегающий игрок сменил
направление. Иначе говоря он перешел к другой окружности Апполония (обозначим
её А2). Пусть А точка в которой сменил направление убегающий игрок и В точка в
которой сменил направление догоняющий игрок. Тогда отрезок АВ конец пути по
траектории на А1 и начало пути по траектории А2. Следовательно любой отрезок на
траектории А1 параллелен АВ и в то же время любой отрезок на траектории А2 также
параллелен АВ. Таким образом, параллельность отрезков соединяющих
соответствующие точки на траектории убегающего и догоняющего игроков
сохраняются и при смене направления движения.
Один кролик и несколько лис
Вспомним задачу с которой началась работа. Один
кролик пытается убежать от группы лисиц. Известно, что кролик бегает быстрее
лисиц. Ситуация в которой все лисицы находятся в одной полуплоскости от кролика
можно считать неинтересной. Его скорость выше и он непременно убежит. Какой-то
шанс у лисиц появляется, если им каким-либо образом удастся кролика окружить.
Вот так:
Конечно, сам по себе факт окружения кролика
успеха лисам не гарантирует. Совершенно очевидно, что нужно ещё что-то. Нужно
видимо какое-то специальное отношение расстояний, отношение скоростей. В общем,
между различными факторами образующими ситуацию, необходима какая-то
закономерность.
Основой, известного нам, математического
аппарата является окружность Апполония, но как мы помним из предыдущей лекции
она строилась из тех соображения, что преследователь быстрее убегающего, в
противном случае множество точек встречи просто пустое. Поэтому на первый
взгляд использовать окружность Апполония не получится.
Проведём небольшое формальное преобразование.
Пусть кролик будет преследователем, а лиса убегающим, а чтобы эту новую задачу
свести к предыдущей добавим в условие, что все направления движения от кролика
для лисы запрещены и двигаться она может только к кролику, а кролику разрешено
движение только по прямой из исходной точки. С точки зрения здравого смысла
такая постановка абсурдна, но как математики, мы имеем право так поступить.
Новая задача будет выглядеть так: Несколько лис окружили кролика который
пытается поймать хотя бы одну. Лисы не возражают и ведут себя так, чтобы
максимально облегчить задачу кролика. Вопрос, при каких условиях на любом
направлении движения кролика по прямой, лисы смогут осуществить встречу кролика
хотя бы с одной лисой.
В такой постановке ответ почти очевиден. Кролик
гарантированно встретится с хотя бы одной лисой, если любая прямая по которой
он движется пересечёт хотя одну окружность Апполония. То есть имеет место
следующая ситуация:
Рисунок сделан с учётом того, что скорости лис
могут быть различные, различие в скоростях лис определяет различие в радиусах.
Совокупность окружностей Апполония ограничивают замкнутую внутреннюю область в
которой располагается кролик.
Чтобы сложилась такая ситуация необходимо
какое-то соотношение между скоростями лис, кролика и расстояниями между ними. А
для того, чтобы получить возможность что-либо считать нам нужен радиус
окружности Апполония.
Радиус окружности Апполония:
Для того чтобы получить радиус построим формулу описывающую
окружность.
P –
Преследователь
E –
Убегающий игрок
O –
Центр окружности Апполония
M –
Точка встречи
Выберем систему координат таким образом, чтобы
её начало было в центре окружности Апполония и E=(0,0); P=(0, – b)
Очевидно, что |EM|/Ve=
|PM|/Vp
Или, что тоже самое |EM|* Vp =
|PM|*
Ve
Тогда |EM| = Öx2 + y2 и |PM| =
Ö x2 + (y +b)2
Подставим в предыдущую формулу и получим
VpÖx2 + y2 = VeÖ x2 + (y +b)2
Возведём в квадрат обе части уравнения, сгруппируем и
получим следующее уравнение
x2 + (y – (bVe2)/(Vp2
– Ve2))2 = (Ve Vpb/(Vp2
– Ve2))2
Это действительно уравнение окружности и отсюда мы можем
получить выражение для радиуса.
R = Ve Vpb/(Vp2
– Ve2)
Из этого же уравнения можно определить и
координаты преследователя и убегающего игрока
Знание этих величин, и скоростей позволяет
решить целый ряд задач. Например следующую:
Три лисы окружили кролика таким образом, что
кролик оказался в центре окружности описанной возле равностороннего
треугольника, в вершинах которого находятся лисы. Известно также, что скорости
всех лис одинаковы и известно, что кролику не удастся убежать, причем, если бы
его скорость была хотя бы немного больше он бы убежал. Найти отношение скорости
лис и скорости кролика.
4.
Преследование на плоскости с одним преследователем
В данной игре существует оптимальная стратегия
и для преследователя и для убегающего игрока. Оптимальной стратегией для
преследователя будет стратегия параллельного сближения, а для убегающего игрока
движение по прямой EA где Е начальная точка убегающего игрока и А точка
Апполония.
Оптимальность стратегии для убегающего
очевидна, так как начальная точка преследователя находится на той же самой
прямой. Действительно суть стратегии параллельного сближения в том, что
А) Преследователь изменяет направление движения
в тот же самый момент когда направление движения меняет убегающий игрок.
Б) Новое направление выбирается таким образом,
чтобы преследователь и убегающий игрок встретились на окружности Апполония.
Из этих двух пунктов и следует оптимальность
выбранной стратегии. А теперь определим оптимальное время преследования для
такой игры.
Известно, что точка встречи – это точка
Апполония. Известно, также что оба игрока движутся по прямой, следовательно,
для определения времени встречи существенно важны не абсолютные значения
скоростей, а то насколько скорость преследователя больше скорости убегающего
игрока. Поэтому мы можем перейти к эквивалентной задаче, в которой убегающий
игрок стоит на месте, а преследователь движется со скоростью равно Vp – Ve
В этой задаче преследователь должен пройти
расстояние между его начальным положением и начальным положением убегающего. Мы
уже обозначали это расстояние через b тогда оптимальное время преследование будет дано следующим
выражением t=b/(Vp – Ve).
Вспомним, что игрой с линией жизни называется игра с
границей которую убегающий игрок стремится достичь, а преследователь наоборот
стремится этого не допустить. Сразу из определения следует следующая несложная
теорема:
Теорема: В
игре с линией жизни убегание невозможно только в том случае, когда линия жизни
не пересекается с окружностью Апполония. При этом форма линии жизни
несущественна.
Теорема очевидна и в доказательстве не
нуждается.
Задача «о крысе загнанной в угол»
Из названия уже ясно, что речь идёт о игре в которой
участвуют два игрока действующих внутри некоторого угла. Эта игра не
исследована исчерпывающе. Хорошо известны только некоторые частные случаи,
например преследование в прямом угле.
Теорема. Пусть
убегающий игрок находится в вершине угла а преследователь на биссектрисе
Обозначим скорость убегающего игрока через Ve
тогда, если скорость преследователя Vp = Ö2 Ve, то оптимальное
время преследования t = b / Ve
Доказательство. Очевидно,
что оптимальной стратегией для убегающего игрока (крысы) будет бегство по
катету. Отношение катетов |Pb| и |Eb| равно Ö2. То есть равно
отношению их скоростей.
Лев и человек
Пусть два игрока (лев и человек) находятся внутри круглой
арены и их скорости равны. На главный вопрос «Каковы их шансы?» есть
однозначный ответ, человек при любых начальных условиях сможет убежать.
Попробуем доказать это утверждение.
Синий кружок – это преследователь и зелёный кружок это
убегающий игрок. Для начала выполним небольшой качественный анализ. Проведем
через преследователя и убегающего прямую линию и перпендикуляр к ней. Пусть
убегающий игрок движется по перпендикуляру какое-то время. Построим треугольник
на точках (Лев, Человек, Точка пересечения отрезка по которому движется человек
с окружностью). Этот треугольник тупоугольный и тупой угол при вершине, в которой
находится человек. Это следует из того, что начальное положение Льва и Человека
– это единственное положение, когда данный угол равен 90 градусов, острым этот
угол быть не может, следовательно, он тупой.
Итак мы выяснили, что в момент начала движения угол при
вершине человек увеличивается, мы не можем сказать насколько, но сам факт не
вызывает сомнения.
Далее, человек, конечно же, не сможет двигаться по данному
отрезку бесконечно (впереди стенка ограждения). Поэтому он должен повернуть на
другой отрезок (последовательность отрезков показана на чертеже). Мы вполне
можем момент поворота принять за начальный момент движения. Итак, пусть это
будет начальный момент, но выше было сказано, что в начальный момент движения
угол в вершине Человек увеличивается, следовательно, если он был тупым, он
станет ещё более тупым.
При каждом повороте мы имеем следующий тупоугольный
треугольник
Если как уже было сказано, угол при вершине Человек при
каждом повороте увеличивается, то в пределе треугольник должен сложиться в
отрезок.
А по условию их скорости равны. Естественно, что находясь в
точности позади человека, Лев не имеет никаких шансов его поймать. Единственно,
что нужно человеку это правильно определить последовательность моментов времени
в которые необходимо осуществлять поворот. Попробуем сделать это.
Строгое доказательство. Обозначим через «а» расстояние от точки Человек до точки
пересечение отрезка построенного указанным выше способом с окружностью. А через
ti временные точки в которых человек будет осуществлять
поворот. Пусть эти моменты времени вычисляются следующим образом:
ti = (1/v)*(a/2 + a/3 + …. + a/i) = (a/v)*(1/2 + 1/3 +
…..1/i)
Таким образом, наша теорема справедлива, если полученный
числовой ряд не сходится. Покажем, что это действительно так.
Пусть i = 2k.
Тогда имеем следующее
(1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 … 1/(2k-1 +1) + ….+ 1/2k) >
(1/2 + 1/4 + 1/4 + 1/8 +1/8 +1/8 +1/8 +… 1/2k +… +1/2k) = k/2
Отсюда следует, что при к стремящимся к бесконечности время
также стремится к бесконечности, что и требовалось доказать.
Кстати из этого же следует, что хотя лев и не может догнать
человека, но он может приблизиться к человеку сколь угодно близко. Это следует
из того соображения, что в момент поворота человек разворачивается в сторону
льва. Может показаться странным, что бесконечно большое количество разворотов
не даёт возможность льву поймать человека. Объясняется это очень просто. Угол
разворота каждый раз уменьшается.
Заключение
В процессе выполнения исследования были
рассмотрены различные игры на преследования и были проанализированы алгоритмы
поиска пути. В ходе работы была показана взаимосвязь между играми на
преследование и окружностью Апполония, что позволяет некоторые задачи игр на
преследование решать методами, не выходящими за рамки школьной математики, хотя
в основном данные игры решаются методами теории дифференциальных уравнений.
Список
использованных источников
1. Гервер М.Л., Про лису и собаку // Квант №2, 1973,
с. 39–44.
2. Гервер М.Л., Собака бежит наперерез // Квант №3,
1973, с. 15–18.
3. Петросян Л.А., Преследование на плоскости // Петросян Л.А.,
Рихсеев Б.Б., – М.: Наука. Гл. ред. физ.-мат. лит., 1991. – 96 с.
– (Попул. лекции по мат.; Вып. 61)