投弹算法

我有一个nxm个由非负整数组成的矩阵。例如:

“投下炸弹”会使目标细胞及其所有八个邻居的数量减少一个，直到最小值为零。

x x x 
x X x
x x x

什么样的算法可以确定将所有细胞减少到零所需的最少炸弹数量?

B选项(因为我不是一个细心的读者)

事实上，问题的第一个版本并不是我要寻找的答案。我没有仔细阅读整个任务，有额外的约束条件，让我们说:

那么简单的问题是，当行中的序列必须是非递增的:

8 7 6 6 5是可能的输入序列

7 8 5 5 2是不可能的，因为7 -> 8在一个序列中增长。

也许为“简单”的问题找到答案会有助于为更难的问题找到解决方案。

PS:我相信当我们有几个相同的情况需要最少的炸弹来清除上面的线时，我们会选择在“左侧”使用最多炸弹的一个。还有什么证据是正确的吗?

当前回答

这里有一个解决方案，推广良好的性质的角。

让我们假设我们可以为给定的字段找到一个完美的落点，也就是说，一个减少其中值的最佳方法。然后，为了找到最少的炸弹数量，一个算法的初稿可能是(代码是从ruby实现中复制粘贴的):

dropped_bomb_count = 0
while there_are_cells_with_non_zero_count_left
  coordinates = choose_a_perfect_drop_point
  drop_bomb(coordinates)
  dropped_bomb_count += 1
end
return dropped_bomb_count

挑战是choose_a_perfect_drop_point。首先，让我们定义一个完美的落点是什么。

(x, y)的放置点会减少(x, y)中的值。它也可能会减少其他单元格中的值。 (x, y)的放置点A比(x, y)的放置点b更好，如果它减少了b所减少的单元格的适当超集中的值。如果没有其他更好的投放点，投放点是最大的。 (x, y)的两个放置点是等效的，如果它们减少了同一组单元格。如果(x, y)的放置点等价于(x, y)的所有最大放置点，那么它就是完美的。

如果(x, y)存在一个完美的投放点，那么您不能比在(x, y)的一个完美投放点上投放炸弹更有效地降低(x, y)处的值。

给定字段的完美放置点是其任何单元格的完美放置点。

以下是一些例子:

单元格(0,0)(从零开始的索引)的完美放置点是(1,1)。(1,1)的所有其他放置点，即(0,0)、(0,1)和(1,0)，减少的单元格较少。

单元格(2,2)(从零开始的索引)的完美落点是(2,2)，以及所有周围的单元格(1,1)、(1,2)、(1,3)、(2,1)、(2,3)、(3,1)、(3,2)和(3,3)。

单元格(2,2)的完美放置点是(3,1):它减少了(2,2)中的值和(4,0)中的值。(2,2)的所有其他放置点都不是最大的，因为它们减少了一个单元格。(2,2)的完美下拉点也是(4,0)的完美下拉点，它是字段的唯一完美下拉点。它为这个领域带来了完美的解决方案(一颗炸弹)。

(2,2)没有完美的落点:(1,1)和(1,3)都减少(2,2)和另一个单元格(它们是(2,2)的最大落点)，但它们不相等。然而，(1,1)是(0,0)的完美落点，(1,3)是(0,4)的完美落点。

根据完美落点的定义和一定的检查顺序，我得到了以下问题示例的结果:

Drop bomb on 1, 1
Drop bomb on 1, 1
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 6
Drop bomb on 1, 2
Drop bomb on 1, 2
Drop bomb on 0, 6
Drop bomb on 0, 6
Drop bomb on 2, 1
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 3, 1
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 4
Drop bomb on 3, 4
Drop bomb on 3, 3
Drop bomb on 3, 3
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 4, 6
28

然而，该算法只有在每一步之后至少有一个完美落点时才能工作。可以在没有完美落点的情况下构建例子:

对于这些情况，我们可以修改算法，这样我们就不会选择完美的落点，而是选择一个具有最大落点的最小选择的坐标，然后计算每个选择的最小值。在上面的例子中，所有有值的单元格都有两个最大落点。例如，(0,1)有最大落点(1,1)和(1,2)。选择其中任何一个，然后计算最小值，会得到这样的结果:

Drop bomb on 1, 1
Drop bomb on 2, 2
Drop bomb on 1, 2
Drop bomb on 2, 1
2

2013-03-10 22:47:02

其他回答

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个炸弹投掷的所有结果，所以这里有一些节省。当然，您不能以花费更长的时间为代价缓存任何东西——动态编程方法以内存换取速度。

2013-03-08 18:05:01

永远不要轰炸边界(除非正方形没有边界以外的邻居) 零角落。到零角，将对角线上一个正方形的角的值降低(唯一的非边界邻居) 这会产生新的角落。见第2节

编辑:没有注意到Kostek提出了几乎相同的方法，所以现在我提出了更强烈的主张: 如果要清除的角总是选择在最外层，那么它是最优的。

在OP的例子中:在除5之外的任何地方掉落2(1+1或2)并不会导致掉落5所能击中的任何方块。所以我们必须在5上加上2(在左下角加上6…)

在这之后，只有一种方法可以清除(在左上角)角落里原本是1(现在是0)的东西，那就是在B3上删除0(类似excel的符号)。等等。

只有在清除了整个A和E列以及1和7行之后，才开始更深一层的清理。

考虑只清除那些故意清除的角落，清除0值的角落不需要花费任何成本，并且简化了思考。

因为所有以这种方式投掷的炸弹都必须被投掷，并且这将导致清除战场，这是最佳解决方案。

睡了一觉后，我意识到这不是真的。考虑

我的方法是在B3和C2上投放炸弹，而在B2上投放炸弹就足够了

2013-03-08 18:17:07

生成最慢但最简单且无错误的算法，并测试所有有效的可能性。这种情况非常简单(因为结果与炸弹放置的顺序无关)。

创建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[][]递减代码

2013-09-06 09:49:17

所有这些问题都归结为计算编辑距离。简单地计算给定矩阵和零矩阵之间的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

2013-03-09 23:38:24

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

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产生结果的方法，看看你的贪婪算法是否能做得更好。

2013-03-16 07:42:04

推荐文章

最新文章

标签