投弹算法

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 2不可能，因为7-

也许为“更容易”的案例找到答案会有助于为更难的案例找到解决方案。

附言：我相信，当我们有几个相同的情况需要最少的炸弹来清除上限时，我们会选择一个使用最多炸弹的排在“左边”。还有可能是正确的证据吗？

Answer 1

由于时间不够，我不得不只停留在部分解决方案上，但希望即使是这个部分解决方案也能为解决这个问题的一种潜在方法提供一些见解。

当面对难题时，我喜欢提出更简单的问题来培养对问题空间的直觉。在这里，我采取的第一步是将这个二维问题简化为一维问题。考虑一条线：

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

从一个需要以某种方式下降的数字开始是一个很有吸引力的想法，因为它突然变得可以找到一个解决方案，正如一些人所声称的，至少和所有其他解决方案一样好。

复杂性的下一步，即至少同样好的搜索仍然是可行的，是在董事会的边缘。我很清楚，轰炸外缘从来没有任何严格的好处；你最好先轰炸一个地点，然后免费获得另外三个位置。考虑到这一点，我们可以说轰炸边缘内侧的环1至少和轰炸边缘一样好。此外，我们可以将这一点与直觉结合起来，即轰炸边缘内部的右边缘实际上是将边缘空间降到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 2

波利亚说：“如果你不能解决一个问题，那么还有一个更容易解决的问题：找到它。”

明显更简单的问题是1维问题（当网格是单行时）。让我们从最简单的算法开始——贪婪地轰炸最大的目标。什么时候会出错？

给定1 1，贪婪算法不关心它先轰炸哪个细胞。当然，中心单元更好——它一次将所有三个单元归零。这建议了一个新的算法A，“炸弹以最小化剩余的总和”。这个算法什么时候出错？

给定1，算法A在轰炸第2、第3或第4个单元之间是不相关的。但是轰炸第二个小区离开0 0 1 1比轰炸第三个小区离开1 0 1 0 1要好。如何解决这个问题？轰炸第三个牢房的问题是，它让我们工作在左边，工作在右边，这必须分开进行。

“轰炸以最小化剩余金额，但最大化左侧（我们轰炸的地方）的最小值加上右侧的最小值”怎么样。调用此算法B。此算法何时出错？

编辑：在阅读了评论之后，我同意一个更有趣的问题是改变一维问题，使两端连接起来。我很想看到这方面的进展。

Answer 3

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

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

如果你想轰炸矩形（假设一个大矩形-没有边的情况下），你可以看到，唯一的办法是将周长上的空心矩形正方形减少到0，要么轰炸周长，要么轰炸周长内的空心矩形正方形。我将把周长层称为1，里面的矩形称为2。

一个重要的洞察是第1层没有点轰炸，因为这样做得到的“爆炸半径”总是包含在第2层另一个正方形的爆炸半径内。你应该能够很容易地让自己相信这一点。

所以，我们可以把问题简化为找到一个最佳的方法来炸开周界，然后我们可以重复这个过程，直到所有的方块都为0。

但当然，如果有可能以一种不太理想的方式轰炸周边地区，这并不总是能找到一个最佳解决方案，但是通过使用X个额外的炸弹，减少内层的问题就变得简单了

但是，我们知道我们可能很贪婪。因为第2层的炸弹在将第2层还原为0方面比第3层的炸弹更有效。出于和以前一样的原因——我们总是可以在第3层放置一枚炸弹，它会影响第2层的每一个方格，而放置在第2层的炸弹可以。所以，贪婪永远不会伤害我们（在贪婪的意义上）。

所以，我们所要做的就是找到最佳的方法，通过轰炸下一个内层，将介电常数降低到0。

我们从来不会因为先把角落炸到0而受到伤害，因为只有内层的角落才能到达它，所以我们真的别无选择（而且，周界上任何能到达角落的炸弹都有爆炸半径包含在爆炸半径中从内层的角落）。

一旦我们这样做了，0角附近周长上的正方形只能由内层的2个正方形到达：

0       A       B

C       X       Y

D       Z

在这一点上，周长实际上是一个封闭的一维循环，因为任何炸弹都会减少3个相邻的方块。除了角落附近的一些奇怪之处——X可以“击中”甲、乙、丙和丁。

现在我们不能使用任何爆炸半径技巧-每个正方形的情况都是对称的，除了奇怪的角，甚至没有爆炸半径也是另一个的子集。请注意，如果这是一条线（正如Panic上校所讨论的），而不是一个闭环，那么解决方案就很简单。endpoint必须减少为0，轰炸endpoint附近的点不会对您造成任何伤害，这也是因为爆炸半径是一个超集。将endpoint设置为0后，仍然有一个新endpoint，因此重复此操作（直到该行全部为0）。

因此，如果我们可以将层中的一个正方形优化为0，我们就有了一个算法（因为我们已经切割了循环，现在有了一条带endpoint的直线）。我相信在最小值的正方形附近进行轰炸（给你2个选项），这样在最小值的2个正方形内的最大值就是可能的最小值（你可能需要分割轰炸来管理这个）将是最佳的，但我（还没有？）有证据。