这里似乎有一个非二部匹配子结构。考虑下面的例子:

0010000
1000100
0000001
1000000
0000001
1000100
0010000

这种情况下的最佳解决方案的大小为5，因为这是9-cycle的边的最小顶点覆盖的大小。

这个例子，特别地，表明了一些人发布的线性规划松弛法是不精确的，不管用，还有其他一些不好的东西。我很确定我可以减少“用尽可能少的边覆盖我的平面立方图的顶点”来解决你的问题，这让我怀疑任何贪婪/爬坡的解决方案是否有效。

在最坏的情况下，我找不到在多项式时间内解出来的方法。可能有一个非常聪明的二进制搜索和dp解决方案，但我没有看到。

编辑:我看到这个比赛(http://deadline24.pl)是语言无关的;他们给你一堆输入文件，你给他们输出。所以你不需要在最坏情况下多项式时间内运行的东西。特别是，您可以查看输入!

There are a bunch of small cases in the input. Then there's a 10x1000 case, a 100x100 case, and a 1000x1000 case. The three large cases are all very well-behaved. Horizontally adjacent entries typically have the same value. On a relatively beefy machine, I'm able to solve all of the cases by brute-forcing using CPLEX in just a couple of minutes. I got lucky on the 1000x1000; the LP relaxation happens to have an integral optimal solution. My solutions agree with the .ans files provided in the test data bundle.

我敢打赌你可以用比我更直接的方式使用输入的结构，如果你看了它;看起来你只需要砍掉第一行，或者两行，或者三行直到你什么都不剩。(看起来，在1000x1000中，所有的行都是不增加的?我猜这就是你的“B部分”的来源吧?)

Well, suppose we number the board positions 1, 2, ..., n x m. Any sequence of bomb drops can be represented by a sequence of numbers in this set, where numbers can repeat. However, the effect on the board is the same regardless of what order you drop the bombs in, so really any choice of bomb drops can be represented as a list of n x m numbers, where the first number represents the number of bombs dropped on position 1, the second number represents the number of bombs dropped on position 2, etc. Let's call this list of n x m numbers the "key".

你可以试着先计算1个炸弹投下的所有板子状态，然后用这些来计算2个炸弹投下的所有板子状态，等等，直到你得到所有的0。但是在每一步中，您都将使用上面定义的键缓存状态，因此您可以在计算下一步时使用这些结果(一种“动态规划”方法)。

但是根据n、m的大小和网格中的数字，这种方法的内存需求可能会过多。一旦你计算了N + 1的所有结果，你就可以抛弃N个炸弹投掷的所有结果，所以这里有一些节省。当然，您不能以花费更长的时间为代价缓存任何东西——动态编程方法以内存换取速度。

使用分支和定界的数学整数线性规划

As it has already been mentioned, this problem can be solved using integer linear programming (which is NP-Hard). Mathematica already has ILP built in. "To solve an integer linear programming problem Mathematica first solves the equational constraints, reducing the problem to one containing inequality constraints only. Then it uses lattice reduction techniques to put the inequality system in a simpler form. Finally, it solves the simplified optimization problem using a branch-and-bound method." [see Constrained Optimization Tutorial in Mathematica.. ]

我写了下面的代码，利用ILP库的Mathematica。它的速度快得惊人。

solveMatrixBombProblem[problem_, r_, c_] := 
 Module[{}, 
  bombEffect[x_, y_, m_, n_] := 
   Table[If[(i == x || i == x - 1 || i == x + 1) && (j == y || 
        j == y - 1 || j == y + 1), 1, 0], {i, 1, m}, {j, 1, n}];
  bombMatrix[m_, n_] := 
   Transpose[
    Table[Table[
      Part[bombEffect[(i - Mod[i, n])/n + 1, Mod[i, n] + 1, m, 
        n], (j - Mod[j, n])/n + 1, Mod[j, n] + 1], {j, 0, 
       m*n - 1}], {i, 0, m*n - 1}]];
  X := x /@ Range[c*r];
  sol = Minimize[{Total[X], 
     And @@ Thread[bombMatrix[r, c].X >= problem] && 
      And @@ Thread[X >= 0] && Total[X] <= 10^100 && 
      Element[X, Integers]}, X];
  Print["Minimum required bombs = ", sol[[1]]];
  Print["A possible solution = ", 
   MatrixForm[
    Table[x[c*i + j + 1] /. sol[[2]], {i, 0, r - 1}, {j, 0, 
      c - 1}]]];]

对于问题中提供的示例:

solveMatrixBombProblem[{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}, 7, 5]

输出

对于那些用贪婪算法读这篇文章的人

在下面这个10x10的问题上试试你的代码:

5   20  7   1   9   8   19  16  11  3  
17  8   15  17  12  4   5   16  8   18  
4   19  12  11  9   7   4   15  14  6  
17  20  4   9   19  8   17  2   10  8  
3   9   10  13  8   9   12  12  6   18  
16  16  2   10  7   12  17  11  4   15  
11  1   15  1   5   11  3   12  8   3  
7   11  16  19  17  11  20  2   5   19  
5   18  2   17  7   14  19  11  1   6  
13  20  8   4   15  10  19  5   11  12

这里用逗号分隔:

5, 20, 7, 1, 9, 8, 19, 16, 11, 3, 17, 8, 15, 17, 12, 4, 5, 16, 8, 18, 4, 19, 12, 11, 9, 7, 4, 15, 14, 6, 17, 20, 4, 9, 19, 8, 17, 2, 10, 8, 3, 9, 10, 13, 8, 9, 12, 12, 6, 18, 16, 16, 2, 10, 7, 12, 17, 11, 4, 15, 11, 1, 15, 1, 5, 11, 3, 12, 8, 3, 7, 11, 16, 19, 17, 11, 20, 2, 5, 19, 5, 18, 2, 17, 7, 14, 19, 11, 1, 6, 13, 20, 8, 4, 15, 10, 19, 5, 11, 12

对于这个问题，我的解决方案包含208个炸弹。这里有一个可能的解决方案(我能够在大约12秒内解决这个问题)。

作为一种测试Mathematica产生结果的方法，看看你的贪婪算法是否能做得更好。

这是另一个想法:

让我们先给黑板上的每个空格分配一个权重，计算在那里扔炸弹会减少多少数字。如果这个空间有一个非零数，它就得到一个点，如果它的相邻空间有一个非零数，它就得到一个额外的点。如果这是一个1000 * 1000的网格，我们为这100万个空间中的每一个都分配了权重。

然后根据权重对列表中的空格进行排序，并轰炸权重最高的空格。可以这么说，这是我们最大的收获。

在此之后，更新每个空间的重量是受炸弹的影响。这是你轰炸的空间，和它相邻的空间，以及它们相邻的空间。换句话说，任何空间的价值都可能因为爆炸而减少为零，或者相邻空间的价值减少为零。

然后，根据权重重新排序列表空间。由于轰炸只改变了一小部分空间的权重，因此不需要使用整个列表，只需在列表中移动这些空间。

轰炸新的最高权重空间，并重复上述步骤。

这保证了每次轰炸都能减少尽可能多的空格(基本上，它会击中尽可能少的已经为零的空格)，所以这是最优的，除非它们的权重是相同的。所以你可能需要做一些回溯跟踪，当有一个平局的顶部重量。不过，只有最高重量的领带重要，其他领带不重要，所以希望没有太多的回溯。

Edit: Mysticial's counterexample below demonstrates that in fact this isn't guaranteed to be optimal, regardless of ties in weights. In some cases reducing the weight as much as possible in a given step actually leaves the remaining bombs too spread out to achieve as high a cummulative reduction after the second step as you could have with a slightly less greedy choice in the first step. I was somewhat mislead by the notion that the results are insensitive to the order of bombings. They are insensitive to the order in that you could take any series of bombings and replay them from the start in a different order and end up with the same resulting board. But it doesn't follow from that that you can consider each bombing independently. Or, at least, each bombing must be considered in a way that takes into account how well it sets up the board for subsequent bombings.

这是部分答案，我试图找到一个下界和上界，可能是炸弹的数量。

在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个炸弹确实是一个最优解。

当贪心和我上面提到的寻找最小界的方法不收敛时，我猜你必须回去检查所有的组合。

求下界的算法如下:

选一个数值最大的元素，命名为P。 将所有距离P和P本身两步远的单元格标记为不可拾取。 将P添加到最小值列表中。 重复步骤1，直到所有单元格都不可拾取。 对最小值列表求和得到下界。

你的新问题，有跨行不递减的值，很容易解决。

Observe that the left column contains the highest numbers. Therefore, any optimal solution must first reduce this column to zero. Thus, we can perform a 1-D bombing run over this column, reducing every element in it to zero. We let the bombs fall on the second column so they do maximum damage. There are many posts here dealing with the 1D case, I think, so I feel safe in skipping that case. (If you want me to describe it, I can.). Because of the decreasing property, the three leftmost columns will all be reduced to zero. But, we will provably use a minimum number of bombs here because the left column must be zeroed.

现在，一旦左边的列归零，我们只要剪掉最左边的三列现在归零，然后对现在化简的矩阵重复这一步骤。这必须给我们一个最优的解决方案，因为在每个阶段我们使用可证明的最少数量的炸弹。