El 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.
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]
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]
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]
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]