我有一个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部分”的来源吧?)
其他回答
生成最慢但最简单且无错误的算法，并测试所有有效的可能性。这种情况非常简单(因为结果与炸弹放置的顺序无关)。
创建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[][]递减代码
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个炸弹投掷的所有结果，所以这里有一些节省。当然，您不能以花费更长的时间为代价缓存任何东西——动态编程方法以内存换取速度。
这将是一个贪婪的方法:
计算一个阶为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”的结果。
你可以使用状态空间规划。 例如，使用A*(或其变体之一)加上启发式f = g + h，如下所示:
G:到目前为止投下的炸弹数量 H:网格中所有值的总和除以9(这是最好的结果，意味着我们有一个可接受的启发式)
评价函数，总和:
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)或这样
