5

NxM 0-1 マトリックスと数値 K(<=NxM) を指定すると、そのサブ四角形の内部に少なくとも K 1 がある、その 0-1 マトリックスの最小のサブ四角形領域を見つける必要があるという異常な問題に遭遇しました。さらに、その面積 (両方の次元の積) を最小化する必要があります。

例:
00000
01010
00100
01010
00000
K = 3

したがって、内部に 3 つの 1 を含む最小領域 6 のサブ長方形を見つけることができます。
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)) です。

ネストされた 2 つのループは、線形検索を二分検索に変更することで最適化できます (細いサブ長方形をより高速に処理するため)。

また、（行/列をサブ長方形に追加した後）、このサブ長方形の面積が面積より大きくならないように、列/行の数を 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) です。

'l' によるループは、内部で処理されたすべてのサブ長方形が単一列のサブ長方形である (行が多すぎる) 場合、または内部で処理されたサブ長方形に十分な「1」が含まれていない (行が不足している) 場合に終了する可能性があります。 ）。

于 2012-07-24T13:39:32.330 に答える
0

この問題は、クリーク決定問題をNP 困難に還元できるため、 NP 困難です。したがって、可能性のあるすべての部分行列を試す力ずくのアプローチよりも効率的なアルゴリズムはありません (P=NP を除く)。

クリーク決定問題は、次の方法で問題に還元できます。

  • 行列をグラフの隣接行列とします。
  • K=L^2 と設定します。ここで、L は探しているクリークのサイズです。
  • この入力で問題を解決してください。問題の解が 1 のみを含む LxL サブマトリックスである場合、グラフには L クリークが含まれます (これは多項式時間で確認できます)。
于 2012-07-24T12:34:41.260 に答える
0

頭のてっぺんから、マトリックス内のすべての 1 の座標ペア (?) のリストを作成し、それらの中から各 K 組み合わせの (最小の) 含まれるサブ四角形を見つけて、それらの中で最小のものを選ぶことができます*。 .

* これは、K 組み合わせの最小および最大の行インデックスと列インデックスによって定義されます。

于 2012-07-24T12:53:36.273 に答える