19

エントリがすべて 0 または 1 の配列 M[1..m,1.. n] で表される mXn ビットマップが与えられたとします。すべて 1 のブロックは、M[i .. i0, j .. j0] で、すべてのビットが 1 に等しい. M 内のすべてが 1 で面積が最大のブロックを見つける効率の良いアルゴリズムを説明、解析してください。

動的プログラミング ソリューションを作成しようとしています。しかし、私の再帰アルゴリズムは 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各要素が最初の 0 までの 1 の数を表す配列を生成します。

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]。任意の位置で、スタック上の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)ます。

この例の 3 行目の実行例:

  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 だったので、 を押し(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

ここで、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 次元配列がある場合:

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

あなたはこれをします：

最初に a を追加します0:

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

ここで、 を押すたびに0、連続する一連のものがどこで終了するかがわかります。したがって、temp現在の 1 の数の現在の合計 (変数) を保持している場合は、その合計をそれまでの最大値 (変数) と比較してmax、ゼロに達したときに現在の合計をリセットできます。これにより、変数内の連続する 1 のシーケンスの最大長が得られます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)ます) ごとに、1 次元配列のアルゴリズムを適用して、その高さを持つ最大面積を持つものを見つけます ( 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 次元の問題に似ていることに注意してください。列を合計して、結果を見てみましょう。

1 2 2 2 0 1 0

ここで、問題は 1 次元のケースに縮小されますが、連続するj - i + 1(2この場合は) 値のサブシーケンスを見つけなければならないという例外があります。これは、j - i + 1「ウィンドウ」の各列が 1 でいっぱいでなければならないことを意味します。Sこれは、マトリックスを使用して効率的に確認できます。

どのように機能するかを理解するためSに、再び 1 次元のケースを考えてみましょう: let 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]です。2 番目のケースは、sfor each 列があることを除いて、同じように機能します。

ご不明な点がございましたら、お気軽にお問い合わせください。

これがあなたのニーズに合っているかどうかはわかりませんが、O(numLines*numCols)動的計画法に基づくアルゴリズムもあると思います。あなたが求めている部分配列が正方形の場合を除いて、私はまだそれを理解できません。ただし、誰かがより良い洞察を持っているかもしれないので、もう少し待ってください.

于 2010-09-27T19:21:29.107 に答える
1

A[i,j] に 2 つの値を格納する新しい行列 A を定義します: 左上隅が i,j である最大の部分行列の幅と高さで、この行列を右下隅から始めて下の行で埋めますトップに。[i,j]=1 で行列が与えられた場合にこれらのケースを実行します。

ケース 1: 元の行列の右隣または下隣の要素のいずれも現在の要素と等しくない、つまり: M[i,j] != M[i+1,j] および 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: 両方の隣接が等しい: 3 つの長方形が考慮されます。

  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])

上記の 3 つのケースで最大の面積を持つものは、この位置の長方形を表すと見なされます。

i,j に左上隅がある最大の行列のサイズは A[i,j].width*A[i,j].height であるため、A[i,j の計算中に見つかった最大値を更新できます。 ]

一番下の行と一番右の列の要素は、それぞれ下と右の隣接要素が異なっているかのように扱われます。

于 2014-07-15T05:11:03.633 に答える