我有一个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:我相信当我们有几个相同的情况需要最少的炸弹来清除上面的线时，我们会选择在“左侧”使用最多炸弹的一个。还有什么证据是正确的吗?
当前回答
你可以使用状态空间规划。 例如，使用A*(或其变体之一)加上启发式f = g + h，如下所示:
G:到目前为止投下的炸弹数量 H:网格中所有值的总和除以9(这是最好的结果，意味着我们有一个可接受的启发式)
其他回答
如果你想要绝对最优解来清理棋盘，你将不得不使用经典的回溯，但如果矩阵非常大，它将需要很长时间才能找到最佳解，如果你想要一个“可能的”最优解，你可以使用贪婪算法，如果你需要帮助写算法，我可以帮助你
现在想想，这是最好的办法。在那里制作另一个矩阵，存储通过投掷炸弹而移除的点，然后选择点数最多的单元格，并在那里投掷炸弹更新点数矩阵，然后继续。例子:
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
没有必要将问题转化为线性子问题。
相反，使用简单的贪婪启发式，即从最大的角落开始轰炸角落。
在给定的例子中，有四个角，{2,1,6,4}。对于每个角落，没有比轰炸单元格对角线更好的移动了，所以我们知道我们的第一个2+1+6+4 = 13次轰炸必须在这些对角线单元格中。在完成轰炸之后，我们会得到一个新的矩阵:
2 3 4 7 1 0 1 1 6 0 0 1 1 6 0 1 1 6 0 0 0 5 0 0 0
1 5 2 6 2 0 3 0 5 1 0 3 0 5 1 => 1 0 4 0 => 0 0 3 => 0 0 0
4 3 4 2 1 2 1 1 1 0 2 1 1 1 0 0 0 0 0 0 0 0 0 0 3
2 1 2 4 1 => 2 1 2 4 1 => 2 1 2 4 1 0 0 3 0 0 0 3
3 1 3 4 1 0 0 0 0 0 0 0 0 0 0
2 1 4 3 2 0 0 0 0 0 0 0 0 0 0
6 9 1 6 4 0 3 0 2 0 0 0 0 0 0
在前13次爆炸之后，我们使用启发式方法通过3次爆炸消除3 0 2。现在，我们有两个新的角，在第四行{2,1}。我们炸了那些，再炸3次。我们现在已经将矩阵化简为4 * 4。有一个角落，左上角。我们搞砸了。现在我们还有两个角，{5,3}。因为5是最大的角，我们首先轰炸5个角，然后最后轰炸另一个角的3。总数是13+3+3+1+5+3 = 28。
所有这些问题都归结为计算编辑距离。简单地计算给定矩阵和零矩阵之间的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
到目前为止，一些答案给出了指数时间，一些涉及动态规划。我怀疑这些是否有必要。
我的解是O(mnS)其中m和n是板子的维度，S是所有整数的和。这个想法相当野蛮:找到每次可以杀死最多的位置，并在0处终止。
对于给定的棋盘，它给出28步棋，并且在每次落子后打印出棋盘。
完整的，不言自明的代码:
import java.util.Arrays;
public class BombMinDrops {
private static final int[][] BOARD = {{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}};
private static final int ROWS = BOARD.length;
private static final int COLS = BOARD[0].length;
private static int remaining = 0;
private static int dropCount = 0;
static {
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
remaining = remaining + BOARD[i][j];
}
}
}
private static class Point {
int x, y;
int kills;
Point(int x, int y, int kills) {
this.x = x;
this.y = y;
this.kills = kills;
}
@Override
public String toString() {
return dropCount + "th drop at [" + x + ", " + y + "] , killed " + kills;
}
}
private static int countPossibleKills(int x, int y) {
int count = 0;
for (int row = x - 1; row <= x + 1; row++) {
for (int col = y - 1; col <= y + 1; col++) {
try {
if (BOARD[row][col] > 0) count++;
} catch (ArrayIndexOutOfBoundsException ex) {/*ignore*/}
}
}
return count;
}
private static void drop(Point here) {
for (int row = here.x - 1; row <= here.x + 1; row++) {
for (int col = here.y - 1; col <= here.y + 1; col++) {
try {
if (BOARD[row][col] > 0) BOARD[row][col]--;
} catch (ArrayIndexOutOfBoundsException ex) {/*ignore*/}
}
}
dropCount++;
remaining = remaining - here.kills;
print(here);
}
public static void solve() {
while (remaining > 0) {
Point dropWithMaxKills = new Point(-1, -1, -1);
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
int possibleKills = countPossibleKills(i, j);
if (possibleKills > dropWithMaxKills.kills) {
dropWithMaxKills = new Point(i, j, possibleKills);
}
}
}
drop(dropWithMaxKills);
}
System.out.println("Total dropped: " + dropCount);
}
private static void print(Point drop) {
System.out.println(drop.toString());
for (int[] row : BOARD) {
System.out.println(Arrays.toString(row));
}
System.out.println();
}
public static void main(String[] args) {
solve();
}
}
评价函数，总和:
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)或这样
