我有一个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:我相信当我们有几个相同的情况需要最少的炸弹来清除上面的线时，我们会选择在“左侧”使用最多炸弹的一个。还有什么证据是正确的吗?
当前回答
没有必要将问题转化为线性子问题。
相反，使用简单的贪婪启发式，即从最大的角落开始轰炸角落。
在给定的例子中，有四个角，{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。
其他回答
我也有28招。我使用了两个测试来确定最佳下一步:第一个是产生最小棋盘和的一步。其次，对于相等的和，产生最大密度的移动，定义为:
number-of-zeros / number-of-groups-of-zeros
我是哈斯克尔。“解决板”显示引擎的解决方案。你可以通过输入“main”来玩游戏，然后输入目标点，“best”作为推荐，或者“quit”退出。
输出: *主>解决板 [(4, 4),(3、6),(3),(2,2),(2,2),(4、6)(4、6),(2,6),(2),(4,2)(2,6),(3),(4,3)(2,6)(4,2)(4、6)(4、6),(3、6),(2,6)(2,6)(2、4)(2、4)(2,6),(6),(4,2)(4,2)(4,2)(4,2)]
import Data.List
import Data.List.Split
import Data.Ord
import Data.Function(on)
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]
n = 5
m = 7
updateBoard board pt =
let x = fst pt
y = snd pt
precedingLines = replicate ((y-2) * n) 0
bomb = concat $ replicate (if y == 1
then 2
else min 3 (m+2-y)) (replicate (x-2) 0
++ (if x == 1
then [1,1]
else replicate (min 3 (n+2-x)) 1)
++ replicate (n-(x+1)) 0)
in zipWith (\a b -> max 0 (a-b)) board (precedingLines ++ bomb ++ repeat 0)
showBoard board =
let top = " " ++ (concat $ map (\x -> show x ++ ".") [1..n]) ++ "\n"
chunks = chunksOf n board
in putStrLn (top ++ showBoard' chunks "" 1)
where showBoard' [] str count = str
showBoard' (x:xs) str count =
showBoard' xs (str ++ show count ++ "." ++ show x ++ "\n") (count+1)
instances _ [] = 0
instances x (y:ys)
| x == y = 1 + instances x ys
| otherwise = instances x ys
density a =
let numZeros = instances 0 a
groupsOfZeros = filter (\x -> head x == 0) (group a)
in if null groupsOfZeros then 0 else numZeros / fromIntegral (length groupsOfZeros)
boardDensity board = sum (map density (chunksOf n board))
moves = [(a,b) | a <- [2..n-1], b <- [2..m-1]]
bestMove board =
let lowestSumMoves = take 1 $ groupBy ((==) `on` snd)
$ sortBy (comparing snd) (map (\x -> (x, sum $ updateBoard board x)) (moves))
in if null lowestSumMoves
then (0,0)
else let lowestSumMoves' = map (\x -> fst x) (head lowestSumMoves)
in fst $ head $ reverse $ sortBy (comparing snd)
(map (\x -> (x, boardDensity $ updateBoard board x)) (lowestSumMoves'))
solve board = solve' board [] where
solve' board result
| sum board == 0 = result
| otherwise =
let best = bestMove board
in solve' (updateBoard board best) (result ++ [best])
main :: IO ()
main = mainLoop board where
mainLoop board = do
putStrLn ""
showBoard board
putStr "Pt: "
a <- getLine
case a of
"quit" -> do putStrLn ""
return ()
"best" -> do putStrLn (show $ bestMove board)
mainLoop board
otherwise -> let ws = splitOn "," a
pt = (read (head ws), read (last ws))
in do mainLoop (updateBoard board pt)
评价函数，总和:
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)或这样
Pólya说:“如果你不能解决一个问题，那么有一个更容易解决的问题:找到它。”
显然更简单的问题是一维问题(当网格是单行时)。让我们从最简单的算法开始——贪婪地轰炸最大的目标。什么时候会出问题?
给定11 11，贪婪算法对先炸毁哪个单元格无关。当然，中心单元格更好——它一次将所有三个单元格归零。这就提出了一种新的算法a，“炸弹最小化剩余的总和”。这个算法什么时候会出错?
给定1 1 2 11 1，算法A在轰炸第2，第3或第4单元格之间是无所谓的。但是轰炸第二个单元格，留下0 0 11 11比轰炸第三个单元格，留下10 10 10 10 1好。如何解决这个问题?轰炸第三个单元格的问题是，左边的功和右边的功必须分开做。
“炸弹使剩余的总和最小化，但使左边(我们轰炸的地方)的最小值和右边的最小值最大化”如何?叫这个算法b，这个算法什么时候出错?
编辑:在阅读了评论之后，我同意一个更有趣的问题将是改变一维问题，使其两端连接起来。很乐意看到这方面的进展。
到目前为止，一些答案给出了指数时间，一些涉及动态规划。我怀疑这些是否有必要。
我的解是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();
}
}
所有这些问题都归结为计算编辑距离。简单地计算给定矩阵和零矩阵之间的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
