我有一个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:我相信当我们有几个相同的情况需要最少的炸弹来清除上面的线时，我们会选择在“左侧”使用最多炸弹的一个。还有什么证据是正确的吗?
当前回答
在这里，线性规划方法似乎非常有用。
设Pm x n为包含位置值的矩阵:
现在定义一个炸弹矩阵B(x, y)m x n，其中1≤x≤m, 1≤y≤n如下所示
以这样一种方式
例如:
所以我们正在寻找一个矩阵Bm x n = [bij]
可以定义为炸弹矩阵的和: (qij将是我们在pij位置投放的炸弹数量) pij - bij≤0(为了更简洁，我们称之为P - B≤0)
而且，B应该使和最小。
我们也可以把B写成前面的丑矩阵:
由于P - B≤0(即P≤B)，我们得到了如下线性不等式系统:
qmn x1定义为
PMN x 1定义为
我们可以说我们有一个方程组是smnxmn这个矩阵要倒转来解方程组。我自己没有扩展它，但我相信在代码中应该很容易做到。
现在，我们有一个最小的问题可以表述为
I believe it is something easy, almost trivial to be solved with something like the simplex algorithm (there is this rather cool doc about it). However, I do know almost no linear programming (I will take a course about it on Coursera but it is just in the future...), I had some headaches trying to understand it and I have a huge freelance job to finish so I just give up here. It can be that I did something wrong at some point, or that it can't go any further, but I believe this path can eventually lead to the solution. Anyway, I am anxious for your feedback.
(特别感谢这个神奇的网站从LaTeX表达式创建图片)
其他回答
生成最慢但最简单且无错误的算法，并测试所有有效的可能性。这种情况非常简单(因为结果与炸弹放置的顺序无关)。
创建N次应用bomp的函数 为所有炸弹放置/炸弹计数可能性创建循环(当矩阵==0时停止) 记住最好的解决方案。 在循环的最后，你得到了最好的解决方案 不仅是炸弹的数量，还有它们的位置
代码可以是这样的:
void copy(int **A,int **B,int m,int n)
{
for (int i=0;i<m;i++)
for (int j=0;i<n;j++)
A[i][j]=B[i][j];
}
bool is_zero(int **M,int m,int n)
{
for (int i=0;i<m;i++)
for (int j=0;i<n;j++)
if (M[i][j]) return 0;
return 1;
}
void drop_bomb(int **M,int m,int n,int i,int j,int N)
{
int ii,jj;
ii=i-1; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i-1; jj=j ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i-1; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i ; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i ; jj=j ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i ; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i+1; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i+1; jj=j ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i+1; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
}
void solve_problem(int **M,int m,int n)
{
int i,j,k,max=0;
// you probably will need to allocate matrices P,TP,TM yourself instead of this:
int P[m][n],min; // solution: placement,min bomb count
int TM[m][n],TP[m][n],cnt; // temp
for (i=0;i<m;i++) // max count of bomb necessary to test
for (j=0;j<n;j++)
if (max<M[i][j]) max=M[i][j];
for (i=0;i<m;i++) // reset solution
for (j=0;j<n;j++)
P[i][j]=max;
min=m*n*max;
copy(TP,P,m,n); cnt=min;
for (;;) // generate all possibilities
{
copy(TM,M,m,n);
for (i=0;i<m;i++) // test solution
for (j=0;j<n;j++)
drop_bomb(TM,m,n,TP[i][j]);
if (is_zero(TM,m,n))// is solution
if (min>cnt) // is better solution -> store it
{
copy(P,TP,m,n);
min=cnt;
}
// go to next possibility
for (i=0,j=0;;)
{
TP[i][j]--;
if (TP[i][j]>=0) break;
TP[i][j]=max;
i++; if (i<m) break;
i=0; j++; if (j<n) break;
break;
}
if (is_zero(TP,m,n)) break;
}
//result is in P,min
}
这可以通过很多方式进行优化，……最简单的是用M矩阵重置解，但你需要改变最大值和TP[][]递减代码
Pólya说:“如果你不能解决一个问题，那么有一个更容易解决的问题:找到它。”
显然更简单的问题是一维问题(当网格是单行时)。让我们从最简单的算法开始——贪婪地轰炸最大的目标。什么时候会出问题?
给定11 11，贪婪算法对先炸毁哪个单元格无关。当然，中心单元格更好——它一次将所有三个单元格归零。这就提出了一种新的算法a，“炸弹最小化剩余的总和”。这个算法什么时候会出错?
给定1 1 2 11 1，算法A在轰炸第2，第3或第4单元格之间是无所谓的。但是轰炸第二个单元格，留下0 0 11 11比轰炸第三个单元格，留下10 10 10 10 1好。如何解决这个问题?轰炸第三个单元格的问题是，左边的功和右边的功必须分开做。
“炸弹使剩余的总和最小化，但使左边(我们轰炸的地方)的最小值和右边的最小值最大化”如何?叫这个算法b，这个算法什么时候出错?
编辑:在阅读了评论之后，我同意一个更有趣的问题将是改变一维问题，使其两端连接起来。很乐意看到这方面的进展。
永远不要轰炸边界(除非正方形没有边界以外的邻居) 零角落。 到零角，将对角线上一个正方形的角的值降低(唯一的非边界邻居) 这会产生新的角落。见第2节
编辑:没有注意到Kostek提出了几乎相同的方法，所以现在我提出了更强烈的主张: 如果要清除的角总是选择在最外层，那么它是最优的。
在OP的例子中:在除5之外的任何地方掉落2(1+1或2)并不会导致掉落5所能击中的任何方块。所以我们必须在5上加上2(在左下角加上6…)
在这之后，只有一种方法可以清除(在左上角)角落里原本是1(现在是0)的东西，那就是在B3上删除0(类似excel的符号)。 等等。
只有在清除了整个A和E列以及1和7行之后，才开始更深一层的清理。
考虑只清除那些故意清除的角落，清除0值的角落不需要花费任何成本，并且简化了思考。
因为所有以这种方式投掷的炸弹都必须被投掷，并且这将导致清除战场，这是最佳解决方案。
睡了一觉后，我意识到这不是真的。 考虑
ABCDE
1 01000
2 10000
3 00000
4 00000
我的方法是在B3和C2上投放炸弹，而在B2上投放炸弹就足够了
我相信为了减少炸弹的数量，你只需要最大化伤害。 要做到这一点，需要检查具有最强力的区域。因此，您首先分析具有3x3核的场，并检查哪里的和更强。还有炸弹…一直这样做，直到场地变平。这个文件的答案是28
var oMatrix = [
[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]
]
var nBombs = 0;
do
{
var bSpacesLeftToBomb = false;
var nHigh = 0;
var nCellX = 0;
var nCellY = 0;
for(var y = 1 ; y<oMatrix.length-1;y++)
for(var x = 1 ; x<oMatrix[y].length-1;x++)
{
var nValue = 0;
for(var yy = y-1;yy<=y+1;yy++)
for(var xx = x-1;xx<=x+1;xx++)
nValue += oMatrix[yy][xx];
if(nValue>nHigh)
{
nHigh = nValue;
nCellX = x;
nCellY = y;
}
}
if(nHigh>0)
{
nBombs++;
for(var yy = nCellY-1;yy<=nCellY+1;yy++)
{
for(var xx = nCellX-1;xx<=nCellX+1;xx++)
{
if(oMatrix[yy][xx]<=0)
continue;
oMatrix[yy][xx] = --oMatrix[yy][xx];
}
}
bSpacesLeftToBomb = true;
}
}
while(bSpacesLeftToBomb);
alert(nBombs+'bombs');
如果你想要绝对最优解来清理棋盘，你将不得不使用经典的回溯，但如果矩阵非常大，它将需要很长时间才能找到最佳解，如果你想要一个“可能的”最优解，你可以使用贪婪算法，如果你需要帮助写算法，我可以帮助你
现在想想，这是最好的办法。在那里制作另一个矩阵，存储通过投掷炸弹而移除的点，然后选择点数最多的单元格，并在那里投掷炸弹更新点数矩阵，然后继续。例子:
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
