Comment trouver un nombre minimal de subdivisions

Question

Imaginez que vous avez une toile et que dans cette toile il y a déjà des objets. Comment pouvez-vous trouver la façon minimale de couvrir la zone "non couverte" avec des carrés, ne pas se superposer, remplissant complètement la toile. Dans mon cas, le "canvas" est un conteneur html-div et les objets sont des conteneurs div imbriqués. pourrait ressembler à ceci: http://www.encodechain.com/demo/200908_optimize.png A gauche, il y a le « start » et à droite il y a le possible premier « pas » ...

Je sais qu'il ya un algorithme pour cela, mais actuellement je ne me souviens pas le nom.

Answer 1

Le mieux que je pouvais trouver était cet article: Tiling a rectangle with the fewest squares. Le papier est une lecture intéressante, bien que parfois il plonge profondément dans le territoire de la théorie avec des «constantes universelles». Je ne suis pas certain que la question de "un rectangle de taille m par n soit carrelé de k carrés" est NP-complète. Comme indiqué dans une autre réponse, votre question ressemble à des problèmes d'emballage qui sont NP-complets. Et, bien sûr, votre problème est une généralisation de celui abordé dans ce document, puisque vous avez affaire à des zones non rectangulaires. Vous pourriez commencer par casser votre zone dans le nombre minimum de rectangles, un autre problème intéressant en soi. Et finalement, même si vous pouviez le faire de manière efficace, je ne suis pas sûr que le fait de paver ces rectangles de manière optimale aboutirait à un pavage globalement optimal.

Comme le note l'auteur, un algorithme glouton est un bon point de départ: il suffit de poser le plus grand carré possible jusqu'à ce que la zone soit pleine.

Answer 2

Packing Problem

Knapsack Problem

Et un article sur la résolution de problèmes d'emballage 2d