パズル：最大の長方形を見つける (最大長方形問題)
https://stackoverflow.com/questions/7245
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
空きスペースに収まる最大面積の長方形を見つけるための最も効率的なアルゴリズムは何ですか?
画面が次のようになっているとします (「#」は塗りつぶされた領域を表します)。
....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............
考えられる解決策は次のとおりです。
....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...
通常、私は解決策を見つけるのを楽しみます。ただし、これは私が取り組んでいるプロジェクトで実際に役立つため、今回は自分で手探りして時間を無駄にすることは避けたいと思っています。よく知られている解決策はありますか?
Shog9 書きました：
入力は配列 (他の回答で示唆されているように) ですか、それとも任意のサイズで配置された四角形の形式のオクルージョンのリスト (ウィンドウ位置を処理するウィンドウ システムの場合のように) ですか?
はい、画面上に配置された一連のウィンドウを追跡する構造があります。また、各エッジ間のすべての領域（空か塗りつぶしか）と、左端または上端のピクセル位置を追跡するグリッドもあります。この特性を利用する修正されたフォームがいくつかあると思います。何か知っていますか？
解決 2
@lassevk
DDJ からの参照記事を見つけました。 最大長方形問題
他のヒント
私はその博士の著者です。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 の記事は、必要なものに簡単に翻訳できるはずです。
ここにいくつかのコードと分析が含まれるページがあります。
特定の問題はページの少し下から始まります。ページ内でテキストを検索してください。 最大長方形問題.
http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module6/module6.html
@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++) {
ははは...O(m2 n2)..おそらくそれが私が思いついたものです。
彼らは最適化の開発を続けているようです...良さそうだね、読んでみるよ。
Dobbs のソリューションを Java で実装しました。
何も保証はありません。
package com.test;
import java.util.Stack;
public class Test {
public static void main(String[] args) {
boolean[][] test2 = new boolean[][] { new boolean[] { false, true, true, false },
new boolean[] { false, true, true, false }, new boolean[] { false, true, true, false },
new boolean[] { false, true, false, false } };
solution(test2);
}
private static class Point {
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int x;
public int y;
}
public static int[] updateCache(int[] cache, boolean[] matrixRow, int MaxX) {
for (int m = 0; m < MaxX; m++) {
if (!matrixRow[m]) {
cache[m] = 0;
} else {
cache[m]++;
}
}
return cache;
}
public static void solution(boolean[][] matrix) {
Point best_ll = new Point(0, 0);
Point best_ur = new Point(-1, -1);
int best_area = 0;
final int MaxX = matrix[0].length;
final int MaxY = matrix.length;
Stack<Point> stack = new Stack<Point>();
int[] cache = new int[MaxX + 1];
for (int m = 0; m != MaxX + 1; m++) {
cache[m] = 0;
}
for (int n = 0; n != MaxY; n++) {
int openWidth = 0;
cache = updateCache(cache, matrix[n], MaxX);
for (int m = 0; m != MaxX + 1; m++) {
if (cache[m] > openWidth) {
stack.push(new Point(m, openWidth));
openWidth = cache[m];
} else if (cache[m] < openWidth) {
int area;
Point p;
do {
p = stack.pop();
area = openWidth * (m - p.x);
if (area > best_area) {
best_area = area;
best_ll.x = p.x;
best_ll.y = n;
best_ur.x = m - 1;
best_ur.y = n - openWidth + 1;
}
openWidth = p.y;
} while (cache[m] < openWidth);
openWidth = cache[m];
if (openWidth != 0) {
stack.push(p);
}
}
}
}
System.out.printf("The maximal rectangle has area %d.\n", best_area);
System.out.printf("Location: [col=%d, row=%d] to [col=%d, row=%d]\n", best_ll.x + 1, best_ll.y + 1,
best_ur.x + 1, best_ur.y + 1);
}
}
非常に苦労した後、私はこのアルゴリズムを書きました...コードを見てください...
あなたはそれを理解しています。このコードは話します!!
import java.util.Scanner;
import java.util.Stack;
/**
* Created by BK on 05-08-2017.
*/
public class LargestRectangleUnderHistogram {
public static void main(String... args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] input = new int[n];
for (int j = 0; j < n; j++) {
input[j] = scanner.nextInt();
}
/*
* This is the procedure used for solving :
*
* Travel from first element to last element of the array
*
* If stack is empty add current element to stack
*
* If stack is not empty check for the top element of stack if
* it is smaller than the current element push into stack
*
* If it is larger than the current element pop the stack until we get an
* element smaller than the current element or until stack becomes empty
*
* After popping each element check if the stack is empty or not..
*
* If stack is empty it means that this is the smallest element encountered till now
*
* So we can multiply i with this element to get a big rectangle which is contributed by
*
* this
*
* If stack is not empty then check for individual areas(Not just one bar individual area means largest rectangle by this) (i-top)*input[top]
*
*
* */
/*
* Initializing the maxarea as we check each area with maxarea
*/
int maxarea = -1;
int i = 0;
Stack<Integer> stack = new Stack<>();
for (i = 0; i < input.length; i++) {
/*
* Pushing the element if stack is empty
* */
if (stack.isEmpty()) {
stack.push(i);
} else {
/*
* If stack top element is less than current element push
* */
if (input[stack.peek()] < input[i]) {
stack.push(i);
} else {
/*
* Else pop until we encounter an element smaller than this in stack or stack becomes empty
*
* */
while (!stack.isEmpty() && input[stack.peek()] > input[i]) {
int top = stack.pop();
/*
* If stack is empty means this is the smallest element encountered so far
*
* So we can multiply this with i
* */
if (stack.isEmpty()) {
maxarea = maxarea < (input[top] * i) ? (input[top] * i) : maxarea;
}
/*
* If stack is not empty we find areas of each individual rectangle
* Remember we are in while loop
*/
else {
maxarea = maxarea < (input[top] * (i - top)) ? (input[top] * (i - top)) : maxarea;
}
}
/*
* Finally pushing the current element to stack
* */
stack.push(i);
}
}
}
/*
* This is for checking if stack is not empty after looping the last element of input
*
* This happens if input is like this 4 5 6 1 2 3 4 5
*
* Here 2 3 4 5 remains in stack as they are always increasing and we never got
*
* a chance to pop them from stack by above process
*
* */
while (!stack.isEmpty()) {
int top = stack.pop();
maxarea = maxarea < (i - top) * input[top] ? (i - top) * input[top] : maxarea;
}
System.out.println(maxarea);
}
}
私はその著者です 最大長方形ソリューション LeetCode に基づいており、この回答はこれに基づいています。
スタックベースのソリューションについては他の回答ですでに説明されているため、最適なソリューションを紹介したいと思います。 O(NM) ユーザー起点の動的プログラミングソリューション モリシェン2008.
直感
次の手順を実行して、各点に対して長方形を計算するアルゴリズムを想像してください。
塗りつぶされた領域に到達するまで上向きに反復して、長方形の最大高さを見つけます。
長方形の最大高さに収まらない高さになるまで外側に向かって左右に反復して、長方形の最大幅を見つけます。
たとえば、黄色の点で定義された四角形を見つけます。
最大の長方形は、この方法で構築された長方形の 1 つである必要があることがわかります (最大の長方形の底面には、次の塗りつぶされた正方形が配置される点が必要です) 身長 その点以上）。
各ポイントに対して、いくつかの変数を定義します。
h - その点によって定義される長方形の高さ
l - その点によって定義される長方形の左境界
r - その点によって定義される長方形の右境界
これら 3 つの変数は、その点での四角形を一意に定義します。この長方形の面積は次のように計算できます。 h * (r - l). 。これらすべての領域の世界最大値が当社の結果です。
動的プログラミングを使用すると、 h, l, 、 そして r 前の行の各点の h, l, 、 そして r 線形時間の次の行のすべての点について。
アルゴリズム
指定された行 matrix[i], を追跡します。 h, l, 、 そして r 3 つの配列を定義することで、行内の各点を計算します - height, left, 、 そして right.
height[j] の高さに対応します matrix[i][j], 、その他の配列についても同様です。
ここで問題となるのは、各配列をどのように更新するかです。
height
h は、ポイントからの行内にある連続する塗りつぶされていないスペースの数として定義されます。新しいスペースがある場合は増分し、スペースが埋まる場合は 0 に設定します (空のスペースを示すには「1」を使用し、埋まったスペースには「0」を使用します)。
new_height[j] = old_height[j] + 1 if row[j] == '1' else 0
left:
長方形の左境界が変化する原因を考えてみましょう。現在の行より上の行に発生する塗りつぶされたスペースのすべてのインスタンスは、現在のバージョンの left, 、私たちに影響を与える唯一のものは、 left 現在の行に塗りつぶされたスペースがある場合です。
その結果、次のように定義できます。
new_left[j] = max(old_left[j], cur_left)
cur_left これは、これまでに遭遇した右端の塗りつぶされたスペースよりも 1 つ大きいです。長方形を左に「拡張」すると、その点を超えて拡張できないことがわかります。拡張しないと、塗りつぶされたスペースにぶつかってしまいます。
right:
ここで推論を再利用できます left そして以下を定義します:
new_right[j] = min(old_right[j], cur_right)
cur_right これは、これまでに遭遇した塗りつぶされたスペースの左端にあるものです。
実装
def maximalRectangle(matrix):
if not matrix: return 0
m = len(matrix)
n = len(matrix[0])
left = [0] * n # initialize left as the leftmost boundary possible
right = [n] * n # initialize right as the rightmost boundary possible
height = [0] * n
maxarea = 0
for i in range(m):
cur_left, cur_right = 0, n
# update height
for j in range(n):
if matrix[i][j] == '1': height[j] += 1
else: height[j] = 0
# update left
for j in range(n):
if matrix[i][j] == '1': left[j] = max(left[j], cur_left)
else:
left[j] = 0
cur_left = j + 1
# update right
for j in range(n-1, -1, -1):
if matrix[i][j] == '1': right[j] = min(right[j], cur_right)
else:
right[j] = n
cur_right = j
# update the area
for j in range(n):
maxarea = max(maxarea, height[j] * (right[j] - left[j]))
return maxarea
