Rompecabezas:Encuentra el rectángulo más grande (problema del rectángulo máximo)
https://stackoverflow.com/questions/7245
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cuál es el algoritmo más eficiente para encontrar el rectángulo con el área más grande que quepa en el espacio vacío?
Digamos que la pantalla se ve así ('#' representa el área llena):
....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............
Una solución probable es:
....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...
Normalmente disfrutaría encontrando una solución.Aunque esta vez me gustaría evitar perder el tiempo dando vueltas por mi cuenta ya que esto tiene un uso práctico para un proyecto en el que estoy trabajando.¿Existe una solución conocida?
shog9 escribió:
¿Su entrada es una matriz (como lo implican las otras respuestas), o una lista de oclusiones en forma de rectángulos colocados de tamaño arbitrario (como podría ser el caso en un sistema de ventanas cuando se trata de posiciones de ventanas)?
Sí, tengo una estructura que realiza un seguimiento de un conjunto de ventanas colocadas en la pantalla.También tengo una cuadrícula que realiza un seguimiento de todas las áreas entre cada borde, ya sea que estén vacías o llenas, y la posición de los píxeles de su borde izquierdo o superior.Creo que hay alguna forma modificada que aprovecharía esta propiedad.¿Sabes de alguno?
Solución 2
@lassevk
Encontré el artículo al que se hace referencia, de DDJ: El problema del rectángulo máximo
Otros consejos
Soy el autor de ese Dr.El artículo de Dobb y ocasionalmente me preguntan sobre una implementación.Aquí hay uno 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;
}
Toma su entrada de la consola.Podrías, p.canalice este archivo a él:
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
Y después de imprimir su entrada, generará:
The maximal rectangle has area 12.
Location: [col=7, row=6] to [col=12, row=5]
La implementación anterior no es nada especial, por supuesto, pero se acerca mucho a la explicación del Dr.El artículo de Dobb debería ser fácil de traducir a lo que sea necesario.
Aquí hay una página que tiene algo de código y algunos análisis.
Su problema particular comienza un poco más abajo en la página, busque el texto en la página problema del rectángulo máximo.
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++) {
JA JA...O(m2n2)..Probablemente eso es lo que se me habría ocurrido.
Veo que continúan desarrollando optimizaciones...Se ve bien, lo leeré.
Implementé la solución de Dobbs en Java.
No hay garantía de nada.
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);
}
}
Después de luchar tanto, escribí este algoritmo... Solo mira el código...
Lo entiendes. ¡¡Este código habla !!
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);
}
}
soy el autor del Solución del rectángulo máximo en LeetCode, que es en lo que se basa esta respuesta.
Dado que la solución basada en pila ya se analizó en las otras respuestas, me gustaría presentar una solución óptima O(NM) solución de programación dinámica que se origina en el usuario morrischen2008.
Intuición
Imagine un algoritmo en el que para cada punto calculamos un rectángulo haciendo lo siguiente:
Encontrar la altura máxima del rectángulo iterando hacia arriba hasta alcanzar un área rellena
Encontrar el ancho máximo del rectángulo iterando hacia afuera de izquierda a derecha hasta una altura que no se adapta a la altura máxima del rectángulo
Por ejemplo, encontrar el rectángulo definido por el punto amarillo:
Sabemos que el rectángulo máximo debe ser uno de los rectángulos construidos de esta manera (el rectángulo máximo debe tener un punto en su base donde está el siguiente cuadrado relleno). altura por encima de ese punto).
Para cada punto definimos algunas variables:
h - la altura del rectángulo definido por ese punto
l - el límite izquierdo del rectángulo definido por ese punto
r - el límite derecho del rectángulo definido por ese punto
Estas tres variables definen de forma única el rectángulo en ese punto.Podemos calcular el área de este rectángulo con h * (r - l).El máximo global de todas estas áreas es nuestro resultado.
Usando programación dinámica, podemos usar el h, l, y r de cada punto en la fila anterior para calcular el h, l, y r para cada punto de la siguiente fila en tiempo lineal.
Algoritmo
fila dada matrix[i], hacemos un seguimiento de la h, l, y r de cada punto en la fila definiendo tres matrices - height, left, y right.
height[j] corresponderá a la altura de matrix[i][j], y así sucesivamente con las otras matrices.
La pregunta ahora es cómo actualizar cada matriz.
height
h se define como el número de espacios continuos sin llenar en una línea desde nuestro punto.Incrementamos si hay un espacio nuevo y lo establecemos en cero si el espacio está lleno (estamos usando '1' para indicar un espacio vacío y '0' como uno lleno).
new_height[j] = old_height[j] + 1 if row[j] == '1' else 0
left:
Considere las causas de los cambios en el límite izquierdo de nuestro rectángulo.Dado que todas las instancias de espacios llenos que aparecen en la fila encima de la actual ya se han incluido en la versión actual de left, lo único que afecta a nuestra left es si encontramos un espacio lleno en nuestra fila actual.
Como resultado podemos definir:
new_left[j] = max(old_left[j], cur_left)
cur_left es uno mayor que el espacio lleno más a la derecha que hemos encontrado.Cuando "expandimos" el rectángulo hacia la izquierda, sabemos que no puede expandirse más allá de ese punto; de lo contrario, llegará al espacio lleno.
right:
Aquí podemos reutilizar nuestro razonamiento en left y definir:
new_right[j] = min(old_right[j], cur_right)
cur_right es la aparición más a la izquierda de un espacio lleno que hemos encontrado.
Implementación
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
