algoritmo per trovare il numero minimo di rettangoli che coprono alcuni elementi di un array 2D

Question

semplificato, devo risolvere il seguente problema:

Si dispone di un array a 2 dimensioni pieno di 0 e 1. Trova il numero minimo di rettangoli in modo che coprano tutti gli 1s. I rettangoli non dovrebbero sovrapporsi.

La firma della funzione potrebbe essere simile: List<Rectangle> FindCoveringRectangles(bool[,] array)

ho già una soluzione che è "abbastanza buono", ma non sempre trovare il numero minimo di rettangoli. Mi piacerebbe sapere se esiste un algoritmo ben noto ed efficiente che può essere applicato per risolvere questo problema?

Esempio:

Un array di ingresso:

.......... 
.1.....11. 
.......11. 
...111.... 
...111.... 
...111.... 
....1111.. 
....1111.. 
......11.. 
.......... 

(0s sostituiti da punti di leggibilità)

potrebbe comportare seguenti rettangoli:

(2,2,2,2), 
(2,8,3,9), 
(4,4,6,6), 
(7,5,8,8), 
(9,7,9,8) 

(all'inizio , sinistra, in basso, a destra), 1-based

Ci può essere più di una soluzione, ma una è sufficiente.

Answer 1

Questo è un problema di corrispondenza di un tipo che avrebbe potuto facilmente mostrare NP-difficile. Tuttavia sembra che ci sia in realtà una soluzione molto veloce!

Utilizzando un fill-in bfs è possibile trovare ciascun componente collegato, O(n). Quindi wlog possiamo supporre che dobbiamo solo riempire un'area collegata.

Se l'area non ha buchi in essa, è possibile utilizzare l'algoritmo descritto in this paper (o here on google scholar.)

Un O (n log log n) algoritmo viene proposto per rettangolare minimamente partizionamento di un semplice poligono rettilineo. Per ogni semplice poligono rettilineo P, una coppia visibile al vertice-bordo è un vertice e un bordo che può essere collegato da un segmento di linea orizzontale o verticale che giace interamente all'interno di P. Viene mostrato che, se le coppie visibili di vertice-bordo sono trovate , la corrispondenza massima e l'insieme indipendente massimo del grafico bipartito derivato dagli accordi di un semplice poligono rettilineo possono essere trovati nel tempo lineare senza costruire il grafico bipartito. Utilizzando questo algoritmo, il problema di minimo partizione per poligoni rettilinei convessi e verticalmente (orizzontalmente) convessi poligoni rettilinei possono essere risolti in O (n)

Alcuni degli articoli di cui a coprire anche il caso di una zona con fori . Questi si eseguono in O (n^(3/2) logn), ma continuano a cucire abbastanza bene.

In alternativa, una cosa che si potrebbe fare è risolvere il problema senza buchi, risolvere il problema per ogni buca e quindi sottrarre. Questo potrebbe non dare una soluzione ottimale, ma manterrebbe il runtime.

Si potrebbe anche provare a suddividere la forma nelle sue diverse parti topologiche, ma probabilmente verrebbe eseguita in modo esponenziale nel numero di fori.

In terzo luogo, è possibile provare ad adattare l'algoritmo proposto per il caso più generale, ma potrebbe essere difficile.