我有一个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:我相信当我们有几个相同的情况需要最少的炸弹来清除上面的线时，我们会选择在“左侧”使用最多炸弹的一个。还有什么证据是正确的吗?
当前回答
这是另一个想法:
让我们先给黑板上的每个空格分配一个权重，计算在那里扔炸弹会减少多少数字。如果这个空间有一个非零数，它就得到一个点，如果它的相邻空间有一个非零数，它就得到一个额外的点。如果这是一个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.
其他回答
这是我的解决方案。由于时间有限，我不会用代码写出来，但我相信这应该每次都能产生最优的移动数量——尽管我不确定它在寻找要轰炸的点时是否有效。
首先，正如@Luka Rahne在一条评论中所说的，你轰炸的顺序并不重要，重要的是组合。
其次，正如许多人所说的那样，从角的对角线上轰炸1是最优的，因为它接触的点比角多。
这就生成了我的算法版本的基础: 我们可以在第一个或最后一个炸掉拐角的1-off，这没有关系(理论上) 我们首先破坏这些，因为它可以让后面的决定更容易(在实践中) 我们轰炸影响最大的点，同时轰炸那些角落。
让我们将阻力点定义为棋盘上具有最多不可炸点+周围0数量最多的点
非爆炸点可以定义为在我们正在研究的黑板的当前范围内不存在的点。
我还将定义4个处理范围的边界: 上=0，左=0，下=k，右=j。 (起始值)
最后，我将最优炸弹定义为投掷在与阻力点相邻的点上的炸弹，并接触(1)最高值的阻力点和(2)可能的最大数量的点。
关于方法，很明显我们正在从外到内的工作。我们将能够同时与4架“轰炸机”一起工作。
第一个阻力点显然是我们的弯道。“边界外”的点是不可轰炸的(每个角落的范围外都有5个点)。所以我们先在对角线上炸一个角。
算法:
找到4个最佳炸弹点。 如果一个炸弹点正在轰炸一个接触2个边界(即一个角)的阻力点，则一直轰炸到该点为0。否则，逐个轰炸，直到其中一个触及最佳轰炸点的阻力点为0。 对于每个边界: 如果(sum(bound)==0)前进界
重复以上步骤，直到上=下，左=右
稍后我将尝试编写实际代码
Pólya说:“如果你不能解决一个问题，那么有一个更容易解决的问题:找到它。”
显然更简单的问题是一维问题(当网格是单行时)。让我们从最简单的算法开始——贪婪地轰炸最大的目标。什么时候会出问题?
给定11 11，贪婪算法对先炸毁哪个单元格无关。当然，中心单元格更好——它一次将所有三个单元格归零。这就提出了一种新的算法a，“炸弹最小化剩余的总和”。这个算法什么时候会出错?
给定1 1 2 11 1，算法A在轰炸第2，第3或第4单元格之间是无所谓的。但是轰炸第二个单元格，留下0 0 11 11比轰炸第三个单元格，留下10 10 10 10 1好。如何解决这个问题?轰炸第三个单元格的问题是，左边的功和右边的功必须分开做。
“炸弹使剩余的总和最小化，但使左边(我们轰炸的地方)的最小值和右边的最小值最大化”如何?叫这个算法b，这个算法什么时候出错?
编辑:在阅读了评论之后，我同意一个更有趣的问题将是改变一维问题，使其两端连接起来。很乐意看到这方面的进展。
所有这些问题都归结为计算编辑距离。简单地计算给定矩阵和零矩阵之间的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
如果你想要绝对最优解来清理棋盘，你将不得不使用经典的回溯，但如果矩阵非常大，它将需要很长时间才能找到最佳解，如果你想要一个“可能的”最优解，你可以使用贪婪算法，如果你需要帮助写算法，我可以帮助你
现在想想，这是最好的办法。在那里制作另一个矩阵，存储通过投掷炸弹而移除的点，然后选择点数最多的单元格，并在那里投掷炸弹更新点数矩阵，然后继续。例子:
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
我想不出一个计算实际数字的方法除非用我最好的启发式方法计算轰炸行动并希望得到一个合理的结果。
So my method is to compute a bombing efficiency metric for each cell, bomb the cell with the highest value, .... iterate the process until I've flattened everything. Some have advocated using simple potential damage (i.e. score from 0 to 9) as a metric, but that falls short by pounding high value cells and not making use of damage overlap. I'd calculate cell value - sum of all neighbouring cells, reset any positive to 0 and use the absolute value of anything negative. Intuitively this metric should make a selection that help maximise damage overlap on cells with high counts instead of pounding those directly.
下面的代码在28个炸弹中达到了测试场的完全破坏(注意，使用潜在伤害作为度量，结果是31!)
using System;
using System.Collections.Generic;
using System.Linq;
namespace StackOverflow
{
internal class Program
{
// store the battle field as flat array + dimensions
private static int _width = 5;
private static int _length = 7;
private static int[] _field = new int[] {
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
};
// this will store the devastation metric
private static int[] _metric;
// do the work
private static void Main(string[] args)
{
int count = 0;
while (_field.Sum() > 0)
{
Console.Out.WriteLine("Round {0}:", ++count);
GetBlastPotential();
int cell_to_bomb = FindBestBombingSite();
PrintField(cell_to_bomb);
Bomb(cell_to_bomb);
}
Console.Out.WriteLine("Done in {0} rounds", count);
}
// convert 2D position to 1D index
private static int Get1DCoord(int x, int y)
{
if ((x < 0) || (y < 0) || (x >= _width) || (y >= _length)) return -1;
else
{
return (y * _width) + x;
}
}
// Convert 1D index to 2D position
private static void Get2DCoord(int n, out int x, out int y)
{
if ((n < 0) || (n >= _field.Length))
{
x = -1;
y = -1;
}
else
{
x = n % _width;
y = n / _width;
}
}
// Compute a list of 1D indices for a cell neighbours
private static List<int> GetNeighbours(int cell)
{
List<int> neighbours = new List<int>();
int x, y;
Get2DCoord(cell, out x, out y);
if ((x >= 0) && (y >= 0))
{
List<int> tmp = new List<int>();
tmp.Add(Get1DCoord(x - 1, y - 1));
tmp.Add(Get1DCoord(x - 1, y));
tmp.Add(Get1DCoord(x - 1, y + 1));
tmp.Add(Get1DCoord(x, y - 1));
tmp.Add(Get1DCoord(x, y + 1));
tmp.Add(Get1DCoord(x + 1, y - 1));
tmp.Add(Get1DCoord(x + 1, y));
tmp.Add(Get1DCoord(x + 1, y + 1));
// eliminate invalid coords - i.e. stuff past the edges
foreach (int c in tmp) if (c >= 0) neighbours.Add(c);
}
return neighbours;
}
// Compute the devastation metric for each cell
// Represent the Value of the cell minus the sum of all its neighbours
private static void GetBlastPotential()
{
_metric = new int[_field.Length];
for (int i = 0; i < _field.Length; i++)
{
_metric[i] = _field[i];
List<int> neighbours = GetNeighbours(i);
if (neighbours != null)
{
foreach (int j in neighbours) _metric[i] -= _field[j];
}
}
for (int i = 0; i < _metric.Length; i++)
{
_metric[i] = (_metric[i] < 0) ? Math.Abs(_metric[i]) : 0;
}
}
//// Compute the simple expected damage a bomb would score
//private static void GetBlastPotential()
//{
// _metric = new int[_field.Length];
// for (int i = 0; i < _field.Length; i++)
// {
// _metric[i] = (_field[i] > 0) ? 1 : 0;
// List<int> neighbours = GetNeighbours(i);
// if (neighbours != null)
// {
// foreach (int j in neighbours) _metric[i] += (_field[j] > 0) ? 1 : 0;
// }
// }
//}
// Update the battle field upon dropping a bomb
private static void Bomb(int cell)
{
List<int> neighbours = GetNeighbours(cell);
foreach (int i in neighbours)
{
if (_field[i] > 0) _field[i]--;
}
}
// Find the best bombing site - just return index of local maxima
private static int FindBestBombingSite()
{
int max_idx = 0;
int max_val = int.MinValue;
for (int i = 0; i < _metric.Length; i++)
{
if (_metric[i] > max_val)
{
max_val = _metric[i];
max_idx = i;
}
}
return max_idx;
}
// Display the battle field on the console
private static void PrintField(int cell)
{
for (int x = 0; x < _width; x++)
{
for (int y = 0; y < _length; y++)
{
int c = Get1DCoord(x, y);
if (c == cell)
Console.Out.Write(string.Format("[{0}]", _field[c]).PadLeft(4));
else
Console.Out.Write(string.Format(" {0} ", _field[c]).PadLeft(4));
}
Console.Out.Write(" || ");
for (int y = 0; y < _length; y++)
{
int c = Get1DCoord(x, y);
if (c == cell)
Console.Out.Write(string.Format("[{0}]", _metric[c]).PadLeft(4));
else
Console.Out.Write(string.Format(" {0} ", _metric[c]).PadLeft(4));
}
Console.Out.WriteLine();
}
Console.Out.WriteLine();
}
}
}
产生的轰炸模式输出如下(左边是字段值，右边是度量值)
Round 1:
2 1 4 2 3 2 6 || 7 16 8 10 4 18 6
3 5 3 1 1 1 9 || 11 18 18 21 17 28 5
4 [2] 4 2 3 4 1 || 19 [32] 21 20 17 24 22
7 6 2 4 4 3 6 || 8 17 20 14 16 22 8
1 2 1 1 1 2 4 || 14 15 14 11 13 16 7
Round 2:
2 1 4 2 3 2 6 || 5 13 6 9 4 18 6
2 4 2 1 1 [1] 9 || 10 15 17 19 17 [28] 5
3 2 3 2 3 4 1 || 16 24 18 17 17 24 22
6 5 1 4 4 3 6 || 7 14 19 12 16 22 8
1 2 1 1 1 2 4 || 12 12 12 10 13 16 7
Round 3:
2 1 4 2 2 1 5 || 5 13 6 7 3 15 5
2 4 2 1 0 1 8 || 10 15 17 16 14 20 2
3 [2] 3 2 2 3 0 || 16 [24] 18 15 16 21 21
6 5 1 4 4 3 6 || 7 14 19 11 14 19 6
1 2 1 1 1 2 4 || 12 12 12 10 13 16 7
Round 4:
2 1 4 2 2 1 5 || 3 10 4 6 3 15 5
1 3 1 1 0 1 8 || 9 12 16 14 14 20 2
2 2 2 2 2 [3] 0 || 13 16 15 12 16 [21] 21
5 4 0 4 4 3 6 || 6 11 18 9 14 19 6
1 2 1 1 1 2 4 || 10 9 10 9 13 16 7
Round 5:
2 1 4 2 2 1 5 || 3 10 4 6 2 13 3
1 3 1 1 0 [0] 7 || 9 12 16 13 12 [19] 2
2 2 2 2 1 3 0 || 13 16 15 10 14 15 17
5 4 0 4 3 2 5 || 6 11 18 7 13 17 6
1 2 1 1 1 2 4 || 10 9 10 8 11 13 5
Round 6:
2 1 4 2 1 0 4 || 3 10 4 5 2 11 2
1 3 1 1 0 0 6 || 9 12 16 11 8 13 0
2 2 2 2 0 2 0 || 13 16 15 9 14 14 15
5 4 [0] 4 3 2 5 || 6 11 [18] 6 11 15 5
1 2 1 1 1 2 4 || 10 9 10 8 11 13 5
Round 7:
2 1 4 2 1 0 4 || 3 10 4 5 2 11 2
1 3 1 1 0 0 6 || 8 10 13 9 7 13 0
2 [1] 1 1 0 2 0 || 11 [15] 12 8 12 14 15
5 3 0 3 3 2 5 || 3 8 10 3 8 15 5
1 1 0 0 1 2 4 || 8 8 7 7 9 13 5
Round 8:
2 1 4 2 1 0 4 || 1 7 2 4 2 11 2
0 2 0 1 0 0 6 || 7 7 12 7 7 13 0
1 1 0 1 0 2 0 || 8 8 10 6 12 14 15
4 2 0 3 3 [2] 5 || 2 6 8 2 8 [15] 5
1 1 0 0 1 2 4 || 6 6 6 7 9 13 5
Round 9:
2 1 4 2 1 0 4 || 1 7 2 4 2 11 2
0 2 0 1 0 0 6 || 7 7 12 7 6 12 0
1 1 0 1 0 [1] 0 || 8 8 10 5 10 [13] 13
4 2 0 3 2 2 4 || 2 6 8 0 6 9 3
1 1 0 0 0 1 3 || 6 6 6 5 8 10 4
Round 10:
2 1 4 2 1 0 4 || 1 7 2 4 2 10 1
0 2 [0] 1 0 0 5 || 7 7 [12] 7 6 11 0
1 1 0 1 0 1 0 || 8 8 10 4 8 9 10
4 2 0 3 1 1 3 || 2 6 8 0 6 8 3
1 1 0 0 0 1 3 || 6 6 6 4 6 7 2
Round 11:
2 0 3 1 1 0 4 || 0 6 0 3 0 10 1
0 1 0 0 0 [0] 5 || 4 5 5 5 3 [11] 0
1 0 0 0 0 1 0 || 6 8 6 4 6 9 10
4 2 0 3 1 1 3 || 1 5 6 0 5 8 3
1 1 0 0 0 1 3 || 6 6 6 4 6 7 2
Round 12:
2 0 3 1 0 0 3 || 0 6 0 2 1 7 1
0 1 0 0 0 0 4 || 4 5 5 4 1 7 0
1 0 0 0 0 [0] 0 || 6 8 6 4 5 [9] 8
4 2 0 3 1 1 3 || 1 5 6 0 4 7 2
1 1 0 0 0 1 3 || 6 6 6 4 6 7 2
Round 13:
2 0 3 1 0 0 3 || 0 6 0 2 1 6 0
0 1 0 0 0 0 3 || 4 5 5 4 1 6 0
1 [0] 0 0 0 0 0 || 6 [8] 6 3 3 5 5
4 2 0 3 0 0 2 || 1 5 6 0 4 6 2
1 1 0 0 0 1 3 || 6 6 6 3 4 4 0
Round 14:
2 0 3 1 0 [0] 3 || 0 5 0 2 1 [6] 0
0 0 0 0 0 0 3 || 2 5 4 4 1 6 0
0 0 0 0 0 0 0 || 4 4 4 3 3 5 5
3 1 0 3 0 0 2 || 0 4 5 0 4 6 2
1 1 0 0 0 1 3 || 4 4 5 3 4 4 0
Round 15:
2 0 3 1 0 0 2 || 0 5 0 2 1 4 0
0 0 0 0 0 0 2 || 2 5 4 4 1 4 0
0 0 0 0 0 0 0 || 4 4 4 3 3 4 4
3 1 0 3 0 [0] 2 || 0 4 5 0 4 [6] 2
1 1 0 0 0 1 3 || 4 4 5 3 4 4 0
Round 16:
2 [0] 3 1 0 0 2 || 0 [5] 0 2 1 4 0
0 0 0 0 0 0 2 || 2 5 4 4 1 4 0
0 0 0 0 0 0 0 || 4 4 4 3 3 3 3
3 1 0 3 0 0 1 || 0 4 5 0 3 3 1
1 1 0 0 0 0 2 || 4 4 5 3 3 3 0
Round 17:
1 0 2 1 0 0 2 || 0 3 0 1 1 4 0
0 0 0 0 0 0 2 || 1 3 3 3 1 4 0
0 0 0 0 0 0 0 || 4 4 4 3 3 3 3
3 1 [0] 3 0 0 1 || 0 4 [5] 0 3 3 1
1 1 0 0 0 0 2 || 4 4 5 3 3 3 0
Round 18:
1 0 2 1 0 0 2 || 0 3 0 1 1 4 0
0 0 0 0 0 0 2 || 1 3 3 3 1 4 0
0 0 0 0 0 0 0 || 3 3 2 2 2 3 3
3 [0] 0 2 0 0 1 || 0 [4] 2 0 2 3 1
1 0 0 0 0 0 2 || 2 4 2 2 2 3 0
Round 19:
1 0 2 1 0 [0] 2 || 0 3 0 1 1 [4] 0
0 0 0 0 0 0 2 || 1 3 3 3 1 4 0
0 0 0 0 0 0 0 || 2 2 2 2 2 3 3
2 0 0 2 0 0 1 || 0 2 2 0 2 3 1
0 0 0 0 0 0 2 || 2 2 2 2 2 3 0
Round 20:
1 [0] 2 1 0 0 1 || 0 [3] 0 1 1 2 0
0 0 0 0 0 0 1 || 1 3 3 3 1 2 0
0 0 0 0 0 0 0 || 2 2 2 2 2 2 2
2 0 0 2 0 0 1 || 0 2 2 0 2 3 1
0 0 0 0 0 0 2 || 2 2 2 2 2 3 0
Round 21:
0 0 1 1 0 0 1 || 0 1 0 0 1 2 0
0 0 0 0 0 0 1 || 0 1 2 2 1 2 0
0 0 0 0 0 0 0 || 2 2 2 2 2 2 2
2 0 0 2 0 [0] 1 || 0 2 2 0 2 [3] 1
0 0 0 0 0 0 2 || 2 2 2 2 2 3 0
Round 22:
0 0 1 1 0 0 1 || 0 1 0 0 1 2 0
0 0 0 0 0 0 1 || 0 1 2 2 1 2 0
[0] 0 0 0 0 0 0 || [2] 2 2 2 2 1 1
2 0 0 2 0 0 0 || 0 2 2 0 2 1 1
0 0 0 0 0 0 1 || 2 2 2 2 2 1 0
Round 23:
0 0 1 1 0 0 1 || 0 1 0 0 1 2 0
0 0 [0] 0 0 0 1 || 0 1 [2] 2 1 2 0
0 0 0 0 0 0 0 || 1 1 2 2 2 1 1
1 0 0 2 0 0 0 || 0 1 2 0 2 1 1
0 0 0 0 0 0 1 || 1 1 2 2 2 1 0
Round 24:
0 0 0 0 0 0 1 || 0 0 0 0 0 2 0
0 0 0 0 0 0 1 || 0 0 0 0 0 2 0
0 0 [0] 0 0 0 0 || 1 1 [2] 2 2 1 1
1 0 0 2 0 0 0 || 0 1 2 0 2 1 1
0 0 0 0 0 0 1 || 1 1 2 2 2 1 0
Round 25:
0 0 0 0 0 [0] 1 || 0 0 0 0 0 [2] 0
0 0 0 0 0 0 1 || 0 0 0 0 0 2 0
0 0 0 0 0 0 0 || 1 1 1 1 1 1 1
1 0 0 1 0 0 0 || 0 1 1 0 1 1 1
0 0 0 0 0 0 1 || 1 1 1 1 1 1 0
Round 26:
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
[0] 0 0 0 0 0 0 || [1] 1 1 1 1 0 0
1 0 0 1 0 0 0 || 0 1 1 0 1 1 1
0 0 0 0 0 0 1 || 1 1 1 1 1 1 0
Round 27:
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 [0] 0 0 0 0 || 0 0 [1] 1 1 0 0
0 0 0 1 0 0 0 || 0 0 1 0 1 1 1
0 0 0 0 0 0 1 || 0 0 1 1 1 1 0
Round 28:
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 [0] 0 || 0 0 0 0 0 [1] 1
0 0 0 0 0 0 1 || 0 0 0 0 0 1 0
Done in 28 rounds
