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 | ||||||||||||
| 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 | ||||
| 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{ 
} относительно полицейского.
E
Max{C1,C2,C3}
C1 C2 C3
Преступник на каждом шаге стремится избежать захвата выбором максимально хода относительно каждого из полицейских, другими словами убегает от того кто его быстрее поймает. После того как первые шаги сделаны, карта поимки перерисовывается и для преступника на карте будут определены новые значения.
Глава 3 Программная реализация
3.1 Описание интерфейса
После нажатия на быструю клавишу(F2)начинается новая игра и рисуется сетка. Выбирается управление полицейским(F5), задаются координаты преступника относительно полицейского P1 исходя карты, чтобы просмотреть её на форме необходимо нажать «карта», по желанию можно задать дополнительных полицейских в поле количество и расположить их на карте. Затем начинается игра по кнопке старт, результат выводится в поле цена игры, при неоптимальном режиме, подсчитывается количество шагов полицейского от начала игры до поимки преступника.
3.2 Описание алгоритма программы
Программа предназначена для реализации задачи группового преследования для решения поставленной задачи используется метод объектное ориентированного программирования программа написана на языке C++ с использованием среды для разработки BorlandC++ Builder 6. Ресурсов для работы требует минимальных. Входные данные это координаты преступника относительно полицейского. выходные данные это колличество шагов за которое полицейский поймает преступника и наглядное представление оптимального пути поимки. Правильность работы можно проверить аналитическим путем, посмотрев какой результат должен быть из теоретического представления.
3.3 Пример работы программы
Рассмотрим пример работы программы
Задаем координаты преступника относительно первого полицейского, случайным образом вводим количество полицейских.
