41

1 と 0 でいっぱいの巨大なファイルで、1 の最大の正方形を見つける必要があります。動的計画法を使用する必要があることはわかっています。私はそれを2D配列に格納しています。最大の正方形を見つけるためのアルゴリズムの助けは素晴らしいでしょう、ありがとう!

入力例:

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

答え：

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

これまでの私のコード:

int Square (Sq[int x][int y]) {
   if (Sq[x][y]) == 0) {
       return 0;
   }
   else {
       return 1+MIN( Sq(X-1,Y), Sq(X,Y-1), Sq(X-1,Y-1) );
   }
}

(すでに配列に値が入力されていると仮定します)

int main() {
    int Sq[5][6]; //5,6 = bottom right conner
    int X = Square(Sq[5][6]);
}

そこからどうやって行くの？

4

7 に答える 7

81

ソリューションのスケッチは次のとおりです。

セルごとに、そのセルを左上として使用して正方形を作成できる大きさのカウンターを保持します。明らかに、0のすべてのセルのカウントは0になります。

右下のセルから繰り返しを開始し、左下に移動してから、1行上に移動して繰り返します。

各スキャンでこれを行います：

  1. セルに0が割り当てられている場合count=0
  2. セルに1があり、エッジセル（下端または右端のみ）の場合は、count=1
  3. 他のすべてのセルについては、その右、右下、および下のセルの数を確認してください。それらの最小値を取り、1を加算して、それをカウントに割り当てます。max_countこれまでの最大カウントを追跡するためにグローバル変数を保持します。

マトリックスのトラバースが終了するmax_countと、は目的の値になります。

複雑さは、マトリックスのトラバースのコスト以上のものではありません。

これは、トラバーサル後のマトリックスの外観です。括弧内の値はカウントです。つまり、左上のセルを使用して作成できる最大の正方形です。

1(1) 0(0) 1(1) 0(0) 1(1) 0(0)
1(1) 0(0) 1(4) 1(3) 1(2) 1(1)
0(0) 1(1) 1(3) 1(3) 1(2) 1(1)
0(0) 0(0) 1(2) 1(2) 1(2) 1(1)
1(1) 1(1) 1(1) 1(1) 1(1) 1(1)

Pythonでの実装

def max_size(mat, ZERO=0):
    """Find the largest square of ZERO's in the matrix `mat`."""
    nrows, ncols = len(mat), (len(mat[0]) if mat else 0)
    if not (nrows and ncols): return 0 # empty matrix or rows
    counts = [[0]*ncols for _ in xrange(nrows)]
    for i in reversed(xrange(nrows)):     # for each row
        assert len(mat[i]) == ncols # matrix must be rectangular
        for j in reversed(xrange(ncols)): # for each element in the row
            if mat[i][j] != ZERO:
                counts[i][j] = (1 + min(
                    counts[i][j+1],  # east
                    counts[i+1][j],  # south
                    counts[i+1][j+1] # south-east
                    )) if i < (nrows - 1) and j < (ncols - 1) else 1 # edges
    return max(c for rows in counts for c in rows)
于 2009-11-13T02:03:40.617 に答える
8

LSBRA(X,Y)「X、Y に右下がある最大の正方形」を意味します

擬似コード:

LSBRA(X,Y):
   if (x,y) == 0:
       0
   else:
       1+MIN( LSBRA(X-1,Y), LSBRA(X,Y-1), LSBRA(X-1,Y-1) )

(エッジ セルの場合、MIN 部分をスキップして、(x,y) が 0 でない場合は 1 を返すことができます。)

次のように、「波」でグリッドを斜めに作業します。

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 2 3 4 5 6
2 | 3 4 5 6 7
3 | 4 5 6 7 8

または、端のセルを埋める限り、左から右、上から下に作業します。

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 6 7 8 9 .
2 | . . . . .
3 | . . . . .

そうすれば、必要なデータを以前に計算していない計算に遭遇することはありません。したがって、すべてのLSBRA()「呼び出し」は、実際には以前の計算結果のテーブル ルックアップにすぎません (したがって、動的プログラミングの側面)。

機能する理由

X、Y に右下がある正方形を作成するには、他の 3 つのコーナーのそれぞれに接する 1 つ少ない次元の重なり合う正方形が含まれている必要があります。言い換えれば、持つこと

XXXX
XXXX
XXXX
XXXX

あなたも持っている必要があります...

XXX.    .XXX    ....    ....
XXX.    .XXX    XXX.    ....
XXX.    .XXX    XXX.    ....
....    ....    XXX.    ...X

