Найдите алгоритм, чтобы выиграть эту битву с преступностью！

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

Например, ниже представлена ​​возможная карта города.

Белый круг - это начало подозреваемого, черные круги - полицейские машины, а маленькие квадратики - выходы. В этой ситуации подозреваемого можно остановить. Возможный план: полицейская машина A едет к A ', B остается и C едет к C' .

Аналогичное описание моей проблемы может быть таким:

Химическая фабрика (отмечена белым кружком) взрывается, и ядовитая жидкость начинает течь во всех возможных направлениях со скоростью v , и команды спасателей (отмечены черными кружками), максимальная скорость которых также равна v , пытаются заблокировать его. Маленькие квадраты - это сельские жители, которых они защищают.

Мои мысли

Если у нас есть n полицейских машин, крайне неэффективный подход состоит в том, чтобы перечислить все возможные k -элементные подмножества P вершин, таких как что:

a) k <= n;

b) Удаление всех вершин в P на карте приведет к тому, что любой выход будет недоступен для подозреваемого;

c) Удалить любое подходящее подмножество P сделает доступным хотя бы один выход для подозреваемого.

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

Но как мне перечислить все возможные P s?

@ Лиор Коган:

Посмотрите на эту карту:

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

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