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


当前回答

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

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部分”的来源吧?)

其他回答

你可以把这个问题表示成整数规划问题。(这只是解决这个问题的一种可能的方法)

有分:

a b c d
e f g h
i j k l
m n o p

我们可以写出16个方程其中以点f为例

f <= ai + bi + ci + ei + fi + gi + ii + ji + ki   

最小化所有索引的总和和整数解。

解当然是这些指标的和。

这可以通过将所有xi设置为边界0来进一步简化,因此在本例中最终得到4+1方程。

问题是没有解决这类问题的简单算法。我不是这方面的专家,但解决这个问题作为线性规划是NP困难。

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

创建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上投放炸弹就足够了

这将是一个贪婪的方法:

计算一个阶为n X m的“score”矩阵,其中score[i][j]是如果位置(i,j)被炸毁,则矩阵中各点的总扣除额。(一个点的最高分数是9分,最低分数是0分) 逐行移动,找到并选择第一个得分最高的位置(例如(i,j))。 炸弹(i, j)。增加炸弹数量。 如果原矩阵的所有元素都不为零,则转到1。

但我怀疑这是否是最佳解决方案。

编辑:

我上面提到的贪心方法,虽然有效,但很可能不能给我们最优的解决方案。所以我想应该添加一些DP的元素。

我想我们可以同意,在任何时候,具有最高“分数”(分数[I][j] =总扣分,如果(I,j)被炸)的位置之一必须被瞄准。从这个假设开始,下面是新的方法:

NumOfBombs(M):(返回所需的最小炸弹数量)

给定一个矩阵M (n X M),如果M中的所有元素都为0,则返回0。 计算“分数”矩阵M。 设k个不同的位置P1 P2…Pk (1 <= k <= n*m),为m中得分最高的位置。 return (1 + min(NumOfBombs(M1), NumOfBombs(M2),…, NumOfBombs(Mk)) M1, M2,……,Mk是我们轰炸位置P1, P2,…, Pk。

此外,如果我们想在此基础上破坏位置的顺序,我们必须跟踪“min”的结果。