1.2Решение задачи преследования
Введем теперь редуцированное пространство. Примем точку О, положение автомобиля Р, за начало координат, а ось у направим по направлению предыдущего перемещения Р. Тогда позиция полностью определяется заданием вектора х=(х,у), где х,у- координаты Е в этой новой, связанной с Р системе координат. Ее можно представить себе как карту города, выполненную в полном масштабе и связанную с какой-либо плоскостью полицейской машины, скажем с ее крышей; тогда положение Е определяется вектором х на этой карте.
Недостатком редуцированного пространства является то, что движение в нем становится, как правило, более сложным. Предположим, что Р переместился на две единицы по направлению к А. это эквивалентно перемещению х на две единицы в обратном направлении к точке А’, как показано на рис.2.
| | | | | | | | | | X |
| |  | | E | | | | | |  |
| | | | | | | | | | |
| | | | | | | | | | А’ |
| | | | | |  A | | | | |
| B’ | | | | 0 | 0 | 0 | | | |
| | | | | 0 |  0 | 0 | B | | |
| | | | | 0 | 0 | 0 | | | |
| | | | | | C | | | | |
| | | | | | | | | | |
| | | | | | | | | | |
Рис .2
Пусть теперь Р повернул направо к точке В. Направив ось у вдоль вектора ОВ, мы видим, что х при этом оказывается левее В на четыре единицы и впереди на одну. В первоначальной (неподвижной) системе координат это эквивалентно перемещению х в точку В’.
Перейдем теперь непосредственно к построению решения. это достигается последовательным подсчетом V(x) в каждой точке пространства Eps, начиная от области захвата. Точками Eps здесь являются узлы прямоугольной решетки; будем сопоставлять каждой точке соответствующее значение V и отмечать ее этим значением.
Начало координат и восемь его соседних точек, составляющих область захвата, сразу можно отметить значением 0, так как в этих точках Р совершает захват, не сделав ни одного хода. Принимая во внимание, что игра оканчивается ходом Р, можно сразу найти и отметить точки, для которых V=1; на рис.3 они отмечены цифрой 1.
| | | | | | | | | | | | |
| | | | | | | | | | | ||
| | | | | | | | | | | ||
| | | А | | | | | | | | ||
| | 1 |  1 | 1 | | | | | | | ||
| | 1 | 1 | 1 | А | | | | | | ||
| | 0 | 0 | 0 | 1 | 1 | | | | | ||
| | 0 | 0 | 0 | 1 | 1 | B | | | | ||
| | 0 | 0 | 0 | 1 | 1 | | | | | ||
| | | | | B | | | | | | ||
| | | | | | | | | | | ||
| | | | | | | | | | | ||
| | | | | | | | | | | ||
Рис .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, и обнаружим, что дальнейшие шаги невозможны; построение завершено.
| | | | 8 | 11 | | | | | | | |
| | | | 5 | 8 | | | | | | ||
| | | 3 | 4 | 7 | 10 | | | | | ||
| | | 2 | 3 | 4 | 7 | | | | | ||
| | 1 |  1 | 1 | 3 | 6 | 9 | | | | ||
| | 1 | 1 | 1 | 2 | 3 | 6 | | | | ||
| | 0 | 0 | 0 | 1 | 1 | 5 | 8 | | | ||
| | 0 | 0 | 0 | 1 | 1 | 2 | 3 | | | ||
| 9 | 0 | 0 | 0 | 1 | 1 | 3 | 4 | 5 | 8 | ||
| | 7 | 4 | 3 | 2 | 3 | 4 | 7 | 8 | 11 | ||
| | 10 | 7 | 4 | 3 | 6 | 7 | 10 | | | ||
| | | 8 | 5 | 6 | 9 | | | | | ||
| | | 11 | 8 | | | | | | | ||
Рис. 4
1 2 3 4 5