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

Question

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

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

---

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

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

---

Мои мысли

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

a) k <= n; </p>

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

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

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

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

---

@ Лиор Коган:

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

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

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

Answer 1

Редактировать2: На основе ваших разъяснений:

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

Еще одна близкая тема - распространение вирусов и прививка в сетях . Вот несколько статей:

• Стратегии прививок для жертв вирусов и проблема разбиения суммы квадратов
• Предупреждение против червя: кто победит в битве за контроль над крупномасштабной сетью?
• Защита от сетевых инфекций: теоретическая перспектива игры

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

Извините, что больше не могу помочь.

-

Edit1: Изменено с Игра Cops and Robbers на График охранной игры .

Новый ответ:

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

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

См .: Охрана игр на графиках и Как охранять график?

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

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

-

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

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

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

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

Вот несколько ресурсов:

• Глава 6 Игра в полицейских и грабителей на графиках
• О возможности игры в Cops and Robbers
• Сложность игры полицейских и грабителей
• Переговоры о ГРАСТЕ 2011 (см. Гл.3)

Answer 2

Теперь у меня есть более четкое представление о моей проблеме. Хотя это проще, чем Игра в копы и грабители или Игра по защите графиков , тем не менее это трудная задача для NP.

Две отдельные задачи, которые на самом деле можно разделить на эту проблему:

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

Теперь мы собираемся доказать, что Задание а) является NP-завершенным.

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

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

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

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

Так что вся эта проблема - NP-сложная.