Hispanopedia WikiEl empaquetamiento de rectángulos es un problema de empaquetamiento cuyo objetivo es determinar si un conjunto dado de rectángulos pequeños se puede colocar dentro de un polígono grande dado, de modo que no haya dos rectángulos pequeños superpuestos. Se han estudiado varias variantes de este problema.
Empaquetar rectángulos idénticos en un rectángulo
En esta variante, hay varias instancias de un único rectángulo de tamaño ( l , w ) y un rectángulo más grande de tamaño ( L , W ). El objetivo es colocar tantos rectángulos pequeños como sea posible en el rectángulo grande sin superposición entre ningún rectángulo (pequeño o grande). Las restricciones comunes del problema incluyen limitar la rotación del rectángulo pequeño a múltiplos de 90° y requerir que cada rectángulo pequeño sea ortogonal al rectángulo grande.
Este problema tiene algunas aplicaciones como la carga de cajas sobre palets y, en concreto, la estiba de pulpa de madera . Como resultado de ejemplo: es posible empaquetar 147 rectángulos pequeños de tamaño (137,95) en un rectángulo grande de tamaño (1600,1230). [1]
Empaquetamiento de cuadrados idénticos en un polígono rectilíneo
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 puedan empaquetar en puntos de S.
Supongamos que, para cada punto p en S , ponemos un cuadrado centrado en p . Sea G S el gráfico de intersección de estos cuadrados. Un empaquetamiento de cuadrados es equivalente a un conjunto independiente en G S . Encontrar un empaquetamiento de cuadrados más grande es NP-difícil; se puede demostrar esto reduciendo a partir de 3SAT . [2]
Empaquetar diferentes rectángulos en un rectángulo dado
En esta variante, los rectángulos pequeños pueden tener longitudes y anchos variables, y deben empaquetarse en un rectángulo grande dado. El problema de decisión de si existe tal empaquetamiento es NP-duro . Esto se puede demostrar mediante una reducción de 3-partición . Dada una instancia de 3-partición con 3 m enteros positivos: a 1 , ..., a 3 m , con una suma total de m T , construimos 3 m rectángulos pequeños, todos con un ancho de 1, tales que la longitud del rectángulo i es a i + m . El rectángulo grande tiene ancho m y longitud T + 3 m . Cada solución a la instancia de 3-partición induce un empaquetamiento de los rectángulos en m subconjuntos tales que la longitud total en cada subconjunto es exactamente T , por lo que encajan exactamente en el rectángulo grande. Por el contrario, en cualquier empaquetamiento del rectángulo grande, no debe haber "agujeros", por lo que los rectángulos no deben rotarse. Por lo tanto, el empaquetamiento debe involucrar exactamente m filas donde cada fila contiene 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 empaquetamiento debe ser exacto (sin desperdiciar espacio), los rectángulos pequeños pueden rotarse solo en múltiplos de 90°. En este caso, el problema es NP . Sin este requisito, los rectángulos pequeños pueden rotarse en ángulos arbitrarios. En este caso más general, no está claro si el problema es NP, 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
En esta variante, los rectángulos pequeños pueden tener longitudes y anchos variables, y su orientación es fija (no se pueden rotar). El objetivo es empaquetarlos en un rectángulo envolvente de área mínima, sin límites en el ancho o la altura del rectángulo envolvente. Este problema tiene una aplicación importante en la combinación de imágenes en una sola imagen más grande. Una página web que carga una sola imagen más grande a menudo se procesa más rápido en el navegador que la misma página que carga múltiples 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 instancias pequeñas. [5] [6]
Problemas relacionados
- El corte en guillotina es una variante del embalaje rectangular, con la restricción adicional de que los rectángulos en el embalaje deben ser separables utilizando únicamente cortes de guillotina .
- El conjunto máximo disjunto (o conjunto máximo independiente ) 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 mayor suma de rectángulos que no se superpongan. Por el contrario, en el empaquetamiento de rectángulos (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 artículos utilizan el término "empaquetamiento" incluso cuando las ubicaciones son fijas. [7]
- Empaquetado circular en un rectángulo
- Embalaje cuadrado en un cuadrado
- Teorema de De Bruijn : empaquetar ladrillos rectangulares congruentes de cualquier dimensión en cajas rectangulares.
Referencias
- ^ Birgin, EG; Lobato, RD; Morabito, R (2010). "Un enfoque de partición recursiva eficaz para el empaquetamiento de rectángulos idénticos en un rectángulo". Journal of the Operational Research Society . 61 (2): 306–320. doi :10.1057/jors.2008.141. S2CID 12718141.
- ^ Fowler, Robert J.; Paterson, Michael S.; Tanimoto, Steven L. (13 de junio de 1981). "El empaquetamiento y el recubrimiento óptimos en el plano son NP-completos". Cartas de procesamiento de la información . 12 (3): 133–137. doi :10.1016/0020-0190(81)90111-3. ISSN 0020-0190.
- ^ Demaine, Erik D.; Demaine, Martin L. (1 de junio de 2007). "Rompecabezas, emparejamiento de aristas y empaquetamiento de poliominós: conexiones y complejidad". Graphs and Combinatorics . 23 (1): 195–208. doi :10.1007/s00373-007-0713-4. ISSN 1435-5914. S2CID 17190810.
- ^ de Demaine, Erik (2015). "MIT OpenCourseWare – La dureza simplificada 2 – 3 particiones I". Youtube .
- ^ Huang, E.; Korf, RE (23 de enero de 2013). "Empaquetado óptimo de rectángulos: un enfoque de colocación absoluta". Revista de investigación en inteligencia artificial . 46 : 47–87. arXiv : 1402.0557 . doi : 10.1613/jair.3735 . ISSN 1076-9757.
- ^ "Algoritmo de empaquetamiento de rectángulos de optimización rápida para la creación de sprites CSS". www.codeproject.com . 14 de junio de 2011 . Consultado el 9 de septiembre de 2020 .
- ^ Chan, TM (2003). "Esquemas de aproximación en tiempo polinomial para empaquetar y perforar objetos gordos". Journal of Algorithms . 46 (2): 178–189. CiteSeerX 10.1.1.21.5344 . doi :10.1016/s0196-6774(02)00294-8.