El empaquetamiento de rectángulos es un problema de empaquetamiento en el que el 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 se superpongan dos rectángulos pequeños. 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 solo rectángulo de tamaño ( l , w ) y un rectángulo más grande de tamaño ( L , W ). El objetivo es empaquetar tantos rectángulos pequeños como sea posible en el rectángulo grande. Se permite rotar algunos de los pequeños rectángulos en múltiplos de 90 °.
Este problema tiene algunos como la carga de cajas en palés y, en concreto, la estiba de celulosa . Como resultado de ejemplo: es posible empaquetar 147 pequeños rectángulos de tamaño (137,95) en un gran rectángulo de tamaño (1600,1230). [1]
Empaquetar cuadrados idénticos en un polígono rectilíneo
Dado un polígono rectilíneo 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 que no se solapan que pueden ser envasados en puntos de S .
Suponga que, para cada punto p en S , colocamos un cuadrado centrado en p . Sea G S la gráfica de intersección de estos cuadrados. A-embalaje cuadrado es equivalente a un conjunto independiente en G S . Encontrar un empaque cuadrado más grande es NP-difícil; uno puede probar esto reduciendo de 3SAT . [2]
Empaquetando diferentes rectángulos en un rectángulo dado
En esta variante, los rectángulos pequeños pueden tener diferentes longitudes y anchos, y deben empaquetarse en un rectángulo grande dado. El problema de decisión de si existe tal empaque es NP-hard . Esto puede demostrarse mediante una reducción de 3 particiones . Dada una instancia de 3 particiones con 3 m enteros positivos: a 1 , ..., a 3 m , con una suma total de m T , construimos rectángulos pequeños de 3 m , todos con un ancho de 1, tal que la longitud del rectángulo i es un i + m . El rectángulo grande tiene ancho my largo T + 3 m . Cada solución para la instancia de 3 particiones induce un empaque de los rectángulos en m subconjuntos de tal manera que la longitud total en cada subconjunto es exactamente T , por lo que encajan exactamente en el gran rectángulo. Por el contrario, en cualquier embalaje del rectángulo grande, no debe haber "agujeros", por lo que los rectángulos no deben rotarse. Por lo tanto, el embalaje debe implicar exactamente m filas en las que 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 empaque debe ser exacto (sin desperdicio de espacio), los pequeños rectángulos se pueden rotar solo en múltiplos de 90 °. En este caso, el problema está en NP . Sin este requisito, los pequeños rectángulos se pueden rotar en ángulos arbitrarios. En este caso más general, no está claro si el problema está en NP, ya que es mucho más difícil verificar una solución. [4]
Empaquetando diferentes rectángulos en un rectángulo de área mínima
En esta variante, los pequeños rectángulos pueden tener diferentes longitudes y anchos, 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 procesa 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 del servidor web. El problema es NP-completo en general, pero existen algoritmos rápidos para resolver instancias pequeñas. [5] [6]
Ver también
- El corte con guillotina es un problema estrechamente relacionado con el empaque de rectángulos, en el que existe una restricción adicional sobre el empaque, que debería ser posible separar los rectángulos utilizando solo cortes de guillotina .
- Embalaje cuadrado en un cuadrado
- Teorema de de Bruijn
Referencias
- ^ Birgin, EG; Lobato, RD; Morabito, R (2010). "Un método eficaz de partición recursiva para el empaquetado de rectángulos idénticos en un rectángulo". Revista de la Sociedad de Investigación Operativa . 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 embalaje y el recubrimiento óptimos en el avión son NP-completos" . Cartas de procesamiento de 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 bordes y embalaje Polyomino: conexiones y complejidad" . Gráficos y Combinatoria . 23 (1): 195-208. doi : 10.1007 / s00373-007-0713-4 . ISSN 1435-5914 .
- ^ a b Demaine, Erik (2015). "MIT OpenCourseWare - Dureza simplificada 2 - 3 particiones I" . Youtube .
- ^ Huang, E .; Korf, RE (23 de enero de 2013). "Embalaje de rectángulo óptimo: un enfoque de colocación absoluta" . Revista de Investigación en Inteligencia Artificial . 46 : 47–87. doi : 10.1613 / jair.3735 . ISSN 1076-9757 .
- ^ "Algoritmo de empaquetado rectangular de optimización rápida para la construcción de Sprites CSS" . www.codeproject.com . Consultado el 9 de septiembre de 2020 .