我有一个nxm个由非负整数组成的矩阵。例如:
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:我相信当我们有几个相同的情况需要最少的炸弹来清除上面的线时，我们会选择在“左侧”使用最多炸弹的一个。还有什么证据是正确的吗?
当前回答
评价函数，总和:
int f (int ** matrix, int width, int height, int x, int y)
{
int m[3][3] = { 0 };
m[1][1] = matrix[x][y];
if (x > 0) m[0][1] = matrix[x-1][y];
if (x < width-1) m[2][1] = matrix[x+1][y];
if (y > 0)
{
m[1][0] = matrix[x][y-1];
if (x > 0) m[0][0] = matrix[x-1][y-1];
if (x < width-1) m[2][0] = matrix[x+1][y-1];
}
if (y < height-1)
{
m[1][2] = matrix[x][y+1];
if (x > 0) m[0][2] = matrix[x-1][y+1];
if (x < width-1) m[2][2] = matrix[x+1][y+1];
}
return m[0][0]+m[0][1]+m[0][2]+m[1][0]+m[1][1]+m[1][2]+m[2][0]+m[2][1]+m[2][2];
}
目标函数:
Point bestState (int ** matrix, int width, int height)
{
Point p = new Point(0,0);
int bestScore = 0;
int b = 0;
for (int i=0; i<width; i++)
for (int j=0; j<height; j++)
{
b = f(matrix,width,height,i,j);
if (b > bestScore)
{
bestScore = best;
p = new Point(i,j);
}
}
retunr p;
}
破坏功能:
void destroy (int ** matrix, int width, int height, Point p)
{
int x = p.x;
int y = p.y;
if(matrix[x][y] > 0) matrix[x][y]--;
if (x > 0) if(matrix[x-1][y] > 0) matrix[x-1][y]--;
if (x < width-1) if(matrix[x+1][y] > 0) matrix[x+1][y]--;
if (y > 0)
{
if(matrix[x][y-1] > 0) matrix[x][y-1]--;
if (x > 0) if(matrix[x-1][y-1] > 0) matrix[x-1][y-1]--;
if (x < width-1) if(matrix[x+1][y-1] > 0) matrix[x+1][y-1]--;
}
if (y < height-1)
{
if(matrix[x][y] > 0) matrix[x][y+1]--;
if (x > 0) if(matrix[x-1][y+1] > 0) matrix[x-1][y+1]--;
if (x < width-1) if(matrix[x+1][y+1] > 0) matrix[x+1][y+1]--;
}
}
目标函数:
bool isGoal (int ** matrix, int width, int height)
{
for (int i=0; i<width; i++)
for (int j=0; j<height; j++)
if (matrix[i][j] > 0)
return false;
return true;
}
线性最大化函数:
void solve (int ** matrix, int width, int height)
{
while (!isGoal(matrix,width,height))
{
destroy(matrix,width,height, bestState(matrix,width,height));
}
}
这不是最优的，但可以通过找到更好的评价函数来优化。
. .但是考虑到这个问题，我在想一个主要的问题是在0中间的某个点上得到废弃的数字，所以我要采取另一种方法。这是支配最小值为零，然后试图转义零，这导致一般的最小现有值(s)或这样
其他回答
这是部分答案，我试图找到一个下界和上界，可能是炸弹的数量。
在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，直到所有单元格都不可拾取。 对最小值列表求和得到下界。
评价函数，总和:
int f (int ** matrix, int width, int height, int x, int y)
{
int m[3][3] = { 0 };
m[1][1] = matrix[x][y];
if (x > 0) m[0][1] = matrix[x-1][y];
if (x < width-1) m[2][1] = matrix[x+1][y];
if (y > 0)
{
m[1][0] = matrix[x][y-1];
if (x > 0) m[0][0] = matrix[x-1][y-1];
if (x < width-1) m[2][0] = matrix[x+1][y-1];
}
if (y < height-1)
{
m[1][2] = matrix[x][y+1];
if (x > 0) m[0][2] = matrix[x-1][y+1];
if (x < width-1) m[2][2] = matrix[x+1][y+1];
}
return m[0][0]+m[0][1]+m[0][2]+m[1][0]+m[1][1]+m[1][2]+m[2][0]+m[2][1]+m[2][2];
}
目标函数:
Point bestState (int ** matrix, int width, int height)
{
Point p = new Point(0,0);
int bestScore = 0;
int b = 0;
for (int i=0; i<width; i++)
for (int j=0; j<height; j++)
{
b = f(matrix,width,height,i,j);
if (b > bestScore)
{
bestScore = best;
p = new Point(i,j);
}
}
retunr p;
}
破坏功能:
void destroy (int ** matrix, int width, int height, Point p)
{
int x = p.x;
int y = p.y;
if(matrix[x][y] > 0) matrix[x][y]--;
if (x > 0) if(matrix[x-1][y] > 0) matrix[x-1][y]--;
if (x < width-1) if(matrix[x+1][y] > 0) matrix[x+1][y]--;
if (y > 0)
{
if(matrix[x][y-1] > 0) matrix[x][y-1]--;
if (x > 0) if(matrix[x-1][y-1] > 0) matrix[x-1][y-1]--;
if (x < width-1) if(matrix[x+1][y-1] > 0) matrix[x+1][y-1]--;
}
if (y < height-1)
{
if(matrix[x][y] > 0) matrix[x][y+1]--;
if (x > 0) if(matrix[x-1][y+1] > 0) matrix[x-1][y+1]--;
if (x < width-1) if(matrix[x+1][y+1] > 0) matrix[x+1][y+1]--;
}
}
目标函数:
bool isGoal (int ** matrix, int width, int height)
{
for (int i=0; i<width; i++)
for (int j=0; j<height; j++)
if (matrix[i][j] > 0)
return false;
return true;
}
线性最大化函数:
void solve (int ** matrix, int width, int height)
{
while (!isGoal(matrix,width,height))
{
destroy(matrix,width,height, bestState(matrix,width,height));
}
}
这不是最优的，但可以通过找到更好的评价函数来优化。
. .但是考虑到这个问题，我在想一个主要的问题是在0中间的某个点上得到废弃的数字，所以我要采取另一种方法。这是支配最小值为零，然后试图转义零，这导致一般的最小现有值(s)或这样
由于时间不够，我不得不停留在部分解决方案上，但希望即使是这个部分解决方案也能提供解决这个问题的潜在方法的一些见解。
当面对一个困难的问题时，我喜欢想出一些简单的问题来培养对问题空间的直觉。这里，我采取的第一步是将这个二维问题简化为一维问题。考虑一行字:
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
从一个需要以某种方式下降的数字开始是一个很有吸引力的想法，因为它突然变得可以找到一个解，就像一些人声称的那样，至少和所有其他解一样好。
The next step up in complexity where this search of at least as good is still feasible is on the edge of the board. It is clear to me that there is never any strict benefit to bomb the outer edge; you're better off bombing the spot one in and getting three other spaces for free. Given this, we can say that bombing the ring one inside of the edge is at least as good as bombing the edge. Moreover, we can combine this with the intuition that bombing the right one inside of the edge is actually the only way to get edge spaces down to 0. Even more, it is trivially simple to figure out the optimal strategy (in that it is at least as good as any other strategy) to get corner numbers down to 0. We put this all together and can get much closer to a solution in the 2-D space.
根据对角子的观察，我们可以肯定地说，我们知道从任何起始棋盘到所有角子都是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
The flaw in this approach becomes very obvious in the final two bombings. It is clear, given that the only bomb sites that reduce the 4 figure in the first column in the second row are the first x and the y. The final two bombings are clearly inferior to just bombing the first x, which would have done the exact same (with regard to the first spot in the top row, which we have no other way of clearing). Since we have demonstrated that our current strategy is suboptimal, a modification in strategy is clearly needed.
在这一点上，我可以退一步，只关注一个角落。让我们考虑一下这个问题:
0 4 2 1
4 x y a
2 z . .
1 b . .
It is clear the only way to get the spaces with 4 down to zero are to bomb some combination of x, y, and z. With some acrobatics in my mind, I'm fairly sure the optimal solution is to bomb x three times and then a then b. Now it's a matter of figuring out how I reached that solution and if it reveals any intuition we can use to even solve this local problem. I notice that there's no bombing of y and z spaces. Attempting to find a corner where bombing those spaces makes sense yields a corner that looks like this:
0 4 2 5 0
4 x y a .
2 z . . .
5 b . . .
0 . . . .
对于这个问题，我很清楚，最优解决方案是轰炸y 5次，z 5次。让我们更进一步。
0 4 2 5 6 0 0
4 x y a . . .
2 z . . . . .
5 b . . . . .
6 . . . . . .
0 . . . . . .
0 . . . . . .
这里，最优解决方案是轰炸a和b 6次，然后x 4次。
现在它变成了一个如何将这些直觉转化为我们可以建立的原则的游戏。
希望能继续!
你可以使用状态空间规划。 例如，使用A*(或其变体之一)加上启发式f = g + h，如下所示:
G:到目前为止投下的炸弹数量 H:网格中所有值的总和除以9(这是最好的结果，意味着我们有一个可接受的启发式)
为了尽量减少炸弹的数量，我们必须最大化每个炸弹的效果。要做到这一点，每一步我们都要选择最好的目标。对于每一个点，它和它的八个邻居的总和，可以被用作轰炸这一点的效率量。这将提供接近最佳的炸弹序列。
UPD:我们还应该考虑到零的数量，因为轰炸它们效率很低。事实上，问题是最小化击中零的数量。但我们不知道每一步如何使我们更接近这个目标。我同意这个问题是np完全的。我建议用贪婪的方法，它会给出一个接近真实的答案。
