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.Numero minimo di caselle di copertura per matrice binaria
Esempio:
1111
0110
0110
Box può essere rappresentare con coordinate e lunghezze in ogni coordinata (x,y,lx,ly). Questo esempio è coperto con 2 caselle { (0,0,1,4), (1,1,2,2) }.
Sto cercando come trovare la copertura con il numero minimo di scatole.
Grazie
Questo problema è chiamato partizione di poliedro rettilineo. C'è un buon answer su una domanda simile biziclop pubblicata in un commento.
idea di algoritmo è quello di ridurre al problema la massima 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-complete: -/
Dopo alcune ricerche, ho implementato una soluzione basata su euristico descritto nei documenti da Anuj Jain:
Il mio problema è di dominio chimica computazionale, e ci siamo affrontare enormi problemi multivariata. Ci sono due algoritmi di ottimizzazione globale casi generale che possono essere applicati qui che sono anche stati applicati con successo a sistemi contenenti decine di migliaia di atomi:
a) algoritmi genetici
http://en.wikipedia.org/wiki/Genetic_algorithm
b) Simulated Annealing
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 hanno implementazioni di dominio pubblico ben rispettate e proprietà di ottimalità ben comprese.
Sono le scatole permesso di sovrapporsi? –
@Jeff: per il problema specificato, non si otterrebbe alcun vantaggio dalla sovrapposizione. –
Potrebbe risultare utile: http://stackoverflow.com/questions/4701887/find-the-set-of-largest-contiguous-rectangles-to-cover-multiple-areas/4701966#4701966 – biziclop