gpt4 book ai didi

algorithm - 找到一种算法来赢得这场打击犯罪的战斗!

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:26:43 25 4
gpt4 key购买 nike

在一座城市犯下的罪行,嫌疑人开始逃跑。给了一张城市 map 。目前,一些特定地点有一些警车,他们试图阻止嫌疑人。警车和嫌疑人的车有相同的最高速度。只有当嫌疑人比任何警车更早到达该点时,他才能通过该点。 map 上有几个导出,嫌疑人到达其中一个就躲避。找到一种分配警车的算法,使嫌疑人无路可逃。

例如,下面是一张可能的城市 map 。

enter image description here

白色圆圈是嫌疑犯开始的地方,黑色圆圈是警车,小方 block 是导出。在这种情况下,怀疑可以停止。一个可能的方案是警车 AA'B 留下来,CC '.


我的问题的等效描述可能是:

A chemical factory (marked by the white circle) explodes and poisonous fluid starts to flow at each possible direction at speed v, and the rescue teams (marked by black circles) whose maximum speed is also v are trying to block it. The little squares are villagers they are protecting.


我的想法

如果我们有 n 辆警车,一种非常低效的方法是列出所有可能的 k 顶点元素子集 P,这样:

a) k <= n;

b) Remove all vertices in P in the map will cause any exit unreachable to the suspect;

c) Remove any proper subset of P will let at least one exit reachable to the suspect.

然后我们可以很容易地确定 P 中的每个顶点是否都可以在嫌疑人之前被警察覆盖。

但是如何列出所有可能的 P


@Lior Kogan:

看看这张 map :

enter image description here

如果是双方都知道对方策略的回合制博弈,警察会赢,因为他可以只守在嫌疑人走的那一边。

但在我的问题中,警察输了,因为他永远不知道嫌疑人会选择哪一边。

最佳答案

Edit2:根据您的说明:

我找不到任何关于确切提出的问题的研究。

另一个密切相关的主题是网络中的病毒传播和接种。以下是一些论文:

我认为提出的问题很有趣。虽然我相信它是 NP-hard。

很抱歉无法提供更多帮助。

--

Edit1:从警察和强盗游戏更改为图形守卫游戏

新答案:

这是图形守卫游戏的变体。

一组称为守卫的移动代理试图通过阻止所有可能的攻击来阻止入侵者进入指定区域。在此设置的图模型中,代理和入侵者位于图的顶点上,并且它们通过连接边从一个节点移动到另一个节点。

参见:Guard Games on GraphsHow to Guard a Graph?

在您的变体中,有两个区别:

  • 你试图守卫不止一个区域
  • 每个保护区都是一个节点

--

原答案:

这是经过充分研究的警匪游戏的变体。

警匪游戏是在无向图上进行的,其中一群警察试图捕获一名强盗。该游戏由 Winkler-Nowakowski 和 Quilliot 在 1980 年代独立定义,从那时起就被深入研究。尽管如此,它的计算复杂度仍然是一个悬而未决的问题。

确定 k 个警察是否可以在无向图上捕获强盗的问题,以及计算在给定图上可以捕获强盗的最少警察数量的问题被证明是 NP 难的。

这里有一些资源:

关于algorithm - 找到一种算法来赢得这场打击犯罪的战斗!,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7749958/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com