Puzzle:Trouver le plus grand rectangle (problème du rectangle maximum)
https://stackoverflow.com/questions/7245
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Quel est l'algorithme le plus efficace pour trouver le rectangle avec la plus grande surface qui rentre dans l'espace vide ?
Disons que l'écran ressemble à ceci (« # » représente la zone remplie) :
....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............
Une solution probable est :
....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...
Normalement, j'apprécierais trouver une solution.Même si cette fois, j'aimerais éviter de perdre du temps à tâtonner seul, car cela a une utilité pratique pour un projet sur lequel je travaille.Existe-t-il une solution connue ?
Shog9 a écrit:
Votre entrée est-elle un tableau (comme l'impliquent les autres réponses) ou une liste d'occlusions sous la forme de rectangles positionnés de taille arbitraire (comme cela pourrait être le cas dans un système de fenêtrage lorsqu'il s'agit de positions de fenêtre) ?
Oui, j'ai une structure qui garde la trace d'un ensemble de fenêtres placées sur l'écran.J'ai également une grille qui garde une trace de toutes les zones entre chaque bord, qu'elles soient vides ou remplies, ainsi que la position des pixels de leur bord gauche ou supérieur.Je pense qu'il existe une forme modifiée qui profiterait de cette propriété.En connaissez-vous ?
La solution 2
@lassevk
J'ai trouvé l'article référencé, de DDJ : Le problème du rectangle maximal
Autres conseils
Je suis l'auteur de ce Dr.Dobb et on vous pose parfois des questions sur une implémentation.En voici un simple en 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;
}
Il prend son entrée depuis la console.Vous pourriez par ex.dirigez-y ce fichier :
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
Et après avoir imprimé son entrée, il affichera :
The maximal rectangle has area 12.
Location: [col=7, row=6] to [col=12, row=5]
L'implémentation ci-dessus n'a rien d'extraordinaire bien sûr, mais elle est très proche de l'explication du Dr.L'article de Dobb devrait être facile à traduire selon les besoins.
Voici une page qui contient du code et des analyses.
Votre problème particulier commence un peu plus bas sur la page, recherchez le texte dans la page problème du rectangle maximal.
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++) {
HAHA...O(m2n2)..C'est probablement ce que j'aurais trouvé.
Je vois qu'ils continuent à développer des optimisations...ça a l'air bien, je vais le lire.
J'ai implémenté la solution de Dobbs en Java.
Aucune garantie pour quoi que ce soit.
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);
}
}
Après avoir tant lutté, j'ai écrit cet algorithme... Il suffit de voir le code...
Vous l'avez compris. Ce code parle !!
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);
}
}
Je suis l'auteur du Solution du rectangle maximal sur LeetCode, sur lequel est basée cette réponse.
Puisque la solution basée sur la pile a déjà été abordée dans les autres réponses, je voudrais présenter une solution optimale O(NM) solution de programmation dynamique qui provient de l'utilisateur morrischen2008.
Intuition
Imaginez un algorithme dans lequel, pour chaque point, nous calculons un rectangle en procédant comme suit :
Trouver la hauteur maximale du rectangle en itérant vers le haut jusqu'à ce qu'une zone remplie soit atteinte
Trouver la largeur maximale du rectangle en itérant vers l'extérieur à gauche et à droite jusqu'à une hauteur qui ne correspond pas à la hauteur maximale du rectangle
Par exemple trouver le rectangle défini par le point jaune :
Nous savons que le rectangle maximum doit être l'un des rectangles construits de cette manière (le rectangle maximum doit avoir un point sur sa base où se trouve le prochain carré rempli). hauteur au-dessus de ce point).
Pour chaque point nous définissons quelques variables :
h - la hauteur du rectangle défini par ce point
l - la limite gauche du rectangle défini par ce point
r - la limite droite du rectangle défini par ce point
Ces trois variables définissent de manière unique le rectangle à ce stade.On peut calculer l'aire de ce rectangle avec h * (r - l).Le maximum global de tous ces domaines est notre résultat.
En utilisant la programmation dynamique, nous pouvons utiliser le h, l, et r de chaque point de la ligne précédente pour calculer le h, l, et r pour chaque point de la ligne suivante en temps linéaire.
Algorithme
Ligne donnée matrix[i], nous suivons h, l, et r de chaque point de la ligne en définissant trois tableaux - height, left, et right.
height[j] correspondra à la hauteur de matrix[i][j], et ainsi de suite avec les autres tableaux.
La question est maintenant de savoir comment mettre à jour chaque tableau.
height
h est défini comme le nombre d'espaces continus non remplis dans une ligne à partir de notre point.Nous incrémentons s'il y a un nouvel espace et le mettons à zéro si l'espace est rempli (nous utilisons « 1 » pour indiquer un espace vide et « 0 » pour un espace rempli).
new_height[j] = old_height[j] + 1 if row[j] == '1' else 0
left:
Considérez ce qui provoque des modifications dans la limite gauche de notre rectangle.Étant donné que toutes les instances d'espaces remplis apparaissant dans la ligne au-dessus de la ligne actuelle ont déjà été prises en compte dans la version actuelle de left, la seule chose qui affecte notre left c'est si nous rencontrons un espace rempli dans notre ligne actuelle.
On peut ainsi définir :
new_left[j] = max(old_left[j], cur_left)
cur_left est un espace rempli plus grand que l’extrême droite que nous avons rencontré.Lorsque nous « développons » le rectangle vers la gauche, nous savons qu’il ne peut pas s’étendre au-delà de ce point, sinon il s’étendra dans l’espace rempli.
right:
Ici, nous pouvons réutiliser notre raisonnement dans left et définir :
new_right[j] = min(old_right[j], cur_right)
cur_right est l'occurrence la plus à gauche d'un espace rempli que nous avons rencontré.
Mise en œuvre
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
