Puzzle:Trova il rettangolo più grande (problema del rettangolo massimale)
https://stackoverflow.com/questions/7245
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Qual è l'algoritmo più efficiente per trovare il rettangolo con l'area più grande che possa stare nello spazio vuoto?
Supponiamo che lo schermo assomigli a questo ('#' rappresenta l'area piena):
....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............
Una soluzione probabile è:
....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...
Normalmente mi piacerebbe trovare una soluzione.Anche se questa volta vorrei evitare di perdere tempo armeggiare da solo, dato che ha un uso pratico per un progetto a cui sto lavorando.Esiste una soluzione conosciuta?
Shog9 ha scritto:
Il tuo input è un array (come implicito nelle altre risposte) o un elenco di occlusioni sotto forma di rettangoli posizionati di dimensioni arbitrarie (come potrebbe essere il caso in un sistema a finestre quando si ha a che fare con le posizioni delle finestre)?
Sì, ho una struttura che tiene traccia di una serie di finestre posizionate sullo schermo.Ho anche una griglia che tiene traccia di tutte le aree tra ciascun bordo, siano esse vuote o piene, e la posizione dei pixel del bordo sinistro o superiore.Penso che ci sia qualche forma modificata che trarrebbe vantaggio da questa proprietà.Ne conosci qualcuno?
Soluzione 2
@lassevk
Ho trovato l'articolo di riferimento, da DDJ: Il problema del rettangolo massimo
Altri suggerimenti
Sono l'autore di quel Dr.L'articolo di Dobb e occasionalmente mi viene chiesto informazioni su un'implementazione.Eccone uno semplice in 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;
}
Prende il suo input dalla console.Potresti ad es.inviaci questo file:
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
E dopo aver stampato il suo input, verrà restituito:
The maximal rectangle has area 12.
Location: [col=7, row=6] to [col=12, row=5]
L'implementazione di cui sopra ovviamente non è niente di speciale, ma è molto vicina alla spiegazione nel Dr.Dobb e dovrebbe essere facile da tradurre in qualsiasi cosa sia necessaria.
Ecco una pagina che contiene del codice e alcune analisi.
Il tuo problema particolare inizia un po' più in basso nella pagina, cerca il testo nella pagina problema del rettangolo massimale.
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++) {
AHAHA...O(m2n2)..Probabilmente è quello che mi sarebbe venuto in mente.
Vedo che continuano a sviluppare ottimizzazioni...sembra buono, lo leggerò.
Ho implementato la soluzione di Dobbs in Java.
Nessuna garanzia per nulla.
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);
}
}
Dopo aver lottato così tanto, ho scritto questo algoritmo... Basta vedere il codice...
Lo capisci. Questo codice parla!!
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);
}
}
Sono l'autore del Soluzione del rettangolo massimale su LeetCode, su cui si basa questa risposta.
Poiché la soluzione basata sullo stack è già stata discussa nelle altre risposte, vorrei presentarne una ottimale O(NM) soluzione di programmazione dinamica che proviene dall'utente morrischen2008.
Intuizione
Immagina un algoritmo in cui per ogni punto calcoliamo un rettangolo facendo quanto segue:
Trovare l'altezza massima del rettangolo scorrendo verso l'alto fino a raggiungere un'area piena
Trovare la larghezza massima del rettangolo eseguendo l'iterazione verso sinistra e destra fino a un'altezza che non può contenere l'altezza massima del rettangolo
Ad esempio trovando il rettangolo definito dal punto giallo:
Sappiamo che il rettangolo massimo deve essere uno dei rettangoli costruiti in questo modo (il rettangolo massimo deve avere un punto sulla base dove si trova il successivo quadrato riempito altezza sopra quel punto).
Per ogni punto definiamo alcune variabili:
h - l'altezza del rettangolo definito da quel punto
l - il limite sinistro del rettangolo definito da quel punto
r - il limite destro del rettangolo definito da quel punto
Queste tre variabili definiscono in modo univoco il rettangolo in quel punto.Possiamo calcolare l'area di questo rettangolo con h * (r - l).Il massimo globale di tutte queste aree è il nostro risultato.
Usando la programmazione dinamica, possiamo usare il file h, l, E r di ogni punto nella riga precedente per calcolare il h, l, E r per ogni punto della riga successiva in tempo lineare.
Algoritmo
Riga data matrix[i], teniamo traccia del h, l, E r di ogni punto della riga definendo tre array - height, left, E right.
height[j] corrisponderà all'altezza di matrix[i][j], e così via con gli altri array.
La domanda ora diventa come aggiornare ciascun array.
height
h è definito come il numero di spazi vuoti continui in una linea dal nostro punto.Incrementiamo se c'è un nuovo spazio e lo impostiamo a zero se lo spazio è pieno (stiamo usando '1' per indicare uno spazio vuoto e '0' come pieno).
new_height[j] = old_height[j] + 1 if row[j] == '1' else 0
left:
Considera cosa causa le modifiche al limite sinistro del nostro rettangolo.Poiché tutte le istanze di spazi riempiti presenti nella riga sopra quella corrente sono già state prese in considerazione nella versione corrente di left, l'unica cosa che riguarda il nostro left è se incontriamo uno spazio pieno nella nostra riga corrente.
Di conseguenza possiamo definire:
new_left[j] = max(old_left[j], cur_left)
cur_left è uno spazio più grande dello spazio riempito più a destra che abbiamo incontrato.Quando "espandiamo" il rettangolo a sinistra, sappiamo che non può espandersi oltre quel punto, altrimenti finirà nello spazio pieno.
right:
Qui possiamo riutilizzare il nostro ragionamento left e definire:
new_right[j] = min(old_right[j], cur_right)
cur_right è l'occorrenza più a sinistra di uno spazio pieno che abbiamo incontrato.
Implementazione
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
