动态规划 - 最大正方形块

Question

动态规划 - 最大正方形块

42

我需要在一个充满1和0的巨大文件中找到最大的1方块。我知道我必须使用动态规划。我将其存储在一个二维数组中。如果能提供查找最大方块的算法，那就太好了，谢谢！

例子输入：

1 0 1 0 1 0
1 0 1 1 1 1
0 1 1 1 1 1
0 0 1 1 1 1
1 1 1 1 1 1

答案：

我的代码如下：

int Square (Sq[int x][int y]) {
   if (Sq[x][y]) == 0) {
       return 0;
   }
   else {
       return 1+MIN( Sq(X-1,Y), Sq(X,Y-1), Sq(X-1,Y-1) );
   }
}

（假设值已经输入到数组中）

int main() {
    int Sq[5][6]; //5,6 = bottom right conner
    int X = Square(Sq[5][6]);
}

我该从哪里开始呢？

- batt

2

请提供你目前的研究结果摘要。 - LeopardSkinPillBoxHat

1

@jeffamaphone：这个示例输入不是很清晰。你可以根据自己的理解得出结论；-) - Steve Jessop

非常感谢您的提问 - 我将在下个学期的教程中将其作为练习。 - Konrad Rudolph

相关：https://dev59.com/J3E95IYBdhLWcg3wDpmg - jfs

2

任何想要将此问题作为练习的人都应该查看来自南部东部区域ACM ICPC 2010问题集的问题E：最大正方形：http://ser.cs.fit.edu/ser2010/problems/实现算法，并根据评委的输入/输出文件进行测试。 - Dream Lane

显示剩余2条评论

7个回答

8

LSBRA(X,Y)的意思是“右下角位置为X，Y的最大正方形”

伪代码：

LSBRA(X,Y):
   if (x,y) == 0:
       0
   else:
       1+MIN( LSBRA(X-1,Y), LSBRA(X,Y-1), LSBRA(X-1,Y-1) )

（对于边缘单元格，您可以跳过MIN部分，如果（x，y）不为0，则返回1。）

在网格中对角线“波浪式”地工作，如下所示：

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 2 3 4 5 6
2 | 3 4 5 6 7
3 | 4 5 6 7 8

或者，您可以从左到右、从上到下逐步填写边缘单元格。

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 6 7 8 9 .
2 | . . . . .
3 | . . . . .

这样，您就不会遇到以前没有计算必要数据的计算 - 所有LSBRA()的“调用”实际上只是先前计算结果的表查找（因此具有动态编程方面）。

为什么它起作用

为了在 X、Y 的右下角拥有一个正方形 - 它必须包含每个其他 3 个角的一个少一维的重叠正方形。换句话说，要拥有

XXXX
XXXX
XXXX
XXXX

您还必须拥有...

XXX.    .XXX    ....    ....
XXX.    .XXX    XXX.    ....
XXX.    .XXX    XXX.    ....
....    ....    XXX.    ...X

只要您有这三个（LSBRA检查中的每一个）大小为 N 的正方形，加上当前正方形也“被占据”，您将拥有一个大小为 (N+1) 的正方形。

- Amber

抱歉，能请您再解释一下这段伪代码吗？LSBRA是一个返回整数（最大值？）的函数，而min则返回3个传入参数中最小的LSBRA值。 - batt

LSBRA只是“计算此值”的占位符。对于动态规划实现，它基本上意味着“在X,Y处存储的结果数组中的值是什么”。对于递归实现，它将是一个函数。是的，MIN()表示取参数中的最小值。 - Amber

我用你的解决方案编辑了我的原始帖子，但似乎不正确。你能看一下吗？ =] - batt

3

我首先想到的算法是：

将第一列/行与第二列/行进行 '&&' 操作，即对每个条目及其相应位于另一列/行的条目执行 '&&' 操作。
检查生成的列，如果存在任何长度为2的1，这意味着我们击中了一个2x2的正方形。
将下一列与前两个结果进行 '&&' 操作。如果有任何长度为3的1，则表示我们击中了一个3x3的正方形。
重复，直到所有列都被使用。
从第2列开始重复步骤1-4。

我不会展示具体实现，因为它很简单，而且你的问题听起来像作业。此外，如果输入非常大，可能有更高效的方法可用，因为该方法会变得很慢。

- DeusAduro

2

假设输入矩阵为M：n x m

T[i][j]是DP矩阵，其中包含以正方形右下角(i,j)为底的最大正方形边长。

填充表格的一般规则：

if (M[i][j] == 1) {
  int v = min(T[i][j-1], T[i-1][j]);
  v = min(v, T[i-1][j-1]);
  T[i][j] = v + 1;
}
else 
  T[i][j] = 0;

结果正方形的大小是T中的最大值。

填充T [i] [0]和T [0] [j]很容易。

我不确定这个算法是否适用于您的大文件，但您只需要存储当前和前一行而不是整个矩阵T。

以下注释可以帮助理解总体思路：

所有右下角为（i-1，j），（i，j-1），（i-1，j-1）且大小为s的正方形都在右下角为（i，j）且大小为s + 1的正方形内。
如果存在右下角为（i，j）且大小为s + 1的正方形，则具有右下角角（i-1，j），（i，j-1），（i-1，j-1）的最大正方形的大小至少为s。
相反也是如此。如果至少一个底部右角在（i-1，j），（i，j-1），（i-1，j-1）处的正方形的大小小于s，则具有右下角在（i，j）处的正方形的大小不能大于s + 1。

- sergtk

谢谢你的帮助，但是你说的“结果方面”和填充T[i][0]和T[0][i]是什么意思？有没有更快的方式可以联系到你？ - batt

结果正方形的大小等于T中的最大值。 - sergtk

这个简单公式背后的逻辑是什么？ - Schultz9999

我已经在答案中添加了一些说明，请希望它们是有用的。 - sergtk

1

好的，最低效但简单的方法是：

选择第一个项目。检查是否为1，如果是，则有一个1x1的正方形。
检查下面和右边的一个，如果是1，则检查第2行第2列，如果是1，则为2x2的正方形。
检查第3行第1列、第2列和第3列，以及第1行第3列、第2行第3列，如果是1，则为3x3的正方形。
因此，基本上您需要同时扩展行和列，并检查它们边界内的所有单元格。一旦遇到0，就会中断，所以您在行中向前移动1个点，然后重新开始。
在行末，移动到下一行。
直到结束。

你可能已经看到了这些如何适应while循环等，以及如何使用&&来检查0，当你看着它时，你可能还会注意到如何加速它。但正如其他答案所提到的，它听起来有点像作业，所以我们将把实际的代码留给你自己。

祝好运！

- Mark Mayo

1

关键在于使用动态规划来跟踪区域的根而不是实际区域。

算法如下：

存储一个名为max-square的二维整数数组，其中索引i，j表示它所在的正方形的大小，i，j是右下角。（如果max [i，j] = 2，则表示索引i，j是边长为2的正方形的右下角，面积为2^2 = 4）

对于每个索引i，j：

如果在i，j处元素为0，则将max-square i，j设置为0。

否则：

找到max-square [i-1，j]和max-square [i，j-1]以及max-square [i-1] [j-1]的最小值。将max-square [i，j]设置为3者中的最小值加1。归纳地，您将填写max-square数组。在此过程中查找或跟踪最大值，并返回该值的平方。

请看这些人提出的解决方案： https://leetcode.com/discuss/questions/oj/maximal-square?sort=votes

- Han Sheng Huang

0

设N为2D数组中单元格的数量。存在一种非常高效的算法来列出所有最大空矩形。最大的空正方形位于这些空矩形之一内，一旦计算出最大空矩形列表，找到它就很容易了。可以在www.ulg.ac.be/telecom/rectangles找到一篇介绍如何创建此类列表的O(N)算法的论文以及源代码（未经优化）。请注意，存在一个证明（见论文），即最大空矩形的数量受N的限制。因此，在O(N)的时间内选择最大的空正方形是可行的，整个方法也是O(N)的。实际上，这种方法非常快速。实现非常容易，因为整个代码不应超过40行C（用于列出所有最大空矩形的算法需要约30行C）。

- Sébastien Piérard

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joy Dutta · Accepted Answer

以下是解决方案的草图：

对于每个单元，我们将保留一个计数器，用于指示该单元作为左上角时可以制作多大的正方形。显然，所有值为0的单元格都将具有0的计数。

从右下角单元开始迭代，然后转向左下角，然后再向上一行并重复。

在每次扫描时执行以下操作：

如果单元格的值为0，则将 count=0
如果单元格的值为1，并且是边缘单元格（仅限底部或右侧边缘），则将 count=1
对于所有其他单元格，请检查其右侧、右下和下方的单元格的计数。取它们的最小值加1，并将其分配给计数。保持全局 max_count 变量以跟踪到目前为止的最大计数。

遍历矩阵结束时，max_count 将具有所需的值。

复杂度不超过遍历矩阵的成本。

这是遍历矩阵后矩阵的样子。括号中的值是计数，即使用该单元格作为左上角可以制作的最大正方形。

1(1) 0(0) 1(1) 0(0) 1(1) 0(0)
1(1) 0(0) 1(4) 1(3) 1(2) 1(1)
0(0) 1(1) 1(3) 1(3) 1(2) 1(1)
0(0) 0(0) 1(2) 1(2) 1(2) 1(1)
1(1) 1(1) 1(1) 1(1) 1(1) 1(1)

Python实现

def max_size(mat, ZERO=0):
    """Find the largest square of ZERO's in the matrix `mat`."""
    nrows, ncols = len(mat), (len(mat[0]) if mat else 0)
    if not (nrows and ncols): return 0 # empty matrix or rows
    counts = [[0]*ncols for _ in xrange(nrows)]
    for i in reversed(xrange(nrows)):     # for each row
        assert len(mat[i]) == ncols # matrix must be rectangular
        for j in reversed(xrange(ncols)): # for each element in the row
            if mat[i][j] != ZERO:
                counts[i][j] = (1 + min(
                    counts[i][j+1],  # east
                    counts[i+1][j],  # south
                    counts[i+1][j+1] # south-east
                    )) if i < (nrows - 1) and j < (ncols - 1) else 1 # edges
    return max(c for rows in counts for c in rows)