fc2ブログ



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

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) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