网格算法谜题

Question

我有一个宽度和高度确定的网格，每个单元格可以是三个可能的值（在这个插图中呈现为白色、绿色和红色）：

_{（来源：corexii.com）}

您可以选择任意数量的绿色单元格（在下面的插图中用蓝色标记），它们覆盖所选单元格周围预定的正方形半径内的所有红色单元格（用黄色标记）：

_{（来源：corexii.com）}

目标是：

• 尽可能覆盖红色单元格
• 使用尽可能少的蓝色单元格
• 尽快完成

有人对算法有什么想法吗？

我正在研究很多理论，但我最感兴趣的是近似方法，可以快速完成而不是准确。快速得到合理的结果比整天计算最优解更可取。

（上面的插图可能呈现出这些单元格最常见的分布，但不应假定它们类似于所有可能的分布。）

- Core Xii

---

你的目标非常模糊。是否有优先顺序或效用函数？ - Karoly Horvath

需求#3可能很难，因为它要求您证明不存在比您找到的算法更快的算法。 - Kaz

我会使用边界矩形的概念：最小的矩形区域，包含所有红色单元格。我怀疑解决方案将具有这样的属性，即覆盖正方形将保持在此边界矩形内（前提是n适合在该矩形内）。走出矩形范围并没有实现任何效果，因为那里没有红色单元格需要覆盖；你只是减少了该正方形的潜在覆盖面积。 - Kaz

该问题可以转化为解决集合覆盖问题（Set Cover Problem），详见：http://en.wikipedia.org/wiki/Set_cover_problem。注意：这种转化并没有帮助，但我认为值得一提。 - Karoly Horvath

“k”的典型值是多少？它可以很大吗？ - Karoly Horvath

Answer 1

这个问题是重要的NP难问题集合覆盖问题的特例。(宇宙由红色单元格组成，每个集合包含绿色单元格半径内的红色单元格)。 贪心算法能够得到最优结果的对数n因子近似解。

---

templatetypedef指出这个问题是NP难问题的特例并不能证明它本身也是NP难问题。这是我在上面措辞时小心的原因。但是作为一个NP难问题的特例，信号不容忽视：许多特例进一步研究后都变成了NP难问题。

因此，这里简要说明这个问题实际上是NP难的，通过从度数不超过四的平面图顶点覆盖的化简。

假设我们有一个度数不超过四的平面图，例如：

用一个绿色正方形代表每个顶点，并用红色和绿色正方形交替的链表示每条边，使得有偶数个绿色正方形，奇数个红色正方形，并且如果选择了一个绿色正方形，则它只会覆盖其两侧的两个红色正方形。使用半径为2，这是图的一种可能表示：

为了覆盖所有的红色方格，我们需要选择原图中每条边对应的链上至少一半的绿色方格。如果我们在每条链上选择恰好一半的绿色方格，那么就会在每条边的一个端点处留下一个未覆盖的红色方格（我们可以选择哪个端点）。因此，如果我们能找到最小的顶点集合，使得每条边都与该集合中的顶点相邻，则可以获得最小集合的绿色方格。

例如，在这个例子中，如果我们选择顶点a和d，我们可以使用8个绿色方格来覆盖所有的红色方格: 这对应于原图中的最小顶点覆盖:

- Gareth Rees

---

符合第一和第三个标准，但第二个标准未通过。 - Karoly Horvath

这个问题是集合覆盖问题的一个特例，并不意味着它一定很难求解。例如，2-SAT 是 SAT 问题的一个特例，但却有线性时间的解法。 - templatetypedef

是的，如果半径可以是无限大，那么您只需要添加一个蓝色正方形。如果半径很小，则计算也很容易。 - Rusty Rob

@templatetypedef：请查看修改后的答案。 - Gareth Rees

@Karoly：当一个问题是NP难问题时，找到最优解需要指数时间（据我们所知），因此必须做出一些妥协：通常你能做的最好的事情就是在合理的时间内寻找近似解。 - Gareth Rees