Anar al contingut

Empaquetat de rectànguls

De L'Enciclopèdia, la wikipedia en valencià

L'empaquetat de rectànguls és un problema d'empaquetat a on l'objectiu és determinar si un conjunt determinat de rectànguls chicotets es pot colocar dins d'un polígon gran determinat, de modo que no se superponguen dos rectànguls menuts. S'han estudiat distintes variants d'este problema.

Empaquetar rectànguls idèntics en un rectàngul

En esta variant, hi ha vàries unitats d'un únic rectàngul de tamany (lxw) i un rectàngul de tamany més gran (LxW). L'objectiu és empaquetar tants rectànguls chicotets com siga possible en el rectàngul gran sense superposició entre els rectànguls menuts. Restriccions comunes del problema inclouen llimitar la rotació dels rectànguls chicotets a múltiples de 90° i exigir que cada rectàngul chicotet siga ortogonal sobre el rectàngul gran.

Este problema té algunes aplicacions, com la càrrega de caixes sobre pallets i, en concret, l'estiba de polpa de celulosa. Com a eixemple d'un resultat en este camp, és possible empaquetar 147 rectànguls chicotets de tamany (137x95) en un rectàngul gran de tamany (1600x1230).[1]

Empaquetar quadrats idèntics en un polígon rectilíneu

Donat un polígon rectilíneu (els costats del qual es troben en ànguls rectes) R en el pla, un conjunt S de punts en R i un conjunt de quadrats idèntics, l'objectiu és trobar el major número de quadrats no superposts que es poden empaquetar en punts de S.

Suponga's que, per a cada punt p en S, es coloca un quadrat centrat en p. Siga GS el graf d'intersecció d'estos quadrats. Un embalage quadrat equival a un conjunt independent en GS. Trobar l'empaquetament quadrat més gran és NP-difícil; es pot provar açò reduint la qüestió a un problema de satisfactibilitat booleana.[2]

Referències

  1. ↑ Birgin, I G; Lobato, R D; Morabit, R(2010).«An effective recursive partitioning approach for the packing of identical rectangles in a rectangle».Journal of the Operational Research Society.61(2): 306–320.doi:10.1057/jors.2008.141.
  2. ↑ Fowler, Robert J.; Paterson, Michael S.; Tanimoto, Steven L.(1981-06-13).«Optimal packing and covering in the plane llaure NP-complete».Information Processing Letters.12(3): 133–137.ISSN 0020-0190.doi:10.1016/0020-0190(81)90111-3.(en en)