1.3Реализации поставленной задачи
По поставленной задаче была написана программа
Необходимо выбрать режим управления полицейским(быстрая клавиша F5)
Задаем положение преследуемого по Х и У относительно полицейского, преступник должен находиться в одной из точек карты, которая расположена на форме программы.
Игра начинается по кнопке старт после задании всех необходимых параметров, если положение преследуемого задано вне карты, то программа выдаст сообщение с ошибкой, о невозможности поимки преступника.
При не оптимальном поведении полицейского в поле количество шагов считается количество ходов преследователя до поимки преступника.
На основании изученных результатов в следующей главе получен алгоритм группового преследования.
Глава 2 Групповое преследование
2.1 Постановка задачи группового преследования
Группа полицейских P1,P2,…,Pn преследуют преступника Е по улицам города, которые образуют идеальную прямоугольную решетку неограниченной протяженностью. Скорость преследователей в два раза больше чем скорость преступника, однако полицейские обязаны подчиняться правилам дорожного движения, которые запрещают левые и U-образные повороты, преступник этими правилами пренебрегает. У каждого из полицейских есть своя карта с зоной ответственности, каждый полицейский вступает в погоню когда преступник находится в зоне досягаемости.
Перемещения совершаются поочередно, сначала все преследователи, затем преступник. Игра оканчивается ходом полицейского. И ценой игры считается количество ходов преступника сделанных до его поимки.
Преследователи задаются произвольным образом, в начале игры задан один преследователь, относительно, которого задается положение преступника.
2.2 Решение задачи
Добавим преследователя P2,P3 и посмотрим на карту поимки преступника.
И построим карту поимки с тремя преследователями.
| | | | | 8 | 11 | | | | | | | | | | | | |
| | | | | 5 | 8 | | | | | | | | | | | | |
| | | | 3 | 4 | 7 | 10 | | | | | | | | | | | |
| | | | 2 | 3 | 4 | 7 | | | | | | | | | | | |
| | | | 1 | 1 | 1 | 3 | 6 | 9 | | | | | | | | | |
| | | | 1 | 1 | 1 | 2 | 3 | 9 | | | | | | | | | |
| | | | 0 | 0 | 0 | 1 | 1 | 5 | 8 | | | | 8 | 11 | | | |
| | | | 5,0 | 8,Р2 | 0 | 1 | 1 | 2 | 3 | | | | 5 | 8 | | | |
| | | 3,9 | 4,0 | 7,0 | 10,0 | 1 | 1 | 3 | 4 | 5 | 8 | 9 | 4 | 7 | 10 | | |
| | | 2 | 3,7 | 4,4 | 7,3 | 2 | 3 | 4 | 7 | 8 | 11 | 2 | 3 | 4 | 7 | | |
| | 1 | 1 | 1,10 | 3,7 | 6,4 | Е(9,3) | 6 | 7 | 10 | | 1 | 1 | 1 | 3 | 6 | 9 | |
| | 1 | 1 | 1 | 2,8 | 3,5 | 6,6 | 9 | | | | 1 | 1 | 1 | 2 | 3 | 6 | |
| | 0 | 0 | 0 | 1,11 | 1,8 | 5 | 8 | | | | 0 | 0 | 0 | 1 | 1 | 5 | 8 |
| | 0 | Р1 | 0 | 1 | 1 | 2 | 3 | | | | 0 | Р3 | 0 | 1 | 1 | 2 | 3 |
| 9 | 0 | 0 | 0 | 1 | 1 | 3 | 4 | 5 | 8 | 9 | 0 | 0 | 0 | 1 | 1 | 3 | 4 |
| | 7 | 4 | 3 | 2 | 3 | 4 | 7 | 8 | 11 | | 7 | 4 | 3 | 2 | 3 | 4 | 7 |
| | 10 | 7 | 4 | 3 | 6 | 7 | 10 | | | | 10 | 7 | 4 | 3 | 6 | 7 | 10 |
| | | 8 | 5 | 6 | 9 | | | | | | | 8 | 5 | 6 | 9 | | |
| | | 11 | 8 | | | | | | | | | 11 | 8 | | | | |
Преследуемый находится в точке Е, и находится в зоне досягаемости полицейских Р1, Р2.
P1,P2,P3 выбирают свой ход как одно из двух допустимых направлений , цена по которому меньше положения преступника. Pi вступает в игру, когда преступник находится в его зоне досягаемости
При каждом выборе хода убегающий анализирует положение преступника и выбирает maх(V1,V2,V3), где в свою очередь V1 – количество шагов за которое можно осуществить поимку исходя из текущего положения Р1 и Е, V2 – количество шагов за которое можно осуществить поимку исходя из текущего положения Р2 и Е, V3 – количество шагов за которое можно осуществить поимку исходя из текущего положения Р3 и Е.
После выбора min(V1,V2,V3) преступнику необходимо выбрать оптимальное направление перемещения, относительно каждого полицейского есть четыре направление, каждое из которых соответсует значению на карте, обозначим значения как
, где j-номер полицейского. Выбранное перемещение обозначим за С. Оптимальный ход преступника Сj = max{
} относительно полицейского с номером j.
E
Max{C1,C2,C3}
C1 C2 C3
Преступник на каждом шаге стремится избежать захвата выбором максимально хода относительно каждого из полицейских, другими словами убегает от того кто его быстрее поймает. После того как первые шаги сделаны, карта поимки перерисовывается и для преступника на карте будут определены новые значения.
1 2 3 4 5