19

假设给定一个 mXn 位图，由数组 M[1..m,1..n] 表示，其条目全为 0 或 1。全为 1 的块是 M[i .. i0, 形式的子数组， j .. j0]，其中每个比特都等于 1。描述和分析一种有效的算法，以在 M 中找到最大面积的全一块

我正在尝试制作一个动态编程解决方案。但是我的递归算法在 O(n^n) 时间内运行，即使在记忆化之后，我也无法将其降低到 O(n^4) 以下。有人可以帮我找到更有效的解决方案吗？

4

4 回答 4

24

O(N)（元素数量）解决方案：

A
1 1 0 0 1 0
0 1 1 1 1 1
1 1 1 1 1 0
0 0 1 1 0 0

生成一个数组C，其中每个元素表示上面 1 的数量，包括它，直到第一个 0。

C
1 1 0 0 1 0
0 2 1 1 2 1
1 3 2 2 3 0
0 0 3 3 0 0

我们想要找到最大化的行R和左、右l索引。这是一个在 O(cols) 时间内检查每一行的算法：r(r-l+1)*min(C[R][l..r])

保持一堆对(h, i)，在哪里C[R][i-1] < h ≤ C[R][i]。在任何位置 cur，我们应该对堆栈上的h=min(C[R][i..cur])所有对都有。(h, i)

对于每个元素：

  • 如果h_cur>h_top
    • 推(h, i)。
  • 别的：
    • 虽然h_cur<h_top：
      • 弹出栈顶。
      • 检查它是否会成为一个新的最好的，即(i_cur-i_pop)*h_pop > best。
    • 如果h_cur>h_top
      • 推(h, i_lastpopped)。

在我们的示例中执行第三行的示例：

  i =0      1      2      3      4      5
C[i]=1      3      2      2      3      0
                                 (3, 4)
 S=         (3, 1) (2, 1) (2, 1) (2, 1)
     (1, 0) (1, 0) (1, 0) (1, 0) (1, 0)    
     (0,-1) (0,-1) (0,-1) (0,-1) (0,-1) (0,-1)

i=0, C[i]=1) 推(1, 0)。
i=1, C[i]=3) 推(3, 1)。
i=2, C[i]=2) 流行音乐(3, 1)。检查是否(2-1)*3=3是新的最好的。
        最后i弹出的是 1，所以 push (2, 1)。
i=3, C[i]=2)h_cur=h_top所以什么也不做。
i=4, C[i]=3) 推(3, 4)。
i=5, C[i]=0) 流行音乐(3, 4)。检查是否(5-4)*3=3是新的最好的。
        流行音乐 (2, 1)。检查是否(5-1)*2=8是新的最好的。
        流行音乐 (1, 0)。检查是否(5-0)*1=5是新的最好的。
        结尾。（好的，我们可能应该在末尾添加一个额外的术语 C[cols]=0 以更好地衡量）。

于 2010-09-28T07:51:03.560 回答
10

这是一个O(numCols*numLines^2)算法。让S[i][j] = sum of the first i elements of column j.

我将在这个例子中使用算法：

M
1 1 0 0 1 0
0 1 1 1 0 1
1 1 1 1 0 0
0 0 1 1 0 0

我们有：

S
1 1 0 0 1 0
1 2 1 1 1 1
2 3 2 2 1 1 
2 3 3 3 1 1

现在考虑在一个一维数组中找到所有子数组的最大子数组的问题。这可以使用这个简单的算法来解决：

append 0 to the end of your array
max = 0, temp = 0
for i = 1 to array.size do
  if array[i] = 1 then
    ++temp
  else
    if temp > max then
      max = temp
    temp = 0

例如，如果您有这个一维数组：

1 2 3 4 5 6
1 1 0 1 1 1

你会这样做：

首先附加一个0：

1 2 3 4 5 6 7
1 1 0 1 1 1 0

现在，请注意，每当您点击 a 时0，您就知道连续的序列在哪里结束。因此，如果您保留当前个数的运行总计（temp变量），您可以将该总数与max达到零时的最大值（变量）进行比较，然后重置运行总计。这将为您提供变量中连续序列的最大长度max。

现在你可以使用这个子算法来找到你的问题的解决方案。首先将一0列附加到您的矩阵中。然后计算S。

然后：

max = 0
for i = 1 to M.numLines do
  for j = i to M.numLines do
    temp = 0
    for k = 1 to M.numCols do
      if S[j][k] - S[i-1][k] = j - i + 1 then
        temp += j - i + 1
      else
        if temp > max then
          max = temp
        temp = 0

