Решение задачи преследования

Введение

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

Глава 1 Полицейский и преследователь

Постановка задачи

Полицейский автомобиль Р гонится за автомобилем преступником Е по улицам города; эти улицы образуют идеальную прямоугольную решетку неограниченной протяженности. Скорость автомобиля Р вдвое превышает скорость Е, однако Р обязан подчиняться правилам движения транспорта, которые запрещают левые и U-образные повороты; преступники Е этими правилами пренебрегают. В дискретном варианте этой игры, игроки совершают перемещения поочередно. Если Е находится в точке Е решетки, как показано на рис. 1, то он, когда наступит его очередь передвигаться, может выбрать одну из четырех соседних точек решетки.

Рис 1.

Предположим, что Р находится в точке О и что он переместился сюда предыдущим ходом из точки С. Далее он может или двигаться прямо вперед к точке А, или повернуть направо к В. Будем считать, что поимка преступников произошла, если Р и Е совпадают либо оказываются в соседних точках решетки, т.е. если Р находится в точке О, то Е считается пойманным, если в это время он оказался в одной из девяти точек, отмеченных знаком Х. Игра оканчивается ходом Р, и платой является число его ходов от начала игры до поимки преступников.

Решение задачи преследования

Введем теперь редуцированное пространство. Примем точку О, положение автомобиля Р, за начало координат, а ось у направим по направлению предыдущего перемещения Р. Тогда позиция полностью определяется заданием вектора х=(х,у), где х,у - координаты Е в этой новой, связанной с Р системе координат. Ее можно представить себе как карту города, выполненную в полном масштабе и связанную с какой-либо плоскостью полицейской машины, скажем с ее крышей; тогда положение Е определяется вектором х на этой карте.

Недостатком редуцированного пространства является то, что движение в нем становится, как правило, более сложным. Предположим, что Р переместился на две единицы по направлению к А. это эквивалентно перемещению х на две единицы в обратном направлении к точке А’, как показано на рис.2.

Рис.2

Пусть теперь Р повернул направо к точке В. Направив ось у вдоль вектора ОВ, мы видим, что х при этом оказывается левее В на четыре единицы и впереди на одну. В первоначальной (неподвижной) системе координат это эквивалентно перемещению х в точку В’.

Перейдем теперь непосредственно к построению решения.это достигается последовательным подсчетом V(x) в каждой точке пространства Eps, начиная от области захвата. Точками Eps здесь являются узлы прямоугольной решетки; будем сопоставлять каждой точке соответствующее значение V и отмечать ее этим значением.

Начало координат и восемь его соседних точек, составляющих область захвата, сразу можно отметить значением 0, так как в этих точках Р совершает захват, не сделав ни одного хода. Принимая во внимание, что игра оканчивается ходом Р, можно сразу найти и отметить точки, для которых V=1; на рис.3 они отмечены цифрой 1.

Рис.3

Начиная с этого момента процесс приобретает общность. Следующий

шаг состоит в отыскании таких узлов решетки, которые с точки зрения Е ограничены значениями 0 и 1, а именно таких х, что если бы Е находился в х, то все четыре точки, куда он мог бы отсюда перемещаться, уже были бы отмечены, причем по крайней мере одна из них - с значением 1.. Далее выделим из точек, для которых значение V еще пока не установлено, такие, что один ход Р может перевести их внутрь области, окруженной пунктирной линией. Легко видеть, что этому условию удовлетворяют четыре точки: две из них, отмеченные а, соответствуют случаю, когда Р движется прямо вперед, и две, отмеченные b, когда он сворачивает вправо. Следовательно, точкам a и b отвечает значение V=2.

В самом деле, проверим это последнее утверждение. Если х находится в одной из точек a или b, то Р может перевести х в одну из точек, двигаясь прямо либо сворачивая (такие перемещения являются частью его оптимальной стратегии). Теперь наступает очередь для Е; его оптимальная стратегия предписывает ему переместиться в точку с наибольшим значением V, которое здесь равно 1. Затем снова движется Р, причем мы уже знаем, что он может из этого положения осуществить захват за один ход, сделав таким образом всего два хода.

Дальнейшие шаги нахождения V аналогичны описанным. Предположим, что точки со значением V, равными 0, 1, 2,…, n, найдены и отмечены. Пусть множество S состоит из таких точек х, для которых все четыре соседние точки отмечены, и по крайней мере одна из них отмечена значением n. Теперь если есть еще такие неотмеченные точки, что одно перемещение Р переводит их в S, то мы сопоставляем этим точкам значение V, равное n+1.

Для V=11 получим фигуру, изображенную на рис. 4, и обнаружим, что дальнейшие шаги невозможны; построение завершено.

Рис. 4