我有一些的宽度和高度，其中每个单元可以是三种可能值的网格（呈现为白色，绿色和红色在该图示）：网格算法的益智
illustration http://corexii.com/grid-algorithm-problem-2.png
您可以选择任何数量的绿色细胞（标记在下面的图示蓝色），其覆盖所述选择的细胞周围的预定平方半径（这里）所有红细胞（标记为黄色）：
illustration http://corexii.com/grid-algorithm-problem-3.png
的目标是：
任何人有任何一个算法的想法？
我在看很多的理论，但我最感兴趣的是近似做这个快速而不是准确。快速，合理的结果比整天计算最佳结果要好。
（上面的图示可以呈现这些细胞的最正态分布，但不应当被假定为像的所有可能的分布。）
此问题是重要的NP-硬set cover problem的一种特殊情况。 （宇宙由红色单元组成，每个组由一个绿色单元的半径内的红色单元组成）。greedy algorithm获得最佳结果的因子。
templatetypedef is right to point out这样一个事实，这个问题是一个NP难问题的一种特殊情况并不能证明它实际上是NP难了。这就是为什么我在我的措辞中小心谨慎，而不是暗示后者。但是作为一个NP难题的特殊情况是一个不容忽视的信号：许多特殊情况下进一步调查本身就是NP难题。
所以，这里有一个粗略的草图，说明这个问题实际上是NP-hard，通过在最常见的四个平面图上减少VERTEX COVER。
假设我们有度的至多四个平面图形，例如：
表示由绿色正方形的每个顶点，并且通过红色和绿色的方块，使得交替的链中的每个边缘有偶数个绿色正方形，奇数个红色正方形，每个绿色正方形只会覆盖任何一边的两个红色正方形，如果选择的话。为2的半径，这是图的一个可能的表示：
为了覆盖所有的红色正方形，我们需要选择绿色正方形的至少一半上对应于各链边缘原始图。如果我们在每个链上选择恰好一半的绿色方块，那么在每个边的一端留下一个未覆盖的红色方块（我们可以选择哪一端）。因此，如果我们可以找到最小的一组顶点，那么我们就可以得到最小的一组绿色方块，使得每条边都入射到该组顶点。
在这个例子中，我们可以使用八个绿色方块覆盖红色正方形，如果我们挑顶点一个和d：
与此对应的最小顶点覆盖在原来的图表：
符合第一和第三标准，在第二个标准中不合格 – 2012-03-20 23:32:24
这是集覆盖的特例并不意味着它在计算上很难解决。例如，2SAT是SAT的特例，但具有线性时间解决方案。 – templatetypedef 2012-03-21 00:56:48
是的，如果半径可以是无限的，那么你只需要添加一个蓝色方块。如果半径很小，那么它也很容易计算。 – 2012-03-21 04:04:47
你的目标很模糊。是否有优先顺序或效用函数？ – 2012-03-20 23:09:22
要求＃3可能很难，因为它要求您证明没有算法比找到的算法更快。 – Kaz 2012-03-20 23:11:36
我会使用边界矩形的概念：包含所有红色单元格的最小矩形区域。我怀疑该解决方案将具有覆盖方块在该边界矩形内的属性（前提是'n'能够适合该矩形）。因为没有红细胞可以覆盖，所以在矩形外面横行并没有达到任何效果。你只会减少该广场的潜在覆盖面。 – Kaz 2012-03-20 23:14:18