在城市犯罪，犯罪嫌疑人开始逃跑。给出了城市 map 。目前，在某些特定地点有一些警车，他们试图制止犯罪嫌疑人。警察和犯罪嫌疑人的车厢具有相同的最大速度。犯罪嫌疑人只有在比任何警车还早到达时才能通过。 map 上有几个导出，犯罪嫌疑人到达任何一个导出时都可以逃避。找到分配警车的算法，以使犯罪嫌疑人无法逃避。
例如，下面是可能的城市 map 。
犯罪嫌疑人开始的地方是白色圆圈，警车是黑色的圆圈，导出处是小方块。在这种情况下，犯罪嫌疑人可以被制止。可能的计划是警车A转到A'，B停留，C转到C'。
对我的问题的等效描述可能是:
我的想法
如果我们有n警车，则效率极低的方法是列出所有可能的k-元素子集P的顶点，使得:
然后，我们可以轻松地确定P中的每个顶点是否都可以在不迟于犯罪嫌疑人的情况下被警察覆盖。
但是，如何列出所有可能的P呢？
@Lior Kogan:
看这张 map :
如果这是双方都知道对方的策略的转弯游戏，那么警察将获胜，因为他只能守护犯罪嫌疑人所在的那一方。
但是在我的问题上，警察输了，因为他永远不知道犯罪嫌疑人会选择哪一方。
最佳答案
编辑2:根据您的说明:
我找不到有关确切提出的问题的任何研究。
另一个密切相关的主题是病毒在网络中的传播和接种。以下是一些论文:
我认为提出的问题非常有趣。尽管我认为这很困难。
很抱歉无法提供进一步的帮助。
--
编辑1:已从警察和强盗游戏更改为图形守卫游戏。
新答案:
这是 Graph Guarding游戏的变体。
一组称为 guard 队的移动代理，试图通过阻止所有可能的攻击来将入侵者拒之于指定区域之外。在用于此设置的图模型中，代理和入侵者位于图的顶点上，并且它们通过连接边在节点之间移动。
请参阅:Guard Games on Graphs和How to Guard a Graph?
在您的变体中，有两个区别:
--
原始答案:
这是经过深入研究的 Cops and Robbers游戏的变体。
警察和强盗游戏是在无向图上进行的，一组警察试图捕获强盗。这场比赛是由Winkler-Nowakowski和Quilliot在1980年代独立定义的，自那时以来，人们对此进行了深入的研究。尽管如此，其计算复杂度仍然是一个悬而未决的问题。
确定k个警察是否可以在无向图上捕获强盗的问题，以及计算给定图上可以捕获强盗的最小警察数量的问题被证明是NP难的。
以下是一些资源: