Minimal couvrant nombre de boîtes à matrice binaire

Question

I ai une matrice binaire à n * m (0 et de 1). Le problème est de couvrir tous des 1 avec des boîtes qui ne se chevauchent dont les éléments sont tous 1.

Exemple:

1111
0110
0110

Box peut être représenter avec les coordonnées et les longueurs dans chaque coordonnée (x,y,lx,ly). Cet exemple est recouvert de 2 boîtes { (0,0,1,4), (1,1,2,2) }.

Je cherche comment trouver la couverture avec le nombre minimal de cases.

Merci

Answer 1

Ce problème est appelé partition de polyèdre rectiligne. Il y a une bonne réponse sur biziclop question similaire a écrit dans un commentaire.

Idée de l'algorithme est de réduire au problème correspondant au maximum graphe biparti (sommets sont des coupes possibles.)

3D

Mon problème initial était même sujet en 3D. Cette version est présentée comme NP-complet : - /

Après quelques recherches, je mis en œuvre une solution basée sur heuristique décrite dans les documents par Anuj Jain:

• Cloisonnement Phantoms 3D dans Homogène Cuboïdes
• Partitionnement Régions 3D dans Cuboïdes

Answer 2

Mon domaine de problème est la chimie computationnelle, et nous abordons d'énormes problèmes à plusieurs variables. Il y a deux cas général des algorithmes d'optimisation globale qui peuvent être appliquées ici qui ont également été appliquées avec succès aux systèmes contenant des dizaines de milliers d'atomes:

a) algorithmes génétiques
http://en.wikipedia.org/wiki/Genetic_algorithm

b) le recuit simulé
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 / LOGICIEL / PARSA /
http://www.codeproject.com/KB/recipes/SimulatedAnnealing.aspx

Les deux algorithmes ont bien respecté les mises en œuvre dans le domaine public et bien compris les propriétés d'optimalité.