Автор: Пользователь скрыл имя, 01 Апреля 2012 в 13:30, курсовая работа
Заключается задача в очень простой вещи. Есть преследователь, и есть некто, кто пытается от него убежать. А нам важно понять – это очень просто убегать и догонять или это можно делать множеством способов отличающихся друг от друга эффективностью. И трудно ли найти наиболее оптимальный способ погони или наоборот бегства.
Аннотация
В данном курсовом проекте изучалась задача простого преследования с одним преследователем и несколькими убегающими. Указываются основные определения и рассматриваются две задачи простого преследования одним преследователем.
Введение
Заключается задача в очень простой вещи. Есть преследователь, и есть некто, кто пытается от него убежать. А нам важно понять – это очень просто убегать и догонять или это можно делать множеством способов отличающихся друг от друга эффективностью. И трудно ли найти наиболее оптимальный способ погони или наоборот бегства.
Игра на преследование, убегающий игрок, группа преследователей – это основные понятия, их смысл ясен интуитивно.
Простое движение. Простым движением называется такое движение, при котором расстояние пройденное игроком из начального положения, является линейной функцией от времени s(t)=ρt, где t – время, в течение которого происходило движение, s(t) – путь, пройденный игроком из начального положения, ρ – путь проходимый игроком в единицу времени, называется линейной скоростью. При простом движение ρ является постоянной и не зависит от времени.
Таким образом, простое движение игрока из начального местоположения на плоскости есть движение по любой криволинейной траектории.
Игра
на преследование с простым
Простое движение по ломанным с конечным числом вершин. Такая игра, в которой игрок может изменять направление своего движения конечное число раз.
Решение игры. Найти решение игры – значит определить оптимальную стратегию для всех участников игры и найти оптимальное время преследования.
Оптимальное время преследования. Время преследования называется оптимальным, если выполняются следующие условия:
Множество достижимости – это область плоскости каждую точку, которой игрок может достичь не позже чем за время, двигаясь по какой-либо траектории по закону простого движения.
Множество достижимости – это область плоскости каждую точку, которой игрок может достичь не позже чем за время, двигаясь по какой-либо траектории по закону простого движения.
Лемма 1. Множество достижимости игрока P представляет собой круг с центром в точке P(0) и радиусом ρt.
Пусть преследователь P и убегающий E перемещаются по плоскости в соответствии с простым движением с постоянными линейными скоростями ρ и σ, ρ>σ>0, и в начале игры |P(0)E(0)|=b 0.
Предположим, что игрок E, начиная с момента времени перемещается по полупрямой . Пусть игрок P зная это направление движения игрока E, начиная с момента , перемещается по некоторой прямой , обеспечивая встречу с E в точке М. Тогда должно выполнятся неравенство: ρ|E(0)M|=σ|P(0)M| (1).
Лемма 2. Геометрическое место точек M=(x, y), удовлетворяющее уравнению (1), является окружностью.
Окружность S называется окружностью Аполлония, соответствующая положениям P(0)=(0, -b) и E=(0, 0), где , .
Лемма 3. Пусть М – некоторая точка на окружности Аполлония S и игроки P и Е перемещаются по полупрямым и . Тогда для каждого t, 0<t<|E(0)M|/σ, отрезок параллелен отрезку .
Лемма 4. Пусть М – некоторая точка на окружности Аполлония S и игрок Е перемещаются по полупрямым . Тогда преследователь P не может осуществить встречу с E до момента времени |E(0)M|/σ, т.е. |E(0)M|/σ наименьшее время, за которое P может осуществить встречу с E.
Пусть преследователь P и убегающий Е перемещаются на плоскости в соответствии с простым движением с постоянными линейными скоростями ρ и σ, ρ≥σ>0. Систему координат на плоскости выберем таким образом, чтобы в момент времени t=0 игроки P и E находились в положение P(0)=(0, -b) и E=(0, 0), где b=|P(0)E(0)|>0.
Пусть игрок E, начиная с момента времени t=0, перемещается по полупрямой, т.е. с вектор скоростью , , в свою очередь игрок P, начиная с момента времени , движется с вектор скоростью , т.е. по полупрямой .
Пусть в момент времени игрок Е решил изменить направление своего движения и начал перемещаться по некоторой полупрямой, т.е. с вектор скоростью , , тогда начиная с момента времени игрок P движется с вектор скоростью, т.е. по полупрямой .
Если игрок Е в некоторый момент времени снова изменит направление движения, то игрок P изменит направление своего движения вышеописанным способом.
При таком способе преследования игроком P игрока E для всех до момента встречи P с E отрезок параллелен отрезку . Такой способ преследования игроком P убегающего E называется стратегией параллельного сближения или П-стратегией.
Цель стратегии параллельного сближения заключается в том, чтобы обеспечить преследователю максимальное сближение с убегающим игроком.
Лемма 5. Пусть ρ>σ, М некоторая точка на окружности Аполлония S и игрок Е перемещаются по полупрямым . Тогда П-стратегия предписывает для P движение по полупрямой .
Лемма 6. Пусть ρ>σ≥0; тогда для любого , , имеет место неравенство
Три точки: преследователь и преследуемые и , обладая постоянными линейными скоростями, перемещаются на плоскости, имея при этом возможность в каждый момент времени менять направление своего движения. Пусть α – линейная скорость преследователя, а – линейная скорость убегающего. Скорости игроков произвольны, и существенно лишь то, что α .
Предположим, что игроки и действуют согласовано (составляют коалицию ). Выигрыш убегающей коалиции определим как время встречи игрока с последним из убегающих игроков.
Пусть преследователь выбирает один из двух способов поведения:
В этих предположениях будем искать наилучший ответ убегающей коалиции в смысле максимизации времени поимки.
Геометрическое место точек встречи игроков и при их движение по прямым со скоростями α и есть окружность Аполлония D:
где - начальное местоположение игрока .
Обозначим через местоположение преследователя в момент времени t, а через местоположение убегающего в момент времени t (k=1,2).
Предположим, что преследует , а затем . Рассмотри случай когда, траекториями движения являются полупрямые, выходящие из , а движется в противоположную от сторону по прямой (стратегия ), где N – точка встречи P c . Определим, к какой точке окружности Аполлония должен двигаться игрок , что бы время поимки было максимальным.
Пусть – время встречи P c , - время встречи P c при параллельном сближение из позиций , тогда
Справедливо равенство (рис. 1)
где точка лежит на прямой и Следовательно, мы должны решить задачу нахождения .
Так как (рис. 2.) для всех точек N дуги для всех точек N дуги , то достаточно найти точку , на которой достигается
С этой целью рассмотрим семейство эллипсов с фокусами в точках , которые пересекают или касаются ее в точках дуги , т.е. мы рассматриваем всевозможные эллипсы с фокусными расстояниями , . Выберем из этого семейства тот эллипс, который целиком содержит внутри окружность D и касается её. Очевидно, точка касания является искомой точкой . Итак, игрок должен двигаться в направлении точки . Покажем далее, что если траектория движения есть ломаная с n вершинами, то максимальное время встречи игрока при этом уменьшается. Доказательство проведем для случая, когда , а вершина ломаной находится на отрезке .
Если игроки движутся прямолинейно к точке N окружности Аполлония D, то новая такая окружность , соответствующая какой-либо паре промежуточных положений игроков , касается первоначальной в точке . Следовательно, если игрок в момент времени делает разворот, то границей множества , где будет окружность , лежащая внутри D.
Задача сводится к нахождению
Покажем, что максимум достигается в точке .
Замечание. При гомотетии эллипса с центром в точке , он переходит в эллипс , причем касаются в точке . Если коэффициент гомотетии , то выпуклая область G, ограниченная , содержит , если же , то лежит вне G (если уравнение имеет вид , то уравнение эллипса имеет вид где
Из этого замечания следует, что эллипсы с фокусами в точках c фокусными расстояниями соответственно гомотетичны, причем центр гомотетии находится в точке .
Следовательно,
достигается в точке .
Итак, |. Тогда для всех т.е. точка действительно доставляет максимум (1).
Аналогично, если P преследует , а затем , то двигаться к точке , где . Очевидно, убегающий должен двигаться по прямой в противоположную от P сторону.
Теорема. В рассмотренной игре существует ситуация равновесия. Оптимальная стратегия игрока P выбирается из условия
, а оптимальная стратегия игрока является программная стратегия . Значение игры равно
.
Рассмотрим случай, когда преследователь преследует трех убегающих E= и в начале игры выбирает некоторый порядок преследования (. Пусть α – линейная скорость преследователя, а – линейная скорость убегающего. Скорости игроков произвольны, и существенно лишь то, что α .
Найдем наилучший ответ
Мы получили, что игрок должен двигаться к точке (пересечение окружности Аполлония и эллипса с фокусами в точках ), двигается по прямой . Как только происходит поимка игрока , игрок меняет направление своего движения. Игрок должен двигаться к точке (пересечение окружности Аполлония и эллипса с фокусами в точках ), двигается по прямой . Преследователь применяет стратегию параллельного сближения.
Заключение
В ходе выполнения работы были рассмотрены игры на преследования с одним преследователем. Так же для некоторых игр были найдены наиболее оптимальные стратегии погони и бегства, что значительно упрощает решения данных задач.
Литература