我有一个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:我相信当我们有几个相同的情况需要最少的炸弹来清除上面的线时，我们会选择在“左侧”使用最多炸弹的一个。还有什么证据是正确的吗?
当前回答
所有这些问题都归结为计算编辑距离。简单地计算给定矩阵和零矩阵之间的Levenshtein距离的变体，其中编辑被轰炸替换，使用动态编程来存储中间数组之间的距离。我建议使用矩阵的哈希作为键。在pseudo-Python:
memo = {}
def bomb(matrix,i,j):
# bomb matrix at i,j
def bombsRequired(matrix,i,j):
# bombs required to zero matrix[i,j]
def distance(m1, i, len1, m2, j, len2):
key = hash(m1)
if memo[key] != None:
return memo[key]
if len1 == 0: return len2
if len2 == 0: return len1
cost = 0
if m1 != m2: cost = m1[i,j]
m = bomb(m1,i,j)
dist = distance(str1,i+1,len1-1,str2,j+1,len2-1)+cost)
memo[key] = dist
return dist
其他回答
如果你想要绝对最优解来清理棋盘，你将不得不使用经典的回溯，但如果矩阵非常大，它将需要很长时间才能找到最佳解，如果你想要一个“可能的”最优解，你可以使用贪婪算法，如果你需要帮助写算法，我可以帮助你
现在想想，这是最好的办法。在那里制作另一个矩阵，存储通过投掷炸弹而移除的点，然后选择点数最多的单元格，并在那里投掷炸弹更新点数矩阵，然后继续。例子:
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
生成最慢但最简单且无错误的算法，并测试所有有效的可能性。这种情况非常简单(因为结果与炸弹放置的顺序无关)。
创建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[][]递减代码
蛮力!
我知道它效率不高，但即使你找到了一个更快的算法，你也可以对这个结果进行测试，以了解它有多准确。
使用一些递归，像这样:
void fn(tableState ts, currentlevel cl)
{
// first check if ts is all zeros yet, if not:
//
// do a for loop to go through all cells of ts,
// for each cell do a bomb, and then
// call:
// fn(ts, cl + 1);
}
你可以通过缓存来提高效率，如果不同的方法导致相同的结果，你不应该重复相同的步骤。
阐述:
如果轰炸单元格1,3,5的结果与轰炸单元格5,3,1的结果相同，那么，对于这两种情况，您不应该重新执行所有后续步骤，只需1就足够了，您应该将所有表状态存储在某个地方并使用其结果。
表统计信息的散列可以用于快速比较。
使用分支和定界的数学整数线性规划
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产生结果的方法，看看你的贪婪算法是否能做得更好。
对于更新后的问题，简单的贪心算法可以得到最优结果。
向单元格A[1,1]投掷A[0,0]炸弹，然后向单元格A[2,1]投掷A[1,0]炸弹，并继续向下此过程。要清除左下角，向单元格A[n -2,1]投掷max(A[n -1,0]， A[n -2,0]， A[n -3,0])炸弹。这将完全清除前3列。
用同样的方法清除第3、4、5列，然后是第6、7、8列，等等。
不幸的是，这并不能帮助找到最初问题的解决方案。
“更大”的问题(没有“非增加”约束)可能被证明是np困难的。这是证明的草图。
假设我们有一个度为3的平面图形。我们来求这个图的最小顶点覆盖。根据维基百科的文章，这个问题对于3次以下的平面图形是np困难的。这可以通过平面3SAT的简化来证明。平面3SAT的硬度由3SAT降低而成。这两个证明都在Erik Demaine教授最近的“算法下界”讲座(第7和第9讲)中提出。
如果我们分割原始图的一些边(图中左边的图)，每条边都有偶数个额外的节点，结果图(图中右边的图)应该对原始顶点具有完全相同的最小顶点覆盖。这样的转换允许将图顶点对齐到网格上的任意位置。
如果我们将图顶点只放置在偶数行和列上(这样就不会有两条边与一个顶点形成锐角)，在有边的地方插入“1”，在其他网格位置插入“0”，我们可以使用原始问题的任何解决方案来找到最小顶点覆盖。
