寻找由0和1组成的矩形中最大块的朴素方法

Question

寻找由0和1组成的矩形中最大块的朴素方法

7

我正在尝试想出一种暴力（朴素）解法来查找一个由1和0组成的矩形中最大的连续1或0块。我知道有些最优解法可以在O(n)时间内完成，其中n是矩形的总大小。

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

在上面的矩形中，这是从 (第 2 行，第 2 列) 开始大小为 6 的矩形。我在想...

遍历每个元素，然后通过在其所有方向上迭代来找到它所形成的大小。

这是暴力方法吗？复杂度是多少？我正在遍历所有元素，即 n，但然后我在所有方向上都进行了迭代，这会是多少？

我知道这个问题已经被问了100次，但他们谈论的是最优解。我要找的是一个暴力解法及其复杂度？

- questions

你不需要走所有的方向，只需向右和向下走（我认为这仍然被视为暴力搜索，只是稍微快了一些）。 - Bernhard Barker

“遍历每个元素” - 按什么顺序？性能取决于此。在一种稀疏网格中选择元素比栅格排序更好，尽管两者都可能符合“蛮力法”的要求。 - anatolyg

@OP，你所描述的算法实际上会多次迭代子矩形。它甚至可能比暴力搜索更糟糕，因为它会多次考虑相同的候选项。 :) - Shashank

如果你从矩形中的每个元素只向右和向下迭代，并且在发现子矩形混合了0和1后立即放弃，那么你就是在使用回溯法，这可能比暴力法更有效（尽管最坏情况下仍可能是O(N^3)）。 - Shashank

3个回答

1

暴力破解通常被分为两个（有时是顺序的）部分。第一部分是生成问题的所有可能解决方案的候选项。第二部分是测试这些候选项以查看它们是否实际上是解决方案。

