Учебно-исследовательская работа
«Преследованиена плоскости»
Введение
Заключается задача в очень простой вещи. Естьпреследователи, один или группа, и есть некто, кто пытается от них убежать. Анам важно понять – это очень просто убегать и догонять или это можно делатьмножеством способов отличающихся друг от друга эффективностью. И трудно линайти наиболее эффективный (или оптимальный) способ погони или наоборотбегства.
Прежде чем приступать к анализу рассмотримситуацию, которая на первый взгляд кажется простой. Пусть некоторый кусокплоскости ограждён забором в форме окружности и в этом загоне лис пытаетсяпоймать кролика который бегает несколько быстрее лиса. Очевидно, что у лиса небыло бы никаких шансов, если бы кролик имел возможность бежать по прямой. Вэтом случае при любой стратегии поведения лиса расстояние между ними бы толькоувеличивалось. Стена может быть причиной по которой кролику придётсяразвернуться и побежать в сторону лиса и здесь для лиса возникает уникальнаявозможность поймать кролика.
Однако эта возможность реальна только для оченьспециальной формы площадки и при не очень умном поведении кролика. Но и присамой простой форме – окружности у лиса есть интересная возможность не отстатьот кролика даже при существенном различии в скоростях. Покажем, как он можетэто осуществить.
Предварительное замечание. Цель кролика находиться как можно дальше от лиса. Из этогоследует, что при необходимости смены направления кролик должен осуществлять этуперемену так, чтобы его направление движения составляло не острый угол снаправлением движения лиса (иначе он начнёт сближение). Необходимость же сменынаправления возникает при угрозе столкновения со стенкой. Максимально тупойугол кролик может обеспечить себе, двигаясь вдоль стенки. Отсюда следует, чтопри заборе имеющим форму окружности оптимально для кролика бежать по окружностикак можно большего радиуса, то есть вдоль стены.
Как же в этом случае вести себя лису. Предположим, что у лиса скорость в два раза меньше. Тогдаесли он будет бежать по окружности центр которой будет совпадать с центромокружности кролика но длина её будет в два раза меньше, то за одно и тоже времяи кролик и лис оббегут полную окружность и следовательно в каждый моментвремени расстояние между ними будет равно разности Rк – Rл то естьнезависимым от времени. Что и требовалось доказать.
Интересный вопрос. Итак, мы выяснили, что один лис может не отстать откролика, не означает ли, что группа лисиц (и может быть даже не очень большая)в состоянии кролика поймать.
Данный пример был призван показать, что задачане тривиальна и нуждается в тщательном исследовании, которым мы далее изаймёмся. А для начала сформулируем ещё раз цель исследования:
Главная цель: Выяснить, существует ли оптимальная стратегия как дляубегающего, так и для догоняющего и если да то, как её построить. А оптимальнаястратегия – это такая стратегия, которая гарантирует наилучший результатнезависимо от поведения противника
Для того чтобы построить какую-либо теорию, мыдолжны строго описать основные понятия и объекты, а также сформулироватькакие-то основные утверждения которые будут служить аппаратом для получениянового знания.
1 Основные понятия
Игра на преследование, убегающий игрок,группа преследователей – Это основныепонятия, их смысл ясен интуитивно.
Простое движение. Простым движением называется такое движение, при которомрасстояние пройденное игроком является линейной функцией от времени s(t)=kt. Для тех,кто хорошо изучал физику эта формула возможно ассоциируется с равномерным,прямолинейным движением. Однако это совсем не обязательно. Данная формула можетописывать движение, в котором вектор (а наша формула скалярная, а не векторная)скорости с течением времени меняет направление, но не меняет своего модуля.
Игра на преследование с простым движением. Такая игра – это игра в которой движение любого игрока – этопростое движение
Решение игры. Найти решение игры – значит определить оптимальнуюстратегию для всех участников игры и найти оптимальное время преследования.
Оптимальное время преследования. Время T преследования называется оптимальным если выполняютсяследующие условия:
1. При любом поведении убегающего игрокасуществует способ поведения преследователей гарантирующий встречу хотя быодного из преследователей с убегающим игроком не позже времени T.
2. Для убегающего игрока существует способповедения, гарантирующий невозможность встречи с преследователями раньшевремени T.
Гарантированное время преследования. Если для времени Т выполнено только первое из условийописанных для оптимального времени преследования, то время Т этогарантированное время преследования.
Игра с линией жизни. Пусть область, в которой происходит игра представляет собойвыпуклую область. Её граница называется линией жизни, а игра соответственноигрой с линией жизни, если цель убегающего игрока – достичь линии жизни, а цельпреследователей соответственно не допустить этого события.
Множество достижимости – это область плоскости каждую точку которой игрок можетдостичь не позже чем за время Т двигаясь по какой-либо траектории по законупростого движения.
Зоны убегания и зоны встречи. Зона убегания – это множество точек плоскости в которых дляубегающего игрока есть траектория убегания от преследователей. Соответственнозона встречи – это множество точек в которых не существует траектории убегания.2 Несколько важных утверждений
Утверждение первое: Множество достижимости представляет собой круг.
Доказательство: Ясно, что самая удаленная точкамножества достижимости (удалённая от исходной) это точка до которой игрокдвижется по прямой. Построим множество всех прямых проходящих через исходнуюточку. В силу однородности свойств плоскости движение вдоль одной из этихпрямых ничем не отличается от движения вдоль другой прямой из чего следует, чтона каждой из прямых самая удалённая точка множества достижимости находится наодинаковом расстоянии от исходной точки. А геометрическое множество точекнаходящихся на одинаковом расстоянии от некоего центра называется окружностью.В свою очередь геометрическое место точек ограниченных окружностью называетсякругом, что и требовалось доказать.
Утверждение второе. Пусть убегающий игрок находится в некоторой точке, которуюмы назовём исходной. Построим все возможные прямые через исходную точку. Пустьдалее преследователь зная направление движения убегающего игрока, движется попрямой обеспечивающей встречу за минимальной время. Тогда множество всех точеквстречи представляет собой окружность./> /> /> /> /> /> />
A />
Обозначения:
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
Значение этой теоремы трудно переоценить, таккак она утверждает, что окружность Апполония – это геометрическое место точек вкоторых происходит гарантированная встреча при оптимальном поведении обоихигроков. Не раньше и не позже. А так как оптимальное время преследования однаиз главных целей анализа теории, то становится ясным, почему нужно уметьстроить окружность Апполония3 Стратегия параллельного сближения
А теперь рассмотрим пример стратегии погони. Цельстратегии параллельного сближения заключается в том, чтобы обеспечитьпреследователю максимальное сближение с убегающим игроком. Ниже на картинкепоказаны возможные траектории преследователя и убегающего игрока прииспользовании стратегии параллельного преследования.
Обратите внимание, что отрезки соединяющиеточки, в которых произошла смена направления движения, параллельны друг другу.Этот факт и дал название стратегии./> /> /> /> /> /> /> /> /> /> /> /> /> /> />
Почему именно так. Рассмотрим какой-либо участок движения на котором обаучастника погони движутся по прямым. Их поведение оптимально, это означает, чтоони движутся к точке встречи расположенной на соответствующей окружностиАпполония (обозначим её А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 = (VeVpb/(Vp2– Ve2))2
Это действительно уравнение окружности и отсюда мы можемполучить выражение для радиуса.
R = VeVpb/(Vp2– Ve2)
Из этого же уравнения можно определить икоординаты преследователя и убегающего игрока
Знание этих величин, и скоростей позволяетрешить целый ряд задач. Например следующую:
Три лисы окружили кролика таким образом, чтокролик оказался в центре окружности описанной возле равностороннеготреугольника, в вершинах которого находятся лисы. Известно также, что скоростивсех лис одинаковы и известно, что кролику не удастся убежать, причем, если быего скорость была хотя бы немного больше он бы убежал. Найти отношение скоростилис и скорости кролика. 4.Преследование на плоскости с одним преследователем
В данной игре существует оптимальная стратегияи для преследователя и для убегающего игрока. Оптимальной стратегией дляпреследователя будет стратегия параллельного сближения, а для убегающего игрокадвижение по прямой EA где Е начальная точка убегающего игрока и А точкаАпполония.
Оптимальность стратегии для убегающегоочевидна, так как начальная точка преследователя находится на той же самойпрямой. Действительно суть стратегии параллельного сближения в том, что
А) Преследователь изменяет направление движенияв тот же самый момент когда направление движения меняет убегающий игрок.
Б) Новое направление выбирается таким образом,чтобы преследователь и убегающий игрок встретились на окружности Апполония.
Из этих двух пунктов и следует оптимальностьвыбранной стратегии. А теперь определим оптимальное время преследования длятакой игры.
Известно, что точка встречи – это точкаАпполония. Известно, также что оба игрока движутся по прямой, следовательно,для определения времени встречи существенно важны не абсолютные значенияскоростей, а то насколько скорость преследователя больше скорости убегающегоигрока. Поэтому мы можем перейти к эквивалентной задаче, в которой убегающийигрок стоит на месте, а преследователь движется со скоростью равно Vp– Ve
В этой задаче преследователь должен пройтирасстояние между его начальным положением и начальным положением убегающего. Мыуже обозначали это расстояние через b тогда оптимальное время преследование будет дано следующимвыражением t=b/(Vp– Ve).5 Игра с линией жизни
Вспомним, что игрой с линией жизни называется игра сграницей которую убегающий игрок стремится достичь, а преследователь наоборотстремится этого не допустить. Сразу из определения следует следующая несложнаятеорема:
Теорема: Вигре с линией жизни убегание невозможно только в том случае, когда линия жизнине пересекается с окружностью Апполония. При этом форма линии жизнинесущественна.
Теорема очевидна и в доказательстве ненуждается.
Задача «о крысе загнанной в угол»
Из названия уже ясно, что речь идёт о игре в которойучаствуют два игрока действующих внутри некоторого угла. Эта игра неисследована исчерпывающе. Хорошо известны только некоторые частные случаи,например преследование в прямом угле.
Теорема. Пустьубегающий игрок находится в вершине угла а преследователь на биссектрисе
/>
Обозначим скорость убегающего игрока через 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)