41

空のスペースに収まる最大の面積を持つ長方形を見つけるための最も効率的なアルゴリズムは何ですか？

画面が次のようになっているとしましょう（「＃」は塗りつぶされた領域を表します）：

....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............

考えられる解決策は次のとおりです。

....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...

通常、私は解決策を考え出すのを楽しんでいます。今回は自分で手探りで時間を無駄にしないようにしたいと思いますが、これは自分が取り組んでいるプロジェクトに実用的であるためです。よく知られている解決策はありますか？

Shog9は書いた：

入力は配列（他の応答によって暗示される）ですか、それとも任意のサイズの配置された長方形の形式のオクルージョンのリストですか（ウィンドウ位置を処理するときのウィンドウシステムの場合のように）？

はい、画面に配置された一連のウィンドウを追跡する構造があります。また、空か塗りつぶしかを問わず、各エッジ間のすべての領域と、左エッジまたは上端のピクセル位置を追跡するグリッドもあります。この特性を利用する修正された形式があると思います。何か知っていますか？

4

6 に答える 6

25

私は Dobb 博士の記事の著者であり、実装について時々尋ねられます。これはCの簡単なものです：

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int one;
  int two;
} Pair;

Pair best_ll = { 0, 0 };
Pair best_ur = { -1, -1 };
int best_area = 0;

int *c; /* Cache */
Pair *s; /* Stack */
int top = 0; /* Top of stack */

void push(int a, int b) {
  s[top].one = a;
  s[top].two = b;
  ++top;
}

void pop(int *a, int *b) {
  --top;
  *a = s[top].one;
  *b = s[top].two;
}


int M, N; /* Dimension of input; M is length of a row. */

void update_cache() {
  int m;
  char b;
  for (m = 0; m!=M; ++m) {
    scanf(" %c", &b);
    fprintf(stderr, " %c", b);
    if (b=='0') {
      c[m] = 0;
    } else { ++c[m]; }
  }
  fprintf(stderr, "\n");
}


int main() {
  int m, n;
  scanf("%d %d", &M, &N);
  fprintf(stderr, "Reading %dx%d array (1 row == %d elements)\n", M, N, M);
  c = (int*)malloc((M+1)*sizeof(int));
  s = (Pair*)malloc((M+1)*sizeof(Pair));
  for (m = 0; m!=M+1; ++m) { c[m] = s[m].one = s[m].two = 0; }
  /* Main algorithm: */
  for (n = 0; n!=N; ++n) {
    int open_width = 0;
    update_cache();
    for (m = 0; m!=M+1; ++m) {
      if (c[m]>open_width) { /* Open new rectangle? */
        push(m, open_width);
        open_width = c[m];
      } else /* "else" optional here */
      if (c[m]<open_width) { /* Close rectangle(s)? */
        int m0, w0, area;
        do {
          pop(&m0, &w0);
          area = open_width*(m-m0);
          if (area>best_area) {
            best_area = area;
            best_ll.one = m0; best_ll.two = n;
            best_ur.one = m-1; best_ur.two = n-open_width+1;
          }
          open_width = w0;
        } while (c[m]<open_width);
        open_width = c[m];
        if (open_width!=0) {
          push(m0, w0);
        }
      }
    }
  }
  fprintf(stderr, "The maximal rectangle has area %d.\n", best_area);
  fprintf(stderr, "Location: [col=%d, row=%d] to [col=%d, row=%d]\n",
                  best_ll.one+1, best_ll.two+1, best_ur.one+1, best_ur.two+1);
  return 0;
}

コンソールから入力を受け取ります。たとえば、このファイルをパイプすることができます:

16 12
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0
0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 0
0 0 0 0 1 1 * * * * * * 0 0 1 0
0 0 0 0 0 0 * * * * * * 0 0 1 0
0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 0
0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0

そして、その入力を印刷した後、出力します：

The maximal rectangle has area 12.
Location: [col=7, row=6] to [col=12, row=5]

上記の実装はもちろん派手なものではありませんが、Dr. Dobb の記事の説明に非常に近く、必要なものに簡単に変換できるはずです。

于 2013-11-18T02:20:58.353 に答える
21

@lassevk

DDJからの参照記事を見つけました：最大長方形の問題

于 2008-08-10T17:44:35.237 に答える
2

@lassevk

    // 4. Outer double-for-loop to consider all possible positions 
    //    for topleft corner. 
    for (int i=0; i < M; i++) {
      for (int j=0; j < N; j++) {

        // 2.1 With (i,j) as topleft, consider all possible bottom-right corners. 

        for (int a=i; a < M; a++) {
          for (int b=j; b < N; b++) {

HAHA ... O（m2 n2）..それはおそらく私が思いついたものです。

私は彼らが最適化を開発し続けているのを見ます...よさそうです、私は読みます。

于 2008-08-10T17:30:04.190 に答える