Глава 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{} относительно полицейского.

E

Max{C1,C2,C3}

C1 C2 C3

Преступник на каждом шаге стремится избежать захвата выбором максимально хода относительно каждого из полицейских, другими словами убегает от того кто его быстрее поймает. После того как первые шаги сделаны, карта поимки перерисовывается и для преступника на карте будут определены новые значения.