numero minimo di scatole di rivestimento per matrice binaria

Question

Ho una matrice binaria n m * (0 e 1.). Problema è quello di coprire tutti gli 1 con scatole non sovrapposti i cui elementi sono tutti 1.

Esempio:

1111
0110
0110

Box può essere rappresentare con coordinate e lunghezze in ogni (x,y,lx,ly) coordinate. Questo esempio è coperto con 2 scatole { (0,0,1,4), (1,1,2,2) }.

non vedo come trovare la copertura con un numero minimo di scatole.

Grazie

Answer 1

Questo problema si chiama partizione poliedro rettilinea. C'è una buona risposta su simile biziclop domanda ha scritto in un commento.

Idea dell'algoritmo è quello di ridurre al massimo problema corrispondenza di grafo bipartito (vertici sono possibili tagli.)

3D

Il mio problema originale era lo stesso argomento in 3D. Tale versione è dimostrato di essere NP-completo : - /

Dopo alcune ricerche, ho implementato una soluzione basata su euristico descritto nei documenti da Anuj Jain:

• partizionamento 3D Phantoms in omogenea parallelepipedi
• partizionamento Regioni 3D in parallelepipedi

Answer 2

Il mio dominio problema è chimica computazionale, e ci affrontando enormi problemi multivariata. Ci sono due algoritmi di ottimizzazione globale di casi generali che possono essere applicati qui che sono state anche applicate con successo a sistemi che contengono decine di migliaia di atomi:

a) algoritmi genetici
http://en.wikipedia.org/wiki/Genetic_algorithm

b) simulato ricottura
http://www.gnu.org/software/gsl/
ftp://ftp.alumni.caltech.edu/pub/ingber
http://www.taygeta.com/annealing/simanneal.html
http://www2.cs.uni-paderborn.de/ cs / ag-Monien / SOFTWARE / PARSA /
http://www.codeproject.com/KB/recipes/SimulatedAnnealing.aspx

Entrambi gli algoritmi sono ben rispettato le implementazioni di pubblico dominio e ben compreso le proprietà di ottimalità.