El empaquetado de rectángulos es un problema de empaquetado en el que 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 varias variantes de este problema.
En esta variante, hay varias instancias de un solo rectángulo de tamaño ( l , w ) y un rectángulo de tamaño más grande ( L , W ). 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 o grandes). Las restricciones comunes del problema incluyen limitar la rotación de rectángulos pequeños a múltiplos de 90° y exigir que cada rectángulo pequeño sea ortogonal al rectángulo grande.
Este problema tiene algunas aplicaciones como la carga de cajas sobre palés y, concretamente, la estiba de pasta 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]
Dado un polígono rectilíneo (cuyos lados se encuentran en ángulo recto ) 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 , colocamos un cuadrado centrado en p . Sea G S la gráfica de intersección de estos cuadrados. Un empaquetado cuadrado es equivalente a un conjunto independiente en G S . Encontrar el empaque cuadrado más grande es NP-difícil; uno puede probar esto reduciendo desde 3SAT . [2]
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-duro . Esto se puede demostrar 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, tales que la longitud del rectángulo i es a i + m . El rectángulo grande tiene ancho m y largo T + 3 m . 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 , por lo que encajan 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 rotarse. 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 pequeños rectángulos se pueden girar sólo en múltiplos de 90°. En este caso el problema está en 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 está en NP, ya que es mucho más difícil verificar una solución. [4]
En esta variante, los pequeños rectángulos 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 única 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 instancias pequeñas. [5] [6]