基本上，对于子数组的每个可能高度（有O(numLines^2)可能的高度），您可以通过应用一维数组的算法（in O(numCols)）找到具有该高度的最大面积的那个。

考虑以下“图片”：

   M
   1 1 0 0 1 0 0
i  0 1 1 1 0 1 0
j  1 1 1 1 0 0 0
   0 0 1 1 0 0 0

这意味着我们的高度是j - i + 1固定的。现在，取矩阵中介于两者之间的所有i元素j：

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

请注意，这类似于一维问题。让我们对列求和，看看我们得到了什么：

1 2 2 2 0 1 0

现在，问题被简化为一维情况，除了我们必须找到连续j - i + 1（2在这种情况下）值的子序列。这意味着我们的j - i + 1“窗口”中的每一列都必须满是 1。S我们可以使用矩阵有效地检查这一点。

要了解其S工作原理，请再次考虑一维情况：让s[i] = sum of the first i elements of the vector a. 那么子序列的总和是a[i..j]多少？它是直到和包括的所有元素a[j]的总和，减去直到和包括的所有元素的a[i-1]总和s[j] - s[i-1]。2d 案例的工作方式相同，除了我们s为每一列都有一个。

我希望这很清楚，如果您还有其他问题，请提出。

我不知道这是否符合您的需求，但我认为还有一种O(numLines*numCols)基于动态编程的算法。我还不能弄清楚，除了你所追求的子数组是正方形的情况。然而，有人可能有更好的洞察力，所以再等一会儿。

于 2010-09-27T19:21:29.107 回答
1

定义一个新矩阵 A，它将在 A[i,j] 中存储两个值：左上角为 i,j 的最大子矩阵的宽度和高度，从右下角开始填充此矩阵，按行底部到达顶点。你会发现四种情况： 在 [i,j]=1 给定矩阵时执行这些情况

情况1：原始矩阵中的右或下相邻元素都不等于当前元素，即：M[i,j] != M[i+1,j] and M[i,j] != M [i,j+1] 为 M 原始矩阵，此时 A[i,j] 的值为 1x1

情况2：右边的邻居元素等于当前元素但底部不同，A[i,j].width的值为A[i+1,j].width+1和A[i ,j].height=1

情况3：到底部的相邻元素相等但右边不同，A[i,j].width=1, A[i,j].height=A[i,j+1].height+1

情况4：两个邻居相等：考虑三个矩形：

  1. A[i,j].width=A[i,j+1].width+1; A[i,j].height=1;

  2. A[i,j].height=A[i+1,j].height+1; a[i,j].width=1;

  3. A[i,j].width = min(A[i+1,j].width+1,A[i,j+1].width) 和 A[i,j].height = min(A[i ,j+1]+1,A[i+1,j])

以上三种情况中面积最大的将被视为代表该位置的矩形。

左上角位于 i,j 的最大矩阵的大小为 A[i,j].width*A[i,j].height ，因此您可以更新在计算 A[i,j 时找到的最大值]

最底行和最右边的列元素被视为分别位于底部和右侧的相邻元素不同。

于 2014-07-15T05:11:03.633 回答
0

这是 C# 中的 O(N) 实现。

这个想法是使用动态规划来构建一个累积矩阵，该矩阵具有最大子矩阵的大小，包括当前单元格本身。

    public static int LargestSquareMatrixOfOne(int[,] original_mat)
    {
        int[,] AccumulatedMatrix = new int[original_mat.GetLength(0), original_mat.GetLength(1)];
        AccumulatedMatrix[0, 0] = original_mat[0, 0];
        int biggestSize = 1;
        for (int i = 0; i < original_mat.GetLength(0); i++)
        {
            for (int j = 0; j < original_mat.GetLength(1); j++)
            {
                if (i > 0 && j > 0)
                {
                    if (original_mat[i, j] == 1)
                    {
                        AccumulatedMatrix[i, j] = Math.Min(AccumulatedMatrix[i - 1, j - 1], (Math.Min(AccumulatedMatrix[i - 1, j], AccumulatedMatrix[i, j - 1]))) + 1;
                        if (AccumulatedMatrix[i, j] > biggestSize)
                        {
                            biggestSize = AccumulatedMatrix[i, j];
                        }
                    }
                    else
                    {
                        AccumulatedMatrix[i, j] = 0;
                    }
                }
                else if ( (i > 0 && j == 0) || (j > 0 && i == 0))
                {
                    if (original_mat[i, j] == 1) { AccumulatedMatrix[i, j] = 1; }
                    else { AccumulatedMatrix[i, j] = 0; }
                }
            }
        }
        return biggestSize;
    }
于 2017-04-12T20:14:39.213 回答