找到一种算法来赢得这场打击犯罪的斗争!
在城市犯下的罪行和犯罪嫌疑人开始逃跑.给出了城市地图.目前,某些地方有一些警车,他们试图阻止嫌犯.警察的汽车和嫌疑人的最高速度相同.如果嫌疑人比任何一辆警车更早到达,嫌疑人只能通过一个点.地图中有几个出口,如果他到达任何一个,嫌疑人就会逃避.找到一个分配警车的算法,这样嫌疑人就无法逃避.
例如,下面是一个可能的城市地图.
白色圆圈是嫌疑人开始的地方,黑色圆圈是警车,小方块是出口.在这种情况下,可以阻止嫌疑人.一个可能的计划是警车A前往A',B停留和C前往C'.
我的问题的等效描述可能是:
一个化学工厂(用白色圆圈标记)爆炸,有毒液体开始以各种可能的方向高速流动,
v救援队(标有黑圈)的最高速度也v试图阻挡它.小广场是他们正在保护的村民.
我的想法
如果我们有n警车,一种非常低效的方法是列出所有可能的 - k元素P顶点子集,这样:
a)k <= n;
b)删除
P地图中的所有顶点将导致任何出口无法到达嫌疑人;c)删除任何适当的子集,
P让至少一个出口可以到达嫌疑人.
然后我们可以很容易地确定P警察是否可以在不迟于嫌疑人的情况下覆盖每个顶点.
但是如何列出所有可能的Ps？
@Lior Kogan:
看看这张地图:
如果这是一个双方都知道其他战略的转身游戏,那么警察就会赢,因为他可以保护嫌犯所在的一方.
但在我的问题上,警察输了,因为他永远不知道嫌犯可能选择哪一方.
编辑2:根据您的说明:
我找不到任何关于确切提出的问题的研究.
另一个密切的主题是病毒传播和网络接种.以下是一些文章:
我认为提出的问题非常有趣.虽然我相信它是NP难的.
很抱歉无法继续提供帮助.
-
编辑1:从警察和强盗游戏改为图形防护游戏.
新答案:
这是图形保护游戏的变体.
一个名为警卫的移动代理团队试图通过阻止所有可能的攻击来阻止入侵者进入指定区域.在此设置的图形模型中,代理程序和入侵者位于图形的顶点上,它们通过连接边缘从一个节点移动到另一个节点.
请参阅:图表上的Guard游戏以及如何保护图表？
在您的变体中,有两个不同之处:
- 你正试图守卫不止一个地区
- 每个保护区域都是单个节点
-
原始答案:
这是经过充分研究的警察和强盗游戏的变种.
警察和强盗游戏是在无向图上播放的,其中一群警察试图抓住强盗.该游戏由Winkler-Nowakowski和Quilliot在20世纪80年代独立定义,并且自那时以来一直在深入研究.尽管如此,它的计算复杂性仍然是一个悬而未决的问题.
确定k警察是否可以在无向图上捕获强盗的问题,以及计算可以在给定图上捕获强盗的最小警察数量的问题被证明是NP难的.
以下是一些资源:
现在我对我的问题有了更清晰的认识。虽然比警察与强盗游戏或图守卫游戏简单，但它仍然是一个 NP 难题。
这个问题实际上可以分为两个独立的任务：
任务 a)找到一组可能的顶点，使嫌疑人无法到达任何出口。
任务b）验证这组顶点是否能够及时被警车覆盖。
现在我们要证明任务 a)是 NP 完全的。
首先我们考虑何时只有一个出口。看看这个简单的地图：
False如果某个顶点被警察封锁并且True可以通过，则分配给该顶点。我们知道嫌疑人可以逃避，如果A & (B | D) & C == True。现在我们清楚地看到任务a)相当于著名的NP完全布尔可满足性问题。
如果我们有多个出口，只需创建几个布尔表达式并将它们连接起来AND(&)。
任务b）只是一个二分图匹配问题，可以通过匈牙利算法轻松解决。其时间复杂度为O(n^4)。
所以这整个问题是一个 NP 难题。
| 归档时间： |
|
| 查看次数： |
524 次 |
| 最近记录： |