Algorithme nécessaire pour l'emballage des rectangles de façon plutôt optimale

Question

Ive a obtenu un tas d'objets rectangulaires dont j'ai besoin pour emballer dans le plus petit espace possible (les dimensions de cet espace doivent être des puissances de deux).

Je suis au courant des diverses emballage des algorithmes qui vont emballer les objets aussi bien que possible dans un espace donné, mais dans ce cas j'ai besoin de l'algorithme pour déterminer comment grand que l'espace doit être aussi bien.

Par exemple dire que Ive a obtenu à la suite de rectangles

• 128*32
• 128*64
• 64*32
• 64*32

Ils peuvent être emballés dans un 128*128 espace

_________________
|128*32 |
|________________|
|128*64 |
| |
| |
|________________|
|64*32 |64*32 |
|_______|________|

Cependant, si il y avait également un 160*32 et un 64*64 celui qu'il aurait besoin d'un 256*128 espace

________________________________
|128*32 |64*64 |64*32 |
|________________| |_______|
|128*64 | |64*32 |
| |_______|_______|
| | |
|________________|___ |
|160*32 | |
|____________________|___________|

Quels algorithmes sont là-bas qui sont en mesure d'emballer un bouquet de rectangles et de déterminer la taille requise pour le conteneur (à une puissance de 2, et à l'intérieur d'une taille maximale pour chaque dimension)?

Answer 1

Voir cette page sur l'ARC de projet pour l'étude des solutions, il y a un compromis entre la complexité de mise en œuvre/du temps et de l'optimalité, mais il ya une large gamme d'algorithmes pour choisir de.

Voici un extrait des algorithmes:

1. Premier Ajustement de la Diminution de la Hauteur (FFDH) algorithme
   FFDH packs le prochain élément de R (non-augmentation de la hauteur) sur le premier niveau où R correspond. Si aucun niveau peut accueillir R, un nouveau niveau est créé.
   Le temps de la complexité de la FFDH: O(n·log n).
   Rapprochement ratio: FFDH(I)<=(17/10)·OPT(I)+1; asymptotique lié de 17/10 est serré.

2. La prochaine Ajustement de la Diminution de la Hauteur (NFDH) algorithme
   NFDH packs le prochain élément de R (non-augmentation de la hauteur) sur le niveau actuel si R s'adapte. Sinon, le niveau actuel est "fermé" et un nouveau niveau est créé.
   Le temps de la complexité: O(n·log n).
   Rapprochement ratio: NFDH(I) <= 2·OPT(I)+1; asymptotique lié de 2 est serré.

3. Meilleur Ajustement de la Diminution de la Hauteur (BFDH) algorithme
   BFDH packs le prochain élément de R (non-augmentation de la hauteur) sur le niveau, parmi ceux qui peuvent accueillir de R, pour lequel le résidu d'espace horizontal est le minimum. Si aucun niveau peut accueillir R, un nouveau niveau est créé.

4. En bas à Gauche (BL) Algorithme
   BL première commande d'articles par la non-augmentation de la largeur. BL packs de l'élément suivant au plus près de la bas car il convient et puis aussi proche de la gauche, comme il peut aller sans chevauchement avec tout emballés. Notez que les BL n'est pas un niveau orientée sur l'emballage de l'algorithme.
   Le temps de la complexité: O(n^2).
   Rapprochement ratio: BL(I) <= 3·OPT(I).

5. Baker Haut-Bas (UD) algorithme
   UD utilise une combinaison de BL et une généralisation de NFDH. La largeur de la bande et les éléments sont normalisées, de sorte que la bande est de largeur d'unité. UD commandes les éléments de non-augmentation de la largeur et divise ensuite les éléments en cinq groupes, chacun avec la largeur de la gamme (1/2, 1], (1/3,1/2], (1/4,1/3], (1/5,1/4], (0,1/5]. La bande est également divisé en cinq régions, R1, ··· , R5. Fondamentalement, certains éléments de la largeur de la plage (1/i+1, 1/i], pour 1 <= i <= 4, sont entassés dans la région Ri par BL. Depuis BL laisse un espace à l'augmentation de la largeur de haut en bas sur le côté droit de la bande de gaza, UD en profite par le premier emballage de l'élément Rj pour j = 1, ··· , 4 (dans l'ordre) du haut vers le bas. Si ce n'est pas l'espace, l'article est emballé à Ri par BL. Enfin, les éléments de la taille de la plupart 1/5 sont emballés à l'espace dans R1, ··· , R4 par l' (généralisée) NFDH algorithme. S'il n'y avait pas d'espace dans ces régions, l'article est emballé pour R5 à l'aide de NFDH.
   Rapprochement ratio: UD(I) <= (5/4) · OPT(I)+(53/8)H, où H est la hauteur maximale des éléments; l'asymptotique lié 5/4 est serré.

6. Inverse-fit (RF) de l'algorithme de
   RF normalise également la largeur de la bande et les objets de sorte que la bande est de largeur d'unité. RF d'abord les piles de tous les éléments de largeur supérieure à 1/2. Les autres éléments sont triés dans la non-augmentation de la hauteur et seront emballés au-dessus de la hauteur H0 atteint par les personnes de plus de 1/2. Ensuite RF répète le processus suivant. Grosso modo, RF packs éléments de gauche à droite avec leurs bas le long de la ligne de hauteur H0 jusqu'à ce qu'il n'y a plus de place. Puis packs éléments de droite à gauche et de bas en haut (appelé inverse de niveau) jusqu'à ce que la largeur totale est d'au moins 1/2. Alors l'inverse de niveau est tombé vers le bas jusqu'à (au moins) l'un d'eux touche un élément ci-dessous. La liste déroulante est d'une certaine manière répétée.
   Rapprochement ratio: RF(I) <= 2·OPT(I).

7. Steinberg algorithme
   Steinberg de l'algorithme, que l'on note M dans l'étude, les estimations de la limite supérieure de la hauteur H, nécessaires pour emballer tous les articles, tel qu'il a été prouvé que les éléments d'entrée peut être emballé dans un rectangle de largeur W et de hauteur H. Ils ont ensuite définir sept procédures (avec sept conditions), chacun de diviser un problème en deux plus petits et de les résoudre de manière récursive. Il a été montré que toute docile problème satisfait à l'une des sept conditions.
   Rapprochement ratio: M(I) <= 2·OPT(I).

8. Split-Ajustement de l'algorithme (SF) SF divise éléments en deux groupes, L1 avec une largeur de plus de 1/2 et L2 au plus 1/2. Tous les éléments de L1 sont d'abord emballé par la FFDH. Ensuite, ils sont disposés de sorte que tous les éléments avec une largeur de plus de 2/3 sont en dessous de celles avec une largeur à la plupart des 2/3. Cela crée un rectangle R de l'espace avec une largeur de 1/3. Les autres éléments de L2 sont ensuite conditionnés à la R et de l'espace au-dessus de ceux emballés avec de la L1 à l'aide de FFDH. Les niveaux créés dans R sont considérés comme inférieurs à ceux créés au-dessus de l'emballage de la L1.
   Rapprochement ratio: SF(I) <= (3/2) ·OPT(I) + 2; l'asymptotique lié de 3/2 est serré.

9. Sleator de l'algorithme de
   Sleater de l'algorithme se compose de quatre étapes:

   1. Tous les éléments de largeur supérieure à 1/2 sont emballés sur le dessus de l'un l'autre dans le bas de la bande. Supposons que h0 est la hauteur de la l'emballage de Tous leur emballage va se produire au-dessus de h0.

   2. Les autres éléments sont commandés par la non-augmentation de la hauteur. Un niveau d'objets sont emballés (non en augmentant la hauteur de l'ordre de la gauche vers la droite le long de la ligne de hauteur h0.

   3. Une ligne verticale est ensuite établi au moyen de couper la bande en deux moitiés égales (notez que cette ligne peut couper un élément qui est emballé en partie dans la moitié de droite). Dessinez deux horizontale des segments de ligne de la longueur de la moitié, de l'autre côté de la gauche de la moitié (appelé la gauche de la ligne de base) et une dans la moitié droite (qu'on appelle le droit de base) aussi bas que possible, de sorte que les deux lignes ne se croisent pas n'importe quel élément.

   4. Choisissez la gauche ou la droite ligne de base qui est d'une hauteur inférieure et pack un niveau d'éléments dans la moitié de la bande jusqu'à l'élément suivant est trop large.

   Une nouvelle ligne de base est formé à l'Étape (4) est répété sur le bas de la ligne de base jusqu'à ce que tous les articles sont emballés.
   Le temps de la complexité: O(n ·log n).
   Le rapprochement ratio de Sleator de l'algorithme est de 2,5 qui est serré.

Answer 2

Le rapide et sale de premier passage de la solution est toujours un excellent point de départ, car une comparaison si de rien d'autre.

Avide de placement de grand à petit.

Mettre le plus grand rectangle restant dans votre pique-zone. Si elle ne rentre pas n'importe où, la placer dans un lieu qui s'étend le pack de la région aussi peu que possible. Répétez jusqu'à ce que vous avez terminé avec le plus petit rectangle.

Il n'est pas parfait du tout, mais il est facile et une belle ligne de base. Il serait encore emballer votre exemple d'origine parfaitement, et vous donner un équivalent de réponse pour le deuxième.

Answer 3

Jetez un oeil à des problèmes d'emballage . Je pense que le tien tombe sous l'emballage de la poubelle 2D. Vous devriez être capable d'apprendre beaucoup de solutions à cela et d'autres problèmes d'emballage.

Voir aussi: Conditionnement des données d'image rectangulaires dans une texture carrée.

Answer 4

Il existe une vaste littérature sur ce problème. Une bonne gourmande heuristique est de placer les rectangles de surface la plus grande à la plus petite, dans la première position disponible vers le bas et à gauche du conteneur. Pensez à la gravité qui attire tous les objets dans le coin inférieur gauche. Pour une description de ce google "Chazelle en bas à gauche de l'emballage.

Pour des solutions optimales, l'état-de-la-art des techniques d'pack de plus de 20 rectangles en quelques secondes. Huang a un algorithme qui sépare le problème de trouver le plus petit joignant la boîte englobante de le problème de décider si oui ou non un ensemble de rectangle qui peuvent tenir dans une boîte englobante d'une taille spécifique. Vous donner à son programme un ensemble de rectangles, et il vous indique le plus petit joignant la boîte englobante nécessaire de les emballer.

Pour votre cas, votre boucle externe doit effectuer une itération à partir de la plus petite boîte englobante haussière (avec la largeur et la hauteur successivement à l'augmentation des puissances de deux). Pour chacune de ces boîtes englobantes, test pour voir si vous pouvez trouver un emballage pour votre rectangles. Vous obtiendrez un tas de "non-réponses", jusqu'à ce que la première réponse "oui", qui seront garantis pour être la solution optimale.

Pour la boucle interne de votre algorithme -- celui qui répond "oui" ou "non" pour une matrice de taille spécifique, je voudrais regarder le Huang de référence et de mettre en œuvre son algorithme. Il comprend un grand nombre d'optimisations sur le dessus de l'algorithme de base, mais vous ne vraiment besoin de la viande et des pommes de terre. Puisque vous voulez gérer les rotations, à chaque point de branchement au cours de votre recherche, essayez simplement de deux rotations et de revenir en arrière lorsque les deux rotations n'aboutissent pas à une solution.

Answer 5

Je suis à peu près certain qu'il s'agit d' un problème NP-complet , donc, pour une solution optimale, vous devez implémenter un algorithme de retour arrière qui essaie toutes les combinaisons possibles.

Les bonnes nouvelles sont qu'en raison de la nécessité d'emballer des rectangles 2D dans un espace 2D limité, vous pouvez élaguer beaucoup de possibilités au début, donc ce n'est peut-être pas si mal.