Empaquetado de rectángulos

De Wikipedia, la enciclopedia libre

El empaquetado de rectángulos es un problema de empaquetado donde el objetivo es determinar si un conjunto determinado de rectángulos pequeños se puede colocar dentro de un polígono grande determinado, de modo que no se superpongan dos rectángulos pequeños. Se han estudiado distintas variantes de este problema.

Empaquetar rectángulos idénticos en un rectángulo[editar]

En esta variante, hay varias unidades de un único rectángulo de tamaño (lxw) y un rectángulo de tamaño más grande (LxW). El objetivo es empaquetar tantos rectángulos pequeños como sea posible en el rectángulo grande sin superposición entre los rectángulos pequeños. Restricciones comunes del problema incluyen limitar la rotación de los rectángulos pequeños a múltiplos de 90° y exigir que cada rectángulo pequeño sea ortogonal con respecto al rectángulo grande.

Este problema tiene algunas aplicaciones, como la carga de cajas sobre pallets y, en concreto, la estiba de pulpa de celulosa. Como ejemplo de un resultado en este campo, es posible empaquetar 147 rectángulos pequeños de tamaño (137x95) en un rectángulo grande de tamaño (1600x1230).[1]​

Empaquetar cuadrados idénticos en un polígono rectilíneo[editar]

Dado un polígono rectilíneo (cuyos lados se encuentran en ángulos rectos) R en el plano, un conjunto S de puntos en R y un conjunto de cuadrados idénticos, el objetivo es encontrar el mayor número de cuadrados no superpuestos que se pueden empaquetar en puntos de S.

Supóngase que, para cada punto p en S, se coloca un cuadrado centrado en p. Sea GS el grafo de intersección de estos cuadrados. Un embalaje cuadrado equivale a un conjunto independiente en GS. Encontrar el empaquetamiento cuadrado más grande es NP-difícil; se puede probar esto reduciendo la cuestión a un problema de satisfacibilidad booleana.[2]​

Empaquetar diferentes rectángulos en un rectángulo determinado[editar]

En esta variante, los rectángulos pequeños pueden tener longitudes y anchuras variables y deben empaquetarse en un rectángulo grande determinado. El problema de decisión sobre si existe tal empaquetadura es NP-difícil. Esto se puede demostrar mediante su reducción a una 3-partición. Dada una instancia de 3 particiones con 3m enteros positivos: a1, ..., a3m, con una suma total de m T, se construyen 3 m rectángulos pequeños, todos con un ancho de 1, de modo que la longitud del rectángulo i sea ai + m. El rectángulo grande tiene un ancho m y un largo T + 3m. Cada solución para la instancia de 3 particiones induce un empaquetamiento de los rectángulos en m subconjuntos de modo que la longitud total en cada subconjunto sea exactamente T, de modo que encajen exactamente en el rectángulo grande. Por el contrario, en cualquier embalaje del rectángulo grande, no debe haber "agujeros", por lo que los rectángulos no deben girarse. Por lo tanto, el embalaje debe incluir exactamente m filas donde cada fila contenga rectángulos con una longitud total de exactamente T. Esto corresponde a una solución de la instancia de 3 particiones.[3]​[4]​

Cuando existe una restricción adicional de que el embalaje debe ser exacto (sin desperdiciar espacio), los rectángulos pequeños se pueden girar solo en múltiplos de 90°. En este caso, el problema es de complejidad NP. Sin este requisito, los pequeños rectángulos se pueden girar en ángulos arbitrarios. En este caso más general, no está claro si el problema es de dificultad NP o no, ya que es mucho más difícil verificar una solución.[4]​

Empaquetar diferentes rectángulos en un rectángulo de área mínima[editar]

En esta variante, los rectángulos pequeños pueden tener diferentes longitudes y anchuras y su orientación es fija (no se pueden girar). El objetivo es empaquetarlos en un rectángulo circundante de área mínima, sin límites en el ancho o alto del rectángulo circundante. Este problema tiene una aplicación importante al combinar imágenes en una sola imagen más grande. Una página web que carga una sola imagen más grande a menudo se muestra más rápido en el navegador que la misma página que carga varias imágenes pequeñas, debido a la sobrecarga que implica solicitar cada imagen al servidor web. El problema es NP-completo en general, pero existen algoritmos rápidos para resolver casos con pequeños números de imágenes.[5]​[6]​

Problemas relacionados[editar]

  • Corte con guillotina es una variante del embalaje rectangular, con la restricción adicional de que los rectángulos del embalaje deben poder separarse utilizando únicamente cortes de guillotina.
  • Conjunto disjunto máximo (o conjunto independiente máximo) es un problema en el que tanto los tamaños como las ubicaciones de los rectángulos de entrada son fijos, y el objetivo es seleccionar la suma más grande sin rectángulos superpuestos. Por el contrario, en el empaquetamiento rectangular (como en los problemas de empaquetamiento de la vida real), los tamaños de los rectángulos están dados, pero sus ubicaciones son flexibles. Algunos altículos utilizan el término "empaquetado" incluso cuando las ubicaciones son fijas.[7]​
  • Empaquetado de círculos en un cuadrado
  • Empaquetado de cuadrados
  • Teorema de De Bruijn: empaquetar ladrillos rectangulares congruentes de cualquier dimensión en cajas rectangulares.
  • Cuadratura del cuadrado
  • Problema del sofá

Referencias[editar]

  1. ↑ Birgin, E G; Lobato, R D; Morabito, 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. S2CID 12718141. doi:10.1057/jors.2008.141. 
  2. ↑ Fowler, Robert J.; Paterson, Michael S.; Tanimoto, Steven L. (13 de junio de 1981). «Optimal packing and covering in the plane are NP-complete». Information Processing Letters (en inglés) 12 (3): 133-137. ISSN 0020-0190. doi:10.1016/0020-0190(81)90111-3. 
  3. ↑ Demaine, Erik D.; Demaine, Martin L. (1 de junio de 2007). «Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity». Graphs and Combinatorics (en inglés) 23 (1): 195-208. ISSN 1435-5914. S2CID 17190810. doi:10.1007/s00373-007-0713-4. 
  4. ↑ a b Demaine, Erik (2015). «MIT OpenCourseWare – Hardness made Easy 2 – 3-Partition I». Youtube. 
  5. ↑ Huang, E.; Korf, R. E. (23 de enero de 2013). «Optimal Rectangle Packing: An Absolute Placement Approach». Journal of Artificial Intelligence Research 46: 47-87. ISSN 1076-9757. arXiv:1402.0557. doi:10.1613/jair.3735. 
  6. ↑ «Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites». www.codeproject.com (en inglés estadounidense). 14 de junio de 2011. Consultado el 9 de septiembre de 2020. 
  7. ↑ Chan, T. M. (2003). «Polynomial-time approximation schemes for packing and piercing fat objects». Journal of Algorithms 46 (2): 178-189. doi:10.1016/s0196-6774(02)00294-8. «citeseerx: 10.1.1.21.5344». 
Obtenido de «https://es.wikipedia.org/w/index.php?title=Empaquetado_de_rectángulos&oldid=158856189»