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

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

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

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

Эквивалентное описание моей проблемы может быть:

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

Мои мысли

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

a) k <= n;

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

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

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

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

@Lior Kogan:

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

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

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

Ответ 1

Теперь у меня есть более ясное представление о моей проблеме. Хотя это проще, чем игра Cops and Robbers Game или Graph Guarding, тем не менее это проблема NP-hard.

Две отдельные задачи этой задачи можно фактически разделить на:

Задача a) Найдите возможный набор вершин, который разрешит подозреваемому, недоступному для любых выходов.
Задача b) Подтвердить, может ли этот набор вершин быть своевременно закрыт полицейскими машинами.

Теперь мы докажем, что Задача a) NP-полная.

Сначала рассмотрим, когда есть только один выход. Посмотрите на эту простую карту:

Назначьте False вершине, если она заблокирована полицией и True, если она проходима. Мы знаем, что подозреваемый может уклониться, если A & (B | D) & C == True. Теперь мы ясно видим, что Задача а) эквивалентна известной NP-полной Логической проблеме выполнимости.

Если у нас есть несколько выходов, просто создайте несколько булевых выражений и соедините их с AND(&).

Задача b) - это просто проблема двудольного сопоставления графа, которую можно легко решить с помощью венгерский алгоритм. Это временная сложность O(n^4).

Итак, вся эта проблема - NP-hard.

Ответ 2

Редактировать 2: Основываясь на ваших пояснениях:

Я не мог найти никакого исследования относительно поставленной проблемы.

Другой близкий объект - это распространение вирусов и прививка в сетях. Вот несколько работ:

Я думаю, что поставленная проблема очень интересная. Хотя я считаю, что это NP-жесткий.

Извините, что не смог помочь.

Edit1: Изменена из игры для полицейских и разбойников ....

Новый ответ:

Это вариант игры Graph Guarding.

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

Смотрите: Охранные игры на графиках и Как защитить график?

В вашем варианте есть два отличия:

Вы пытаетесь защитить более чем одну область.
Каждая охраняемая область представляет собой одиночный node

Оригинальный ответ:

Это вариант хорошо изученной игры Cops and Robbers.

Игра "Копы и разбойники" воспроизводится на неориентированных графиках, где группа полицейских пытается поймать грабителя. Игра была определена независимо Винклером-Nowakowski и Quilliot в 1980-х годах и с тех пор интенсивно изучается. Несмотря на это, его сложность вычислений по-прежнему остается открытым.

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

Вот некоторые ресурсы: