炸弹丢弃算法

Question

我有一个n x m由非负整数组成的矩阵.例如:

2 3 4 7 1
1 5 2 6 2
4 3 4 2 1
2 1 2 4 1
3 1 3 4 1
2 1 4 3 2
6 9 1 6 4

"掉落炸弹"会使目标小区的数量和其所有八个邻居的数量减少一个,最小为零.

x x x 
x X x
x x x

什么算法可以确定将所有单元减少到零所需的最小炸弹数量？

B选项(由于我不是一个细心的读者)

实际上问题的第一个版本并不是我想要回答的问题.我没有仔细阅读整个任务,还有其他限制,让我们说:

当行中的序列必须不增加时,简单问题怎么办:

8 7 6 6 5 是可能的输入序列

7 8 5 5 2 因为7 - > 8在序列中生长是不可能的.

也许找到"更容易"的案例的答案将有助于找到更难的解决方案.

PS:我相信当我们有几个相同的情况需要最少的炸弹来清除上线时,我们选择在该行的"左侧"使用大多数炸弹的一个.还有什么证据可能是正确的吗？

Answer 1

有一种方法可以将其简化为一个简单的子问题.

解释,算法和算法提供最优解的原因分为两部分.没有第二个,第一个没有意义,所以我将从为什么开始.

如果你想到轰炸这个矩形(假设一个大矩形 - 还没有边缘的情况)你可以看到,将周边的方形空心矩形减少到0的唯一方法是轰炸周边或轰炸空心矩形在外围的正方形.我将调用周边层1,并将其中的矩形称为第2层.

一个重要的见解是没有点轰炸层1,因为你从中获得的"爆炸半径"总是包含在第2层的另一个方形的爆炸半径内.你应该能够轻松地说服自己.

因此,我们可以减少问题,找到炸毁周界的最佳方法,然后我们可以重复这个,直到所有方格都为0.

但是,当然,如果有可能以不太理想的方式轰炸周边,那么这并不总能找到最佳解决方案,但是通过使用X额外的炸弹可以使内层减少> X炸弹的问题.因此,如果我们将许可者层称为第一层,如果我们在第2层(在第1层内)的某处放置一个额外的X炸弹,我们是否可以减少后来轰炸第2层的努力超过X？换句话说,我们必须证明我们可以贪婪地减少外围.

但是,我们知道我们可以贪婪.因为第2层中没有炸弹可以比第3层中的战略位置炸弹更有效地减少第2层到第0层.并且出于与以前相同的原因 - 我们可以在第3层放置一个会影响每个方块的炸弹第2层炸弹放置在第2层可以.因此,贪婪(在这种贪婪的意义上)永远不会伤害我们.

因此,我们所要做的就是找到通过轰炸下一个内层将许可者减少到0的最佳方法.

我们永远不会受到第一次轰炸角落到0的伤害,因为只有内层的角落可以到达它,所以我们别无选择(并且,周边的任何可以到达角落的炸弹都有一个爆炸半径包含在从内层角落的爆炸半径).

一旦我们这样做,与0角相邻的周边的方块只能从内层到达2个方格:

0       A       B

C       X       Y

D       Z

此时,周边实际上是一个封闭的一维环,因为任何炸弹都会减少3个相邻的正方形.除了角落附近的一些奇怪之外 - X可以"击中"A,B,C和D.

现在我们不能使用任何爆炸半径技巧 - 每个方格的情况是对称的,除了怪异的角落,甚至没有爆炸半径是另一个的子集.请注意,如果这是一行(如Panic Panic所讨论的)而不是闭环,那么解决方案就是微不足道的.终点必须减少到0,并且永远不会让你轰炸终点附近的点,再次因为爆炸半径是一个超集.一旦你的端点为0,你仍然有一个新的端点,所以重复(直到该行全部为0).

因此,如果我们可以最优地将图层中的单个正方形减少到0,我们就有了一个算法(因为我们已经切割了循环,现在有一个带有端点的直线).我相信在广场附近的爆炸具有最低值(给你2个选项),使得最低值的2个方格中的最高值是最小可能(你可能必须拆分你的轰炸来管理这个)将是最佳的但我不(但？)有证据.

Answer 2

Pólya说:"如果你无法解决问题,那么你可以解决一个更容易解决的问题:找到它."

明显更简单的问题是一维问题(当网格是单行时).让我们从最简单的算法开始 - 贪婪地轰炸最大的目标.什么时候出错？

鉴于1 1 1,贪婪算法对它首先轰炸的哪个细胞无动于衷.当然,中心细胞更好 - 它同时将所有三个细胞归零.这表明一种新的算法A,"炸弹以最小化剩余的总和".这个算法何时出错？

鉴于1 1 2 1 1,算法A在轰炸第2,第3或第4个细胞之间无动于衷.但轰炸第二个细胞离开0 0 1 1 1比轰炸第三个细胞更好1 0 1 0 1.如何解决？轰炸第三个细胞的问题在于它让我们左侧工作并向右侧工作,必须单独完成.

怎么样"炸弹最小化剩余的总和,但最大化左边的最小值(我们轰炸的地方)加上最小的右边".调用此算法B.此算法何时出错？

编辑:阅读评论后,我同意一个更有趣的问题是一维问题的变化,以便结束联合.很想看到任何进展.

Answer 3

因为我没有时间,所以我不得不停止部分解决方案,但希望即使这个部分解决方案也能提供一些解决这个问题的潜在方法的见解.

当遇到一个难题时,我想提出更简单的问题来培养对问题空间的直觉.在这里,我采取的第一步是将这个二维问题简化为一维问题.考虑一条线:

0 4 2 1 3 0 1

不知何故,你知道你需要在4现场或附近轰炸4次以使其降低到0.由于现场的左侧是较低的数字,轰炸0或4过度轰炸没有任何好处2.事实上,我相信(但缺乏严格的证据)轰炸2直到4现场降至0至少与任何其他策略一样好,将其4降低到0.一个人可以在战略中从左到右继续前进像这样:

index = 1
while index < line_length
  while number_at_index(index - 1) > 0
    bomb(index)
  end
  index++
end
# take care of the end of the line
while number_at_index(index - 1) > 0
  bomb(index - 1)
end

几个样本轰炸订单:

0 4[2]1 3 0 1
0 3[1]0 3 0 1
0 2[0]0 3 0 1
0 1[0]0 3 0 1
0 0 0 0 3[0]1
0 0 0 0 2[0]0
0 0 0 0 1[0]0
0 0 0 0 0 0 0

4[2]1 3 2 1 5
3[1]0 3 2 1 5
2[0]0 3 2 1 5
1[0]0 3 2 1 5
0 0 0 3[2]1 5
0 0 0 2[1]0 5
0 0 0 1[0]0 5
0 0 0 0 0 0[5]
0 0 0 0 0 0[4]
0 0 0 0 0 0[3]
0 0 0 0 0 0[2]
0 0 0 0 0 0[1]
0 0 0 0 0 0 0

从一个需要以某种方式走下去的数字开始的想法是一个吸引人的想法,因为找到一个解决方案突然变得可行,因为有些人声称至少与所有其他解决方案一样好.

在复杂性的下一步,至少同样好的搜索仍然可行是在董事会的边缘.我很清楚,轰炸外缘并没有任何严格的好处; 你最好一次轰炸现场并免费获得三个其他空间.鉴于此,我们可以说轰炸边缘内部的环至少与轰炸边缘一样好.此外,我们可以将这与直觉相结合,即在边缘内部轰炸正确的边缘实际上是将边缘空间降低到0的唯一方法.更重要的是,找出最优策略非常简单(因为它在将角落数量降至0,我们把它们全部放在一起,可以更接近二维空间中的解决方案.

鉴于对角落件的观察,我们可以肯定地说,我们知道从任何起始板到各个角落都有零的板的最佳策略.这是这种电路板的一个例子(我借用了上面两个线性电路板的数字).我用不同的方式标记了一些空格,我将解释原因.

0 4 2 1 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

人们会注意到在顶行非常类似于我们之前看到的线性示例.回顾我们之前的观察结果,将顶行全部降为0的最佳方法是轰炸第二行(x行).没有办法通过轰炸任何行来清除顶行,y并且没有额外的好处来轰炸顶行轰炸行上的相应空间x.

我们可以应用上面的线性策略(轰炸x行上的相应空格),仅关注我们自己的顶行而不是其他任何东西.它会是这样的:

0 4 2 1 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 3 1 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 2 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 1 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 0 0 0 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

在最后两次爆炸中,这种方法的缺陷变得非常明显.很明显,因为这降低了唯一的爆炸点4在第二行的第一列数字是第一x和y.最后两次爆炸明显不如仅仅轰炸第一次爆炸x,这将完全相同(关于顶行的第一个位置,我们没有其他方式清除).由于我们已经证明我们当前的战略不是最理想的,因此显然需要对战略进行修改.

在这一点上,我可以在复杂性上退一步,只关注一个角落.让我们考虑一下这个:

0 4 2 1
4 x y a
2 z . .
1 b . .

很明显地想把空间的唯一途径4降至零是轰炸的某种组合x,y和z.在我的脑海中有一些杂技,我相当确定最佳解决方案是炸x三次,然后a再炸b.现在问题是如何弄清楚我是如何达到这个解决方案的,如果它揭示了我们可以用来解决这个局部问题的任何直觉.我注意到没有轰炸y和z空间.试图找到一个轰炸那些空间的角落有意义产生一个看起来像这样的角落:

0 4 2 5 0
4 x y a .
2 z . . .
5 b . . .
0 . . . .

对于这一点,我很清楚,最佳解决方案是轰炸y5次和z5次.让我们更进一步.

0 4 2 5 6 0 0
4 x y a . . .
2 z . . . . .
5 b . . . . .
6 . . . . . .
0 . . . . . .
0 . . . . . .

这里,感觉类似地直观的,最优的解决方案是轰炸a和b6次,然后x4倍.

现在它变成了一个如何将这些直觉转化为我们可以建立的原则的游戏.

希望继续!

Answer 4

对于更新的问题,简单的贪婪算法可以提供最佳结果.

将A [0,0]炸弹丢弃到单元A [1,1],然后将A [1,0]炸弹丢弃到单元A [2,1],并向下继续此过程.要清除左下角,请将最大值(A [N-1,0],A [N-2,0],A [N-3,0])炸弹丢弃到单元格A [N-2,1].这将完全清理前3列.

使用相同的方法清洁列3,4,5,然后清除列6,7,8等.

不幸的是,这无助于找到原始问题的解决方案.

"更大"的问题(没有"非重复"约束)可能被证明是NP难的.这是一个证明的草图.

假设我们有一个度数最多为3的平面图.让我们找到该图的最小顶点覆盖.根据维基百科的文章,对于程度高达3的平面图,这个问题是NP难的.这可以通过平面3SAT的减少来证明.和平面3SAT的硬度 - 从3SAT减少.这两个证明都出现在教授的"算法下限"的最近演讲中.Erik Demaine(讲座7和9).

如果我们分割原始图形的一些边缘(图中的左图),每个边缘具有偶数个附加节点,则生成的图形(图上的右图)应该具有与原始顶点完全相同的最小顶点覆盖.这种变换允许将图形顶点对准网格上的任意位置.

如果我们仅将图形顶点放置到偶数行和列(以这种方式使得没有两个边缘入射到一个顶点形成锐角),则在有边缘的地方插入"1",并将"零"插入其他网格位置,我们可以使用原始问题的任何解决方案来找到最小顶点覆盖.

Answer 5

这将是一种贪婪的方法:

1. 计算n×m阶的"得分"矩阵,其中得分[i] [j]是如果位置(i,j)被轰炸则矩阵中的点的总扣除.(一个点的最高得分为9,最低得分为0)

2. 顺行移动,找到并选择得分最高的第一个位置(比如说(i,j)).

3. 炸弹(i,j).增加炸弹数量.

4. 如果原始矩阵的所有元素都不为零,则转到1.

我怀疑这是最佳解决方案.

编辑:

我上面发布的贪婪方法虽然有效,但很可能并没有给我们提供最佳解决方案.所以我想应该添加DP的一些元素.

我想我们可以同意,在任何时候,必须针对具有最高"得分"(得分[i] [j] =如果(i,j)被轰炸的点数的总扣除)的一个位置.从这个假设开始,这是新方法:

NumOfBombs(M):(返回所需的最小爆炸次数)

1. 给定矩阵M的阶数为n X m.如果M的所有元素都为零,则返回0.

2. 计算"得分"矩阵M.

   令k个不同的位置P1,P2,... Pk(1 <= k <= n*m),是具有最高分数的M中的位置.

3. 返回(1 + min(NumOfBombs(M1),NumOfBombs(M2),...,NumOfBombs(Mk)))

   其中M1,M2,...,Mk是我们分别轰炸位置P1,P2,...,Pk的结果矩阵.

此外,如果我们希望除此之外还有核心位置,我们必须跟踪"min"的结果.

Answer 6

您可以将此问题表示为整数编程问题.(这只是解决此问题的可能解决方案之一)

得分:

a b c d
e f g h
i j k l
m n o p

人们可以写出16个方程,其中例如f点

f <= ai + bi + ci + ei + fi + gi + ii + ji + ki   

最小化所有索引和整数解的总和.

解决方案当然是这些索引的总和.

通过在边界0上设置所有xi可以进一步简化这一点,因此在此示例中最终得到4 + 1个等式.

问题是没有解决这些问题的微不足道的算法.我不是这方面的专家,但解决这个问题就像线性规划是NP难的.

Answer 7

这是一个部分答案,我试图找到一个下限和上限,可能是可能的炸弹数量.

在3x3和更小的电路板中,解决方案通常是最大编号的电池.

在大于4x4的电路板中,第一个明显的下限是角的总和:

*2* 3  7 *1*
 1  5  6  2
 2  1  3  2
*6* 9  6 *4*

然而,你安排炸弹,不可能用少于2 + 1 + 6 + 4 = 13的炸弹清除这个4x4板.

在其他答案中已经提到过,将炸弹放在第二个角落以消除角落并不比将炸弹放在角落本身更糟糕,因此给予了董事会:

*2* 3  4  7 *1*
 1  5  2  6  2
 4  3  4  2  1
 2  1  2  4  1
 3  1  3  4  1
 2  1  4  3  2
*6* 9  1  6 *4*

我们可以通过在第二个角落放置炸弹来给角落归零,从而得到一个新的棋盘:

 0  1  1  6  0
 0  3  0  5  1
 2  1  1  1  0
 2  1  2  4  1
 0  0  0  0  0
 0  0  0  0  0
 0  3  0  2  0

到现在为止还挺好.我们需要13枚炸弹来清理角落.

现在观察下面标记的数字6,4,3和2:

 0  1  1 *6* 0
 0  3  0  5  1
 2  1  1  1  0
*2* 1  2 *4* 1
 0  0  0  0  0
 0  0  0  0  0
 0 *3* 0  2  0

没有办法使用单个炸弹轰炸任何两个细胞,所以最小炸弹增加了6 + 4 + 3 + 2,所以加上我们用来清除角落的炸弹数量,我们得到的最小这张地图所需的炸弹数量已成为28枚炸弹.用不到28枚炸弹清除这张地图是不可能的,这是这张地图的下限.

您可以使用贪心算法来建立上限.其他答案表明,贪婪算法产生的解决方案使用28枚炸弹.由于我们早先已经证明没有最佳解决方案可以少于28枚炸弹,因此28枚炸弹确实是最佳解决方案.

当贪婪和找到上面提到的最小边界的方法虽然没有收敛,但我想你必须回去检查所有组合.

查找下限的算法如下:

1. 选择编号最大的元素,将其命名为P.
2. 将所有单元格标记为距离P和P本身两步远不可读.
3. 将P添加到minimums列表中.
4. 重复步骤1直到所有单元格都不可用.
5. 求和minimums列表得到下限.

Answer 8

您的新问题(跨行的非减少值)很容易解决.

观察左列包含最高数字.因此,任何最佳解决方案必须首先将此列减少到零.因此,我们可以对此列执行1-D轰炸,将其中的每个元素减少为零.我们让炸弹落在第二列上,这样它们就会造成最大的伤害.我认为,这里有很多关于1D案例的帖子,所以我觉得在跳过这个案子时我是安全的.(如果你想让我描述一下,我可以.)由于性能下降,最左边的三列将全部减少到零.但是,我们可以在这里使用最少数量的炸弹,因为左列必须归零.

现在,一旦左列被归零,我们只需修剪现在归零的最左边三列,并用现在减少的矩阵重复.这必须为我们提供最佳解决方案,因为在每个阶段我们都使用可证明的最小数量的炸弹.

Answer 9

如果你想要绝对最优解来清理棋盘，你将不得不使用经典的回溯，但是如果矩阵很大，那么需要很长时间才能找到最佳解，如果你想要一个“可能”的最优解，你可以使用贪心算法，如果您需要帮助编写算法，我可以帮助您

想一想，这是最好的办法。在那里制作另一个矩阵，存储通过在那里投下炸弹而删除的点，然后选择具有最大点的单元格并将炸弹投在那里更新点矩阵并继续。例子：

2 3 5 -> (2+(1*3)) (3+(1*5)) (5+(1*3))
1 3 2 -> (1+(1*4)) (3+(1*7)) (2+(1*4))
1 0 2 -> (1+(1*2)) (0+(1*5)) (2+(1*2))

对于每个值大于 0 的相邻单元格，单元格值 +1