5

我遇到了一个普通问题，给定一个 NxM 0-1 矩阵和一个数字 K(<=NxM)，我必须找到该 0-1 矩阵的最小子矩形区域，该子矩形内至少有 K 1 个。此外，它的面积（两个维度的乘积）应该最小化。

例如：
00000
01010
00100
01010
00000
K = 3

所以我可以找到一个最小面积为 6 的子矩形，其中包含 3 个 1。
10
01
10

请注意，我的意思是目标子矩形应该包含来自原始 0-1 矩阵的连续行数和列数。

4

3 回答 3

3 
Compute cumulative sum of rows R[i,j] and columns C[i,j].
For top-left corner (i,j) of each possible sub-rectangle:
   Starting from a single-row sub-rectangle (n=i),
   Search the last possible column for this sub-rectangle (m).
   While m>=j:
     While there are more than 'k' "ones" in this sub-rectangle:
       If this is the smallest sub-rectangle so far, remember it.
       Remove column (--m).
       This decreases the number of "ones" by C[m+1,n]-C[m+1,j-1].
     Add next row (++n).
     This increases the number of "ones" by R[m,n]-R[i-1,n].

时间复杂度为 O(NM(N+M))。

可以通过将线性搜索更改为二分搜索来优化两个嵌套循环（以更快地处理细长的子矩形）。

也有可能（在向子矩形添加一行/一列之后）在 O(1) 时间内减少列/行的数量，使得该子矩形的面积不大于该面积迄今为止最好的子矩形。

这两种优化都需要计算 O(1) 中的任何子矩形权重。为此，请预先计算子矩形 [1..i,1..j] (X[i,j]) 的所有元素的累积总和。然后任何子矩形 [i..m,j..n] 的权重计算为X[m,n]-X[i-1,n]-X[m,j-1]+X[i-1,j-1]。

Compute cumulative sum of columns C[i,j].
For any starting row (k) of possible sub-rectangle:
  For any ending row (l) of possible sub-rectangle:
    Starting column (m = 1).
    Ending column (n = 1).
    While n is not out-of-bounds
      While there are less than 'k' "ones" in sub-rectangle [k..l,m..n]:
        Add column (++n).
        This increases the number of "ones" by C[l,n]-C[k-1,n].
      If this is the smallest sub-rectangle so far, remember it.
      Remove column (++m).
      This decreases the number of "ones" by C[l,m-1]-C[k-1,m-1].

时间复杂度为 O(N 2 M)。

当在其中处理的所有子矩形都是单列子矩形（行太多）或在其中处理的子矩形没有包含足够的“1”时（行数不足），“l”循环可能会终止）。

于 2012-07-24T13:39:32.330 回答
0

这个问题是NP 难的，因为可以将集团决策问题简化为它。因此，没有比尝试所有可能的子矩阵的蛮力方法更有效的算法（除非 P=NP）。

可以通过以下方式将集团决策问题简化为您的问题：

  • 令矩阵为图的邻接矩阵。
  • 设置 K=L^2，其中 L 是我们要查找的团的大小。
  • 在这个输入上解决你的问题。该图包含一个 L-clique ，如果您的问题的解决方案是一个仅包含一个的 LxL 子矩阵（可以在多项式时间内检查）。
于 2012-07-24T12:34:41.260 回答
0

在我的脑海中，您可以列出矩阵中所有坐标对（？），找到其中每个 K 组合的（最小）包含子矩形*，然后选择其中最小的.

* 由 K 组合中的最小和最大行和列索引定义。

于 2012-07-24T12:53:36.273 回答