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

其他回答

这个贪婪的解决方案似乎是正确的:

正如评论中指出的那样,它在2D中会失败。但也许你可以改进它。

1 d: 如果至少有2个数字,你不需要从最左边的那个开始射击,因为从第二个开始射击并不差。所以射到第二个,而第一个不是0,因为你必须这么做。移动到下一个单元格。不要忘记最后一个单元格。

c++代码:

void bombs(vector<int>& v, int i, int n){
    ans += n;
    v[i] -= n;
    if(i > 0)
        v[i - 1] -= n;
    if(i + 1< v.size())
        v[i + 1] -= n;
}

void solve(vector<int> v){
    int n = v.size();
    for(int i = 0; i < n;++i){
        if(i != n - 1){
            bombs(v, i + 1, v[i]);
        }
        else
            bombs(v, i, v[i])
    }
}

对于2D: 再次强调:你不需要在第一行拍摄(如果有第二行)。所以要射到第二个。解决第一行的1D任务。(因为你需要使它为空)。下降。别忘了最后一排。

这是另一个想法:

让我们先给黑板上的每个空格分配一个权重,计算在那里扔炸弹会减少多少数字。如果这个空间有一个非零数,它就得到一个点,如果它的相邻空间有一个非零数,它就得到一个额外的点。如果这是一个1000 * 1000的网格,我们为这100万个空间中的每一个都分配了权重。

然后根据权重对列表中的空格进行排序,并轰炸权重最高的空格。可以这么说,这是我们最大的收获。

在此之后,更新每个空间的重量是受炸弹的影响。这是你轰炸的空间,和它相邻的空间,以及它们相邻的空间。换句话说,任何空间的价值都可能因为爆炸而减少为零,或者相邻空间的价值减少为零。

然后,根据权重重新排序列表空间。由于轰炸只改变了一小部分空间的权重,因此不需要使用整个列表,只需在列表中移动这些空间。

轰炸新的最高权重空间,并重复上述步骤。

这保证了每次轰炸都能减少尽可能多的空格(基本上,它会击中尽可能少的已经为零的空格),所以这是最优的,除非它们的权重是相同的。所以你可能需要做一些回溯跟踪,当有一个平局的顶部重量。不过,只有最高重量的领带重要,其他领带不重要,所以希望没有太多的回溯。

Edit: Mysticial's counterexample below demonstrates that in fact this isn't guaranteed to be optimal, regardless of ties in weights. In some cases reducing the weight as much as possible in a given step actually leaves the remaining bombs too spread out to achieve as high a cummulative reduction after the second step as you could have with a slightly less greedy choice in the first step. I was somewhat mislead by the notion that the results are insensitive to the order of bombings. They are insensitive to the order in that you could take any series of bombings and replay them from the start in a different order and end up with the same resulting board. But it doesn't follow from that that you can consider each bombing independently. Or, at least, each bombing must be considered in a way that takes into account how well it sets up the board for subsequent bombings.

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

我也有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)

这是一个广度搜索,通过这个“迷宫”的位置寻找最短路径(一系列轰炸)。不,我不能证明没有更快的算法,抱歉。

#!/usr/bin/env python

M = ((1,2,3,4),
     (2,3,4,5),
     (5,2,7,4),
     (2,3,5,8))

def eachPossibleMove(m):
  for y in range(1, len(m)-1):
    for x in range(1, len(m[0])-1):
      if (0 == m[y-1][x-1] == m[y-1][x] == m[y-1][x+1] ==
               m[y][x-1]   == m[y][x]   == m[y][x+1] ==
               m[y+1][x-1] == m[y+1][x] == m[y+1][x+1]):
        continue
      yield x, y

def bomb(m, (mx, my)):
  return tuple(tuple(max(0, m[y][x]-1)
      if mx-1 <= x <= mx+1 and my-1 <= y <= my+1
      else m[y][x]
      for x in range(len(m[y])))
    for y in range(len(m)))

def findFirstSolution(m, path=[]):
#  print path
#  print m
  if sum(map(sum, m)) == 0:  # empty?
    return path
  for move in eachPossibleMove(m):
    return findFirstSolution(bomb(m, move), path + [ move ])

def findShortestSolution(m):
  black = {}
  nextWhite = { m: [] }
  while nextWhite:
    white = nextWhite
    nextWhite = {}
    for position, path in white.iteritems():
      for move in eachPossibleMove(position):
        nextPosition = bomb(position, move)
        nextPath = path + [ move ]
        if sum(map(sum, nextPosition)) == 0:  # empty?
          return nextPath
        if nextPosition in black or nextPosition in white:
          continue  # ignore, found that one before
        nextWhite[nextPosition] = nextPath

def main(argv):
  if argv[1] == 'first':
    print findFirstSolution(M)
  elif argv[1] == 'shortest':
    print findShortestSolution(M)
  else:
    raise NotImplementedError(argv[1])

if __name__ == '__main__':
  import sys
  sys.exit(main(sys.argv))