スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




長方形探索: 最大長方形の面積 Largest Rectangle

2008.03.28 20:47  動的計画法

長方形探索

n × n のマス目のそれぞれに 1 または 0 が記してあり、その中から 1 だけから成る最大の長方形の面積を求めて下さい。

これは前に考えた正方形探索の応用で、今回は最大の長方形を探します。この問題も正方形探索で用いたアルゴリズムを応用して動的計画法で解くことができますが、正方形探索ほど単純な式では解決できません。左上角から右下角に向かって個々の要素を計算していく過程で、既に計算された左と上の要素を利用していきますが、長方形探索の場合、W[i][j] の値はそこから左上方向に向かってできる正方形の辺の長さではなく、そこから左上方向に向かってできる全ての長方形の情報を記録する必要があります。このアルゴリズムの詳しい解説が、プログラム・プロムナードに掲載されています。このアルゴリズムは、現在の要素を求めるために重複を避けながら左と上の要素をマージしたりと、プログラムがやや複雑になります。

ここでは、先に考えたヒストグラム内の最大長方形の面積を求めるアルゴリズムを応用したアルゴリズムを示します。このアルゴリズムは上記の正方形探索を応用したアルゴリズムよりもプログラムが簡単になるだけでなく、より効率の良いアルゴリズムです。アルゴリズムはいたって簡単で、まず各要素について上に向かって 1 が何個連続しているかを示すテーブル T を作ります。次に、T の各行をヒストグラムの入力と見なしヒストグラムの最大長方形の面積を求めるアルゴリズムを適用します。

最大長方形


001 #include<stdio.h>
002 #include<iostream>
003 #include<stack>
004 #include<algorithm>
005 #define MAX 105
006 #define BLOCK 0
007 
008 using namespace std;
009 
010 struct Rectangle{ int height;  int pos; };
011 
012 int getLargestRectangle( int size, int buffer[]){
013     stack<Rectangle> S;
014     int maxv = 0;
015     buffer[size] = 0;
016     
017     for ( int i = 0; i <= size; i++ ){
018         Rectangle rect;
019         rect.height = buffer[i];
020         rect.pos = i;
021         if ( S.empty() ){
022             S.push( rect );
023         } else {
024             if ( S.top().height < rect.height ){
025                 S.push( rect );
026             } else if ( S.top().height > rect.height ) {
027                 int target = i;
028                 while ( !S.empty() && S.top().height >= rect.height){
029                     Rectangle pre = S.top(); S.pop();
030                     int area = pre.height * (i - pre.pos);
031                     maxv = max( maxv, area);
032                     target = pre.pos;
033                 }
034                 rect.pos = target;
035                 S.push(rect);
036             }
037         }
038     }
039     return maxv;
040 }
041 
042 int size;
043 int buffer[MAX][MAX];
044 int T[MAX][MAX];
045 
046 int getLargestRectangle(){
047     for ( int i = 0; i < size; i++ ){
048         for ( int j = 0; j < size; j++ ){
049             T[i][j] = 0;
050         }
051     }
052     
053     for ( int j = 0; j < size; j++ ){
054         int sequence = 0;
055         for ( int i = 0; i < size; i++ ){
056             if ( buffer[i][j] == BLOCK ){
057                 sequence = T[i][j] = 0;
058             } else {
059                 T[i][j] = ++sequence;
060             }
061         }
062     }
063     
064     int maxv = 0;
065     for ( int i = 0; i < size; i++ ){
066         maxv = max( maxv, getLargestRectangle( size, T[i] ) );
067     }
068     
069     return maxv;
070 }
071 
072 int main(void){
073     while( cin >> size, size ){
074         for ( int i = 0; i < size; i++ ){
075             for ( int j = 0; j < size; j++ ){
076                 cin >> buffer[i][j];
077             }
078         }
079         cout << getLargestRectangle() << " ";
080     }
081     
082     return 0;
083 }

n 行についてO(n)の計算量なので、これはO(n2)のアルゴリズムとなります。



スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




ヒストグラム中の最大の長方形の面積

2008.03.04 21:14  動的計画法

ヒストグラム中の最大の長方形の面積


データの離散型分布を表すヒストグラム(柱状グラフ)は、長方形を共通の基線上に並べた多角形として描画されます。これらの長方形は同じ幅を持ちますが、異なる高さのものを含みます。ヒストグラムを表す多角形に含まれる最大の長方形の面積を求めて下さい。入力は各データに対応する長方形の高さの列に対応した n 個の要素からなる1次元配列とします。(source: ACM/ICPC University of Ulm Local Contest)

以下のように、2重ループによって長方形の範囲を選び、そこにできる最大の長方形の面積を計算して更新していけば、全体での最大の面積を求めることができます。これはO(n2)のアルゴリズムです。



001 int getRectangleAreaBF( int size, int buffer[] ){
002 int maxv = 0;
003 for ( int i = 0; i < size; i++ ){
004 for ( int j = i; j < size; j++ ){
005 int minh = INT_MAX;
006 for ( int k = i; k <= j; k++ ){
007 minh = min( minh, buffer[k] );
008 }
009 maxv = max( maxv, minh*(j-i+1));
010 }
011 }
012 return maxv;
013 }



この問題は動的計画法を用いればO(n)のアルゴリズムで解くことができます。この解法は後で考える長方形探索などに応用することができるので重要です。

このアルゴリズムは部分問題の"未解決の"解をスタックに記憶していく、やや巧妙なテクニックを用います。スタックには、長方形の情報を記録します。各長方形は長方形の高さ height とその左端の位置 pos の情報を持たせます。まずスタックを空にし、ヒストグラムの各長方形 rect を左から右へ(i が 0 から n-1 まで)向かって順番に以下の処理を行います。


  1. スタックが空の場合:
      スタックに rect を追加する

  2. スタックの頂点にある長方形の高さが rect の高さより低い場合:
      スタックに rect を追加する

  3. スタックの頂点にある長方形の高さが rect の高さと等しい場合: 
      何もしない

  4. スタックの頂点にある長方形の高さが rect の高さより高い場合:

    • スタックが空でなく、スタックの頂点にある長方形の高さが rect の高さ以上である限り、スタックから長方形を取り出し、その面積を計算し最大値を更新する。長方形の横の長さは現在の位置 i と記録されている左端の位置 pos から計算できる。
    • スタックに rect を追加する。ただし、rect の左端の位置 pos は最後にスタックから取り出した長方形の pos の値とする




以下にアルゴリズムの流れを示します。位置 i におけるスタックには (i - 1) を右端としてできる未完成の長方形のリストが記録されます。図の 1 に示すように最初の5ステップでスタックには4つの未完成の長方形のリストが記録されます。

スタックの応用


図の 2 で6番目のデータである高さ 2 の長方形を追加します。ここから図の 3,4,5 で、2 よりも高い長方形をスタックから順番に取り出し面積を計算します。最後に取り出された高さ 3 の長方形の位置は 1 なので、この現在追加しようとしている高さ 2 の長方形の位置を 1 とします。この時点でスタックには高さ 1 と 2 の未完成の長方形が記録されています。

以下はPOJの解答プログラムです。



001 // pku 2559 (Largest Rectangle in a Histogram)
002 // O(n) algorithm
003 #include<stdio.h>
004 #include<iostream>
005 #include<stack>
006 #include<algorithm>
007 #define MAX 110000
008 typedef long long llong;
009
010 using namespace std;
011
012 struct Rectangle{ llong height; int pos; };
013
014 llong getRectangleArea( int size, llong buffer[]){
015 stack<Rectangle> S;
016 llong maxv = 0;
017 buffer[size] = 0;
018
019 for ( int i = 0; i <= size; i++ ){
020 Rectangle rect;
021 rect.height = buffer[i];
022 rect.pos = i;
023 if ( S.empty() ){
024 S.push( rect );
025 } else {
026 if ( S.top().height < rect.height ){
027 S.push( rect );
028 } else if ( S.top().height > rect.height ) {
029 int target = i;
030 while ( !S.empty() && S.top().height >= rect.height){
031 Rectangle pre = S.top(); S.pop();
032 llong area = pre.height * (i - pre.pos);
033 maxv = max( maxv, area);
034 target = pre.pos;
035 }
036 rect.pos = target;
037 S.push(rect);
038 }
039 }
040 }
041
042 return maxv;
043 }
044
045 main(){
046 int size;
047 llong buffer[MAX+1];
048
049 while(1){
050 scanf("%d", &size);
051 if ( size == 0 ) break;
052 for ( int i = 0; i < size; i++ ) scanf("%lld", &buffer[i]);
053 cout << getRectangleArea( size, buffer ) << endl;
054 }
055 }





テーマ : プログラミング - ジャンル : コンピュータ

| コメント(2) | トラックバック(0) | ↑ページトップ |




最大正方形の面積 正方形探索

2008.03.03 15:40  動的計画法

最大正方形


縦に n 行、横に n 列並べられた n × n のタイルがあります。いくつかのタイルには印(汚れ)が着いています。印のついていない(綺麗な)タイルだけから成るような最大の正方形の辺の長さを求めて下さい。各タイルの大きさは 1 × 1 メートルとします。

力任せのアルゴリズム

タイルの数が小さければこの問題は以下に示すループの入れ子で解くことができます。

  • 2重ループによって候補となる正方形の左上角(i, j)を決める

  • ループによって(i,j)から右下方向にできる正方形の幅 width を決める

  • 2重ループによって決められた範囲が正方形であるかチェックし、そうならば maxWidth を更新する



  • 正方形探索


    このアルゴリズムを実装すると以下のようになります。プログラムが5重ループになるので、O(n5) のアルゴリズムとなります。



    001 int size;
    002 char G[MAX][MAX];
    003
    004 int getLargestSquareBF(){
    005 int maxWidth = 0;
    006 for ( int i = 0; i < size; i++ ){
    007 for ( int j = 0; j < size; j++ ){
    008 for ( int width = 1; width <= size - max(i, j); width++ ){
    009 bool isSquare = true;
    010 for ( int a = i; a < i + width; a++ ){
    011 for ( int b = j; b < j + width; b++ ){
    012 if ( G[a][b] == BLOCK ) {
    013 isSquare = false;
    014 break;
    015 }
    016 }
    017 if ( !isSquare ) break;
    018 }
    019 if ( isSquare ) maxWidth = max( maxWidth, width );
    020 else break;
    021 }
    022 }
    023 }
    024 return maxWidth;
    025 }




    このアルゴリズムは n × n のタイル上の全ての正方形を見落とすことなく調べます。しかし明らかに無駄な処理が発生します。プログラムで break しているように印がついたタイルを見つけた時点でチェックする処理を終了させ次の候補の処理に移る、というようにアルゴリズムを改善したとしても、与えられたタイルのほとんどに印が着いていない場合には上記改善も意味がなく、O(n5)のアルゴリズムに変わりはありません。


    動的計画法による解法

    この問題は動的計画法を用いればO(n2)のアルゴリズムで解くことができます。

    データ
    W[i][j] が (i, j) から左上に向かってできる最大の正方形の辺の長さ(タイルの数)、というような配列 W を用意します。

    初期化
    上端と左端のタイル(i, j が 0 の場所にあるタイル)について
    T[i][j] に印が着いているならば、 W[i][j] = 0
    そうでなければ、W[i][j] = 1 とします。

    処理
    i, j > 0 について
    W[i][j] の値は、W[i-1][j-1], W[i-1][j], W[i][j-1] のうち一番小さい値に 1 を加えたものになります。例えば、下図の局面においては、左隣、左上隣、上隣の要素のうち最小の値は 2 です。これは、現在の位置を右下とした正方形の辺の長さは 2 + 1 より大きくすることはできないことを示しています。

    正方形探索


    計算が左→右、上→下の順に流れていくので、W[i][j] を計算するとき左隣、左上隣、上隣の要素の値はすでに計算済みなので、これらの解を利用することができます。このアルゴリズムを実装すると以下のようになります。プログラムが2重ループになるので、O(n2) のアルゴリズムとなります。



    001 int size;
    002 char G[MAX][MAX];
    003
    004 int getLargestSquare(){
    005 int W[MAX][MAX];
    006
    007 for ( int i = 0; i < size; i++ ) {
    008 W[0][i] = (G[0][i] == BLOCK) ? 0 : 1;
    009 W[i][0] = (G[i][0] == BLOCK) ? 0 : 1;
    010 }
    011
    012 int maxWidth = 0;
    013 for ( int i = 1; i < size; i++ ){
    014 for ( int j = 1; j < size; j++ ){
    015 if ( G[i][j] == BLOCK ) {
    016 W[i][j] = 0;
    017 } else {
    018 W[i][j] = min(W[i-1][j-1], min(W[i-1][j], W[i][j-1])) + 1;
    019 maxWidth = max( maxWidth, W[i][j] );
    020 }
    021 }
    022 }
    023
    024 return maxWidth;
    025 }


    テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。