How Many Lions Are Needed to Clear a Grid?
How Many Lions Are Needed to Clear a Grid?
复制标题
需要多少只狮子才能清除网格？
作者：
Florian Berger;Alexander Gilbers;A. Grüne;R. Klein
我们考虑一个追逃问题，其中一些狮子的任务是清除节点最初被污染的网格图。污染物每单位时间向未被狮子阻挡的每个方向传播一步。每当狮子移动到某个顶点时，该顶点的污染就会被清除。黄铜等人。 [5]表明 n/2 只狮子不足以清除 n x n 网格。在本文中，我们在维度 d > 2 中考虑相同的问题，并证明 θ(nd-1/√d) 狮子对于清除 nd 网格是必要且充分的。此外，我们分析了一个问题变体，其中狮子也被允许从网格顶点跳到不相邻的网格顶点。
We consider a pursuit-evasion problem where some lions have the task to clear a grid graph whose nodes are initially contaminated. The contamination spreads one step per time unit in each direction not blocked by a lion. A vertex is cleared from its contamination whenever a lion moves to it. Brass et al. [5] showed that n/2 lions are not enough to clear the n x n-grid. In this paper, we consider the same problem in dimension d > 2 and prove that Θ(nd-1/√d) lions are necessary and sufficient to clear the nd-grid. Furthermore, we analyze a problem variant where the lions are also allowed to jump from grid vertices to non-adjacent grid vertices.