4

我在描述用于查找二进制数据的最大矩形区域的算法时遇到问题，其中 1 出现的频率比 0 多 k 倍。数据总是这样的 n^2 位：

例如，n = 4 的数据如下所示：

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

k 的值可以是 1 .. j（k = 1 表示 0 和 1 的数量相等）。

对于上述数据示例和 k = 1 的解决方案是：

1 0 1 0 <- 4 x '0' 和 4 x '1'
0 0 1 1
0 1 1 1
1 1 0 1

但在这个例子中：
1 1 1 0
0 1 0 0
0 0 0 0
0 1 1 1

解决方案是：
1 1 1 0
0 1 0 0
0 0 0 0
0 1 1 1

我尝试了一些蛮力算法，但是对于 n > 20，它变得太慢了。你能告诉我应该如何解决这个问题吗？

正如 RBerteig 所提出的 - 问题也可以这样描述：“在一个给定的正方形位图中，通过某个任意过程将单元格设置为 1 或 0，找到 1 和 0 以指定比率 k 出现的最大矩形区域。”

4

3 回答 3

3

如果实施得当，Bruteforce 在 n < 100 的情况下应该做得很好：下面的解决方案具有 O(n^4) 时间和 O(n^2) 内存复杂度。在现代 PC 上，10^8 次操作应该远低于 1 秒（特别是考虑到每个操作都非常便宜：加法和减法很少）。

一些观察

  1. 有 O(n^4) 个子矩形需要考虑，每个子矩形都可以是一个解决方案。
  2. 如果我们能在 O(1)（恒定时间）内找到每个子矩形中 1 和 0 的数量，我们将在 O(n^4) 时间内解决问题。
  3. 如果我们知道某个子矩形中 1 的数量，我们可以找到零的数量（通过区域）。

因此，问题简化为：创建数据结构，允许在恒定时间内找到每个子矩形中 1 的数量。

现在，假设我们有 sub-rectangle [i0..i1]x[j0..j1]。即，它占据 i0 和 i1 之间的行和 j0 和 j1 之间的列。并让count_ones函数计算子矩形中 1 的个数。

这是主要的观察：

count_ones([i0..i1]x[j0..j1]) = count_ones([0..i1]x[0..j1]) - count_ones([0..i0 - 1]x[0..j1]) - count_ones([0..i1]x[0..j0 - 1]) + count_ones([0..i0 - 1]x[0..j0 - 1])

与实际示例相同的观察结果：

AAAABBB
AAAABBB
CCCCDDD
CCCCDDD
CCCCDDD
CCCCDDD

如果我们需要在 D 子矩形 (3x4) 中找到 1 的数量，我们可以通过在整个矩形 (A + B + C + D) 中取 1 的数量，减去 (A + B) 中的 1 的数量来完成矩形，在 (A + C) 矩形中减去 1 的数量，并在 (A) 矩形中添加 1 的数量。(A + B + C + D) - (A + B) - (A + C) + (A) = D

因此，我们需要 table ，sums对于每个包含多个 1 的 sub-rectangle 。 您可以在 O(n^2) 中创建此表，但即使是直接填充它的方法（对于每个并迭代区域的所有元素）也将是 O(n^4)。ij[0..i][0..j]
ij[0..i][0..j]

有了这张桌子，

count_ones([i0..i1]x[j0..j1]) = sums[i1][j1] - sums[i0 - 1][j1] - sums[i1][j0 - 1] + sums[i0 - 1][j0 - 1]

因此，时间复杂度达到了 O(n^4)。

于 2010-09-12T21:53:28.783 回答
2

这仍然是蛮力，但您应该注意的是，您不必从头开始重新计算新i*j矩形的所有内容。相反，对于每个可能的矩形大小，您可以一次将矩形移过n*n网格，减少不再在矩形内的位的计数，并增加新进入矩形的位的计数。您可以将其与改变矩形大小结合起来，并尝试找到移动和调整矩形大小的最佳模式。

于 2010-09-12T21:42:08.683 回答
0

只是一些提示..

您可以对值施加更好的限制。需求导致条件

N1*(k+1) == S*k，其中N1是一个区域的个数，S=dx*dy是它的表面。它可以用更好的形式重写：

N1/k == S/(k+1).

因为数字的最大公约数n和n+1总是 1，所以N1必须是 的倍数k和dx*dy是 的倍数k+1。它大大减少了解决方案的可能空间，越大k越好（dx*dy如果您需要使用 的主要除数k+1）。

现在，因为您只需要具有此类属性的最大区域的表面，所以从最大区域开始并移至较小区域是明智的。通过dx*dy从满足n^2除数k+1和边界条件的向下尝试，您会发现解决方案非常快，比 O(n^4) 快得多，因为一个特殊的原因：除非数组是专门构造的，如果我们假设一个随机输入，在具有表面的区域中存在N1超出S值的概率将随着 的减少而不断增长。（较大的值将使概率更小，但同时它们会使过滤器和对更强）。(n-dx+1)*(n-dy+1)SSkdxdy

另外，这个问题： http: //ioinformatics.org/locations/ioi99/contest/land/land.shtml，看起来有点相似，也许你会在他们的解决方案中找到一些想法。

于 2010-09-14T05:31:51.307 回答