暴力破解：假设您的矩形是m x n。生成所有大小为a x b的子矩形，其中a在{1..m}中，b在{1..n}中。将maximum变量设置为0。测试所有子矩形以查看它是否全部为0和1。如果是，则让maximum = max(maximum, size(sub-rectangle)。或者，仅从测试较大的子矩形开始，并向测试较小的子矩形移动。一旦找到一个全为0或1的子矩形，请停止。时间复杂度将相同，因为在两种方法的最坏情况下，您仍然必须遍历所有子矩形。

时间复杂度：

让我们计算每个步骤产生的子矩形的数量。

大小为1 x 1的子矩形有m*n个。

对于大小为2×1的小矩形，有(m-1)×n个。

对于大小为1×2的小矩形，有m×(n-1)个。

对于大小为2×2的小矩形，有(m-1)×(n-1)个。

...等等

对于大小为a×b的子矩形，从大小为m×n的大矩形中计算子矩形的数量的公式是：

number_of_subrectangles_of_size_a_b = (m-a) * (n-b)

如果我们想象这些数字排列在一个算术序列中，我们得到：

1*1 + 1*2 + ... + 1*n + 2*1 + ... + m*n

这可以分解为：

(1 + 2 + ... + m) * (1 + 2 + ... + n).

这两个算术序列收敛到O(m²)和O(n²)。因此，生成m*n矩形的所有子矩形的时间复杂度为O(m²n²)。现在我们看测试阶段。

生成所有子矩形后，测试大小为a x b的每个子矩形是否全为0或全为1的时间复杂度为O(a*b)。与生成大小为a x b的子矩形的前一步骤不同，该步骤随着a x b的增加而成比例地增加。

例如：大小为m x n的子矩形只有1个。但是测试该矩形是否全为0或全为1需要O(m*n)的时间。相反，大小为1的子矩形有m*n个。但是测试这些矩形是否全为0或全为1只需要每个矩形O(1)的时间。

最终时间复杂度的计算公式如下:

O( (m-(m-1))(n-(n-1))*(mn) + (m-(m-1))(n-(n-2))*m(n-1)... + mn*(m-(m-1))(n-(n-1)) )

请注意以下两点：

该序列中最大的项将接近于 (m/2)(n/2)(m/2)(n/2)，即 O(m²n²)。
该序列总共有 m * n 个项。

因此，暴力解法的测试阶段时间复杂度为 O(mn * m²n²) = O(m³n³)。

总时间复杂度为：

O(generating) + O(testing) = O(m²n² + m³n³) = O(m³n³)

如果给定矩形的面积为N，那么时间复杂度为O(N³)。

- Shashank

感谢您提供如此详细的答案！ - questions

0

可以研究“连通组件”算法以获取更多想法。你所呈现的二维二进制值数组看起来就像是一个二进制的黑白图像。一个重要的例外是，在图像处理中，我们通常允许连接组件（0或1的斑点）具有非矩形的形状。对现有的多通和单通算法进行一些调整应该很容易实现。

http://en.wikipedia.org/wiki/Connected-component_labeling

虽然这是一个比你需要的更一般化的解决方案，但你也可以运行连接组件算法来查找所有连接区域（0或1，背景或前景），然后过滤结果组件（也称为 blob）。我还要提到，对于前景组件，最好选择“4 连通性”而不是“8 连通性”，其中前者意味着仅允许在中心像素的上方、下方、左侧和右侧的像素处进行连接，后者意味着允许在中心像素周围的任意八个像素处进行连接。

再进一步说，对于非常大的二维数组，首先通过创建我们所谓的“图像金字塔”来减少搜索空间可能会有所帮助，这意味着逐渐缩小大小的数组堆栈：每个尺寸的1/2（根据需要填充），1/4，1/8 等。在缩小分辨率图像中可检测到的矩形是成为非常大的图像（或二维位数组）中最大矩形的良好候选对象。虽然这可能不是你考虑的最佳解决方案，但它具有可扩展性。自然需要做出一些努力，以确定缩放数组/图像的成本与在原始大图像中维护相对较大的候选矩形列表的成本之间的成本。

运行长度编码可能对你有帮助，特别是当你处理矩形而不是任意形状的连通分量时。运行长度编码会将每一行表示为0或1的拉伸或“运行长度”。这种技术在十年或二十年前用于加速连通分量算法，现在仍然是一个合理的方法。

无论如何，这不是对你问题最直接的答案，但我希望它能在某种程度上帮到你。

- Rethunk

1

@Rethunk- 感谢您如此详细的回答！ - questions

如果您可以限制矩形的大小，那么有一种非常酷的方法可以以O(small)的时间复杂度进行渲染，我认为还有一种不错的并行化方法。这里的“O(small)”指的是可能存在一些理论上精确确定时间的方法，但该方法允许使用一些有趣的大型数组，并且我没有费心去思考所有的约束条件。该方法实现起来可能有点棘手，但它是如此暴力，以至于令人发笑。 - Rethunk

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

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

- Nico Schertler · Accepted Answer

您所描述的算法类似于以下C代码：

//for each entry
for(int x = 0; x < width; ++x)
    for(int y = 0; y < height; ++y)
    {
        char lookFor = entries[x][y];
        int area = 0;
        for(int row = y; row < height; ++row)
        {
            if(entries[x, row] != lookFor)
                break;
            for(int col = x; col < width; ++col)
            {
                if(entries[col, row] != lookFor)
                    break;
                int currentArea = (col - x + 1) * (row - y + 1);
                if(currentArea > area)
                {
                    //save the current rect
                }
            }
        }
    }

有四个嵌套循环。外部循环将精确迭代n次（其中n为条目数）。内部循环平均将迭代f1 * width和f2 * height次（其中f1和f2为某个常数分数）。算法的其余部分需要恒定时间，并且不取决于问题规模。

因此，复杂度为O(n * f1 * width * f2 * height) = O(n^2)，这基本上意味着“访问每个条目并从那里再次访问每个条目”，无论是否真的需要检查所有条目或只是随问题规模增加的一些常数分数。

编辑

以上解释假设条目未随机分布，并且对于更大的区域，更有可能找到更大的同质子区域。如果不是这种情况，而内部循环的平均迭代次数根本不取决于区域大小（例如对于随机分布的条目），则结果时间复杂度为O(n)。