我有一个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:我相信当我们有几个相同的情况需要最少的炸弹来清除上面的线时,我们会选择在“左侧”使用最多炸弹的一个。还有什么证据是正确的吗?
在这里,线性规划方法似乎非常有用。
设Pm x n为包含位置值的矩阵:
现在定义一个炸弹矩阵B(x, y)m x n,其中1≤x≤m, 1≤y≤n如下所示
以这样一种方式
例如:
所以我们正在寻找一个矩阵Bm x n = [bij]
可以定义为炸弹矩阵的和:
(qij将是我们在pij位置投放的炸弹数量)
pij - bij≤0(为了更简洁,我们称之为P - B≤0)
而且,B应该使和最小。
我们也可以把B写成前面的丑矩阵:
由于P - B≤0(即P≤B),我们得到了如下线性不等式系统:
qmn x1定义为
PMN x 1定义为
我们可以说我们有一个方程组是smnxmn这个矩阵要倒转来解方程组。我自己没有扩展它,但我相信在代码中应该很容易做到。
现在,我们有一个最小的问题可以表述为
I believe it is something easy, almost trivial to be solved with something like the simplex algorithm (there is this rather cool doc about it). However, I do know almost no linear programming (I will take a course about it on Coursera but it is just in the future...), I had some headaches trying to understand it and I have a huge freelance job to finish so I just give up here. It can be that I did something wrong at some point, or that it can't go any further, but I believe this path can eventually lead to the solution. Anyway, I am anxious for your feedback.
(特别感谢这个神奇的网站从LaTeX表达式创建图片)
蛮力!
我知道它效率不高,但即使你找到了一个更快的算法,你也可以对这个结果进行测试,以了解它有多准确。
使用一些递归,像这样:
void fn(tableState ts, currentlevel cl)
{
// first check if ts is all zeros yet, if not:
//
// do a for loop to go through all cells of ts,
// for each cell do a bomb, and then
// call:
// fn(ts, cl + 1);
}
你可以通过缓存来提高效率,如果不同的方法导致相同的结果,你不应该重复相同的步骤。
阐述:
如果轰炸单元格1,3,5的结果与轰炸单元格5,3,1的结果相同,那么,对于这两种情况,您不应该重新执行所有后续步骤,只需1就足够了,您应该将所有表状态存储在某个地方并使用其结果。
表统计信息的散列可以用于快速比较。
这是我的解决方案。由于时间有限,我不会用代码写出来,但我相信这应该每次都能产生最优的移动数量——尽管我不确定它在寻找要轰炸的点时是否有效。
首先,正如@Luka Rahne在一条评论中所说的,你轰炸的顺序并不重要,重要的是组合。
其次,正如许多人所说的那样,从角的对角线上轰炸1是最优的,因为它接触的点比角多。
这就生成了我的算法版本的基础:
我们可以在第一个或最后一个炸掉拐角的1-off,这没有关系(理论上)
我们首先破坏这些,因为它可以让后面的决定更容易(在实践中)
我们轰炸影响最大的点,同时轰炸那些角落。
让我们将阻力点定义为棋盘上具有最多不可炸点+周围0数量最多的点
非爆炸点可以定义为在我们正在研究的黑板的当前范围内不存在的点。
我还将定义4个处理范围的边界:
上=0,左=0,下=k,右=j。
(起始值)
最后,我将最优炸弹定义为投掷在与阻力点相邻的点上的炸弹,并接触(1)最高值的阻力点和(2)可能的最大数量的点。
关于方法,很明显我们正在从外到内的工作。我们将能够同时与4架“轰炸机”一起工作。
第一个阻力点显然是我们的弯道。“边界外”的点是不可轰炸的(每个角落的范围外都有5个点)。所以我们先在对角线上炸一个角。
算法:
找到4个最佳炸弹点。
如果一个炸弹点正在轰炸一个接触2个边界(即一个角)的阻力点,则一直轰炸到该点为0。否则,逐个轰炸,直到其中一个触及最佳轰炸点的阻力点为0。
对于每个边界:
如果(sum(bound)==0)前进界
重复以上步骤,直到上=下,左=右
稍后我将尝试编写实际代码
你可以把这个问题表示成整数规划问题。(这只是解决这个问题的一种可能的方法)
有分:
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困难。
所有这些问题都归结为计算编辑距离。简单地计算给定矩阵和零矩阵之间的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
这是一个广度搜索,通过这个“迷宫”的位置寻找最短路径(一系列轰炸)。不,我不能证明没有更快的算法,抱歉。
#!/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))