これらの 3 つ (LSBRA チェックのそれぞれ) の N サイズの正方形と現在の正方形も「占有」されている限り、(N+1) サイズの正方形ができます。

于 2009-11-13T02:05:28.883 に答える
3

私の頭に浮かぶ最初のアルゴリズムは次のとおりです。

  1. '&&' column / row 1 with column / row 2 if、つまり、各エントリと他の列/行の対応するエントリの間で'&&'操作を実行します。
  2. 結果の列を確認します。長さが21の場合は、2x2の正方形に当たることを意味します。
  3. そして、最初の2つの結果を含む次の列。長さが31の場合、3x3の正方形にヒットします。
  4. すべての列が使用されるまで繰り返します。
  5. 列2から1〜4を繰り返します。

実装は非常に単純で、問題は宿題のように聞こえるので、ここでは説明しません。さらに、入力が非常に大きい場合は遅くなるため、これを行うにははるかに効率的な方法があります。

于 2009-11-13T01:56:53.320 に答える
2

入力行列を次のようにしますM：nxm

T[i][j]は、直角下の正方形を持つ最大の正方形の辺を含むDP行列(i,j)です。

テーブルを埋めるための一般的なルール：

if (M[i][j] == 1) {
  int v = min(T[i][j-1], T[i-1][j]);
  v = min(v, T[i-1][j-1]);
  T[i][j] = v + 1;
}
else 
  T[i][j] = 0;

結果の正方形のサイズは、の最大値ですT。

充填T[i][0]とT[0][j]些細なことです。

このアルゴリズムを巨大なファイルに使用できるかどうかはわかりませんが、行列全体を保存する必要はなくT、現在の行と前の行のみを保存する必要があります。

次のメモは、一般的な考え方を理解するのに役立ちます。

  • サイズsの右下角（i-1、j）、（i、j-1）、（i-1、j-1）のすべての正方形は、サイズsの右下角（i、j）の正方形の内側にあります。 +1。
  • （i、j）に右下隅のサイズs + 1の正方形がある場合、右下の角度（i-1、j）、（i、j-1）、（i-1）の最大正方形のサイズj-1）は少なくともsです。
  • 反対も真実です。（i-1、j）、（i、j-1）、（i-1、j-1）で直角が下にある少なくとも1つの正方形のサイズがsより小さい場合、右下隅にある正方形のサイズat（i、j）はs+1より大きくすることはできません。
于 2009-11-13T02:03:18.340 に答える
1

OK、最も非効率的な方法ですが、単純な方法は次のとおりです。

  1. 最初の項目を選択します。1かどうかを確認し、そうであれば1x1の正方形を使用します。

  2. 下の1つと右の1つをチェックし、1の場合は、行2の列2をチェックし、1の場合は2x2の正方形をチェックします。

  3. 行3の列1、列2、列3に加えて、行1の列3、行2の列3、1、3x3を確認します。

  4. したがって、基本的には、行と列を一緒に展開し続け、境界内のすべてのセルをチェックします。0を打つとすぐに壊れるので、1点続けて移動し、やり直します。

  5. 行の終わりで、次の行に移動します。

  6. 終わりまで。

おそらく、それらがwhileループなどにどのように適合するか、および&&sを使用して0をチェックする方法を確認できます。また、それを見ると、どのように高速化できるかにも気付くでしょう。しかし、他の答えが今述べたように、それは宿題のように聞こえるので、実際のコードはあなたに任せます。

幸運を！

于 2009-11-13T02:02:02.353 に答える
0

N を 2D 配列内のセルの量とします。すべての最大の空の四角形をリストする非常に効率的なアルゴリズムが存在します。最大の空の四角形は、これらの空の四角形の 1 つの内部にあり、最大の空の四角形のリストが計算されれば、それを見つけるのは簡単です。このようなリストを作成するための O(N) アルゴリズムを示す論文は、www.ulg.ac.be/telecom/rectanglesにあります。ソース コードと同様に (最適化されていません)。最大の空の四角形の数が N で制限されるという証明が存在することに注意してください (論文を参照)。したがって、最大の空の四角形の選択は O(N) で実行でき、全体的な方法も O(N) です。実際には、この方法は非常に高速です。コード全体が C で 40 行を超えてはならないため、実装は非常に簡単です (すべての最大の空の四角形をリストするアルゴリズムには、C で約 30 行かかります)。

于 2013-07-07T21:38:38.720 に答える