网格算法拼图

Question

我有一个宽度和高度的网格,其中每个单元格可以有三个可能的值(在此图中显示为白色,绿色和红色):

您可以选择任意数量的绿色单元格(下图中标记为蓝色),其中覆盖所选单元格周围预定方形半径(此处为2)的所有红色单元格(标记为黄色):

目标是:

任何人对算法都有任何想法？

我正在研究很多理论,但我最感兴趣的是近似快速而非准确地做到这一点.快速,合理的结果比整天计算最佳结果更可取.

(上面的插图可能会显示这些单元格的最正态分布,但不应假设它们类似于所有可能的分布.)

Answer 1

这个问题是重要的NP-hard set cover问题的一个特例.(宇宙由红色单元组成,每个集合由一个绿色单元的半径内的红色单元组成.)贪婪算法在最佳结果的log n因子内.

templatetypedef是正确的指出,这个问题是NP难问题的一个特例,并不能证明它实际上也是NP难的.这就是为什么我在上面的措词中小心谨慎而不是暗示后者.但作为一个NP难问题的一个特例是一个不容忽视的信号:许多特殊情况转向进一步调查,本身就是NP难的.

因此,这是一个粗略的草图,这个问题实际上是NP难的,通过减少VERTEX封面,最多可以获得四分之一的平面图.

假设我们有一个最多四度的平面图,例如:

四个顶点连接abcda和ad

用绿色方块表示每个顶点,每个边缘用红色和绿色方块的交替链,这样就有偶数个绿色方块,奇数个红色方块,每个绿色方块只覆盖两个红色方块如果选择,任何一方.半径为2时,这是图表的一种可能表示:

根据覆盖问题表示原始图

为了覆盖所有红色方块,我们需要在每个链上选择至少一半绿色方块,对应于原始图形的边缘.如果我们在每条链上选择正好一半的绿色方块,那么在每条边的一端留下一个未被覆盖的红色方块(我们可以选择哪一端).因此,如果我们能够找到最小的顶点集,使得每个边都入射到该集合中的顶点,那么我们得到最小的绿色正方形集.

在示例中,如果我们选择顶点a和d,我们可以使用八个绿色方块覆盖红色方块:

最小封面,选择八个绿色方块,蓝色

这对应于原始图中的最小顶点覆盖:

最小顶点覆盖