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 1 1 1

解は次のようになります:
1 1 1 0
0 1 0 0
0 0 0
0 1 1 1

ブルート フォース アルゴリズムをいくつか試してみましたが、n > 20 の場合は遅すぎます。この問題をどのように解決すればよいか教えていただけますか?

RBerteig が提案したように、この問題は次のように説明することもできます。

4

3 に答える 3

3

ブルートフォースは、適切に実装されていれば、ここでは n < 100 で問題なく動作するはずです。以下のソリューションは、O(n^4) 時間と O(n^2) メモリの複雑さを持ちます。10^8 演算は、最新の PC では 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

したがって、 sub-rectangle 内の 1 の数を含むtableが必要sumsです。 このテーブルは 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一度に1ステップずつグリッドを横切って長方形を移動し、長方形内になくなったビットのカウントを減らし、新しく長方形に入ったビットのカウントを増やすことができます。これを長方形のサイズの変更と組み合わせて、長方形の移動とサイズ変更に最適なパターンを見つけようとする可能性があります。

于 2010-09-12T21:42:08.683 に答える
0

ほんの少しのヒント..

値に対してより適切な制限を課すことができます。要件は条件につながる

N1*(k+1) == S*k、ここでN1は領域内の 1 の数であり、S=dx*dyはその表面です。より良い形に書き直すことができます：

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

nとの最大公約数n+1は常に 1 であるため、とN1の倍数である必要があります。解の可能なスペースを大幅に削減します。 が大きいほど良いです ( の素約数で遊ぶ必要がある場合)。kdx*dyk+1kdx*dyk+1

ここで、このようなプロパティを持つ最大の領域の表面だけが必要なので、最大の領域から始めて小さな領域に移動するのが賢明です。dx*dy除数と境界条件を満足するfrom n^2downtoを試す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 に答える