algorithm - español - bin packing java

¿Qué algoritmo puede usarse para empaquetar rectángulos de diferentes tamaños en el rectángulo más pequeño posible de una manera bastante óptima?

Question

Tengo un montón de objetos rectangulares que necesito empacar en el espacio más pequeño posible (las dimensiones de este espacio deben ser potencias de dos).

Soy consciente de varios algoritmos de empaquetado que empaquetarán los elementos lo mejor posible en un espacio determinado, sin embargo, en este caso, necesito que el algoritmo determine cuán grande debe ser ese espacio.

Por ejemplo, digo que tengo los siguientes rectángulos

• 128 * 32
• 128 * 64
• 64 * 32
• 64 * 32

Se pueden empaquetar en un espacio de 128 * 128

_________________ |128*32 | |________________| |128*64 | | | | | |________________| |64*32 |64*32 | |_______|________|

Sin embargo, si también hubiera 160 * 32 y 64 * 64, se necesitaría un espacio de 256 * 128

________________________________ |128*32 |64*64 |64*32 | |________________| |_______| |128*64 | |64*32 | | |_______|_______| | | | |________________|___ | |160*32 | | |____________________|___________|

¿Qué algoritmos hay que pueden empaquetar un montón de rectángulos y determinar el tamaño requerido para el contenedor (a una potencia de 2 y dentro de un tamaño máximo determinado para cada dimensión)?

Answer 1

Echa un vistazo a los problemas de embalaje . Creo que el tuyo cae en ''embalaje de contenedores 2D''. Debe poder aprender mucho de las soluciones a ese y otros problemas de embalaje.

Ver también: Empaquetar datos de imagen rectangulares en una textura cuadrada.

Answer 2

Estoy bastante seguro de que este es un problema NP-difícil , por lo tanto, para una solución óptima, tendría que implementar un algoritmo de seguimiento que pruebe todas las combinaciones posibles.

La buena noticia es que debido a la necesidad de empaquetar rectángulos 2D en un espacio 2D limitado, puede eliminar muchas posibilidades desde el principio, por lo que podría no ser tan malo.

Answer 3

Existe una extensa literatura sobre este problema. Una buena heurística codiciosa es colocar rectángulos desde el área más grande hasta la más pequeña en la primera posición disponible hacia la parte inferior e izquierda del contenedor. Piense en la gravedad tirando de todos los elementos hacia la esquina inferior izquierda. Para una descripción de este google "Chazelle inferior izquierda embalaje".

Para soluciones óptimas, las técnicas más modernas pueden empaquetar más de 20 rectángulos en unos pocos segundos. Huang tiene un algorithm que separa el problema de encontrar el cuadro delimitador envolvente más pequeño del problema de decidir si un conjunto de rectángulo puede caber en un cuadro delimitador de un tamaño específico. Le da a su programa un conjunto de rectángulos, y le indica el cuadro delimitador de cierre más pequeño que se requiere para empaquetarlos.

Para su caso, su bucle exterior debe iterar desde el cuadro delimitador más pequeño posible hacia arriba (con el ancho y la altura incrementándose sucesivamente por potencias de dos). Para cada uno de estos cuadros delimitadores, compruebe si puede encontrar un empaque para sus rectángulos. Obtendrá un montón de respuestas negativas hasta la primera respuesta afirmativa, que se garantiza que será la solución óptima.

Para el bucle interno de su algoritmo, el que responde "sí" o "no" a un cuadro delimitador de tamaño específico, buscaría la referencia Huang y solo implementaría su algoritmo. Incluye muchas optimizaciones sobre el algoritmo básico, pero solo necesitas la carne y las patatas básicas. Ya que desea manejar las rotaciones, en cada punto de bifurcación durante su búsqueda, simplemente intente ambas rotaciones y retroceso cuando ambas rotaciones no dan como resultado una solución.

Answer 4

La solución rápida y sucia de primer paso siempre es una excelente para empezar, como una comparación, si nada más.

Colocación codiciosa de grandes a pequeños.

Ponga el rectángulo más grande que quede en su área empacada. Si no puede caber en cualquier lugar, colóquelo en un lugar que extienda la región del paquete lo menos posible. Repita hasta que termine con el rectángulo más pequeño.

No es perfecto en absoluto, pero es fácil y una buena línea de base. Aun así, empaquetaría su ejemplo original perfectamente y le daría una respuesta equivalente para el segundo también.

Answer 5

Lo que necesita está en https://github.com/nothings/stb/blob/master/stb_rect_pack.h

muestra:

stbrp_context context;

struct stbrp_rect rects[100];

for (int i=0; i< 100; i++)
{
    rects[i].id = i;
    rects[i].w = 100+i;
    rects[i].h = 100+i;
    rects[i].x = 0;
    rects[i].y = 0;
    rects[i].was_packed = 0;
}

int rectsLength = sizeof(rects)/sizeof(rects[0]);

int nodeCount = 4096*2;
struct stbrp_node nodes[nodeCount];


stbrp_init_target(&context, 4096, 4096, nodes, nodeCount);
stbrp_pack_rects(&context, rects, rectsLength);

for (int i=0; i< 100; i++)
{
    printf("rect %i (%hu,%hu) was_packed=%i/n", rects[i].id, rects[i].x, rects[i].y, rects[i].was_packed);
}

Answer 6

Una solución general es no trivial (no se puede hablar de matemáticas por completo)
Por lo general, las personas usan un algoritmo genético para probar posibles combinaciones, pero puede hacerlo razonablemente bien simplemente poniendo la forma más grande en primer lugar y luego probando diferentes lugares para el siguiente más grande y así sucesivamente.

Answer 7

Vea esta página en el proyecto ARC para una encuesta de soluciones, hay una compensación entre la complejidad / tiempo de implementación y la optimización, pero hay una amplia gama de algoritmos para elegir.

Aquí hay un extracto de los algoritmos:

1. Algoritmo de altura decreciente (FFDH) de primer ajuste
   FFDH empaqueta el siguiente artículo R (en altura no creciente) en el primer nivel donde R se ajusta. Si ningún nivel puede acomodar R, se crea un nuevo nivel.
   Complejidad temporal de FFDH: O (n · log n).
   Relación de aproximación: FFDH (I) <= (17/10) · OPT (I) +1; El límite asintótico de 17/10 es estrecho.

2. Algoritmo de altura decreciente de ajuste siguiente (NFDH)
   NFDH empaqueta el siguiente artículo R (en altura no creciente) en el nivel actual si R se ajusta. De lo contrario, el nivel actual se "cierra" y se crea un nuevo nivel.
   Complejidad temporal: O (n · log n).
   Relación de aproximación: NFDH (I) <= 2 · OPT (I) +1; El límite asintótico de 2 es apretado.

3. Algoritmo de altura decreciente (BFDH)
   BFDH empaqueta el siguiente artículo R (en altura no creciente) en el nivel, entre aquellos que pueden acomodar R, para los cuales el espacio horizontal residual es el mínimo. Si ningún nivel puede acomodar R, se crea un nuevo nivel.

4. Algoritmo de abajo a la izquierda (BL)
   BL artículos de primer orden por ancho no creciente. BL empaca el siguiente elemento lo más cerca posible de la parte inferior, y luego lo más cerca posible de la izquierda sin superponerse con ningún elemento empacado. Tenga en cuenta que BL no es un algoritmo de empaquetamiento orientado a nivel.
   Complejidad del tiempo: O (n ^ 2).
   Relación de aproximación: BL (I) <= 3 · OPT (I).

5. Algoritmo de Baker Up-Down (UD)
   UD usa una combinación de BL y una generalización de NFDH. El ancho de la tira y los elementos están normalizados, de modo que la tira tiene un ancho de unidad. UD ordena los artículos en ancho que no aumenta y luego los divide en cinco grupos, cada uno con un ancho en el rango (1/2, 1], (1 / 3,1 / 2], (1 / 4,1 / 3 ], (1 / 5,1 / 4], (0,1 / 5]. La banda también se divide en cinco regiones R1, ···, R5. Básicamente, algunos elementos de ancho en el rango (1 / i + 1, 1 / i], para 1 <= i <= 4, están empaquetados en la región Ri por BL. Dado que BL deja un espacio de ancho creciente de arriba a abajo en el lado derecho de la tira, UD toma esta ventaja primero empacar el artículo en Rj para j = 1, ···, 4 (en orden) de arriba a abajo. Si no hay tal espacio, el artículo se empaqueta en Ri por BL. Finalmente, los artículos de tamaño máximo 1/5 se empaquetan en los espacios en R1, ···, R4 mediante el algoritmo NFDH (generalizado). Nuevamente, si no hay espacio en estas regiones, el artículo se empaqueta en R5 usando NFDH.
   Relación de aproximación: UD (I) <= (5/4) · OPT (I) + (53/8) H, donde H es la altura máxima de los artículos; El límite asintótico de 5/4 es apretado.

6. Algoritmo de ajuste inverso (RF)
   RF también normaliza el ancho de la tira y los elementos para que la tira tenga un ancho de unidad. RF primero apila todos los elementos de ancho mayor que 1/2. Los elementos restantes se clasifican en altura no creciente y se empaquetarán por encima de la altura H0 alcanzada por aquellos mayores que 1/2. Luego RF repite el siguiente proceso. En términos generales, RF empaqueta artículos de izquierda a derecha con su parte inferior a lo largo de la línea de altura H0 hasta que no haya más espacio. Luego empaca los artículos de derecha a izquierda y de arriba a abajo (llamado nivel inverso) hasta que el ancho total sea al menos 1/2. Luego, el nivel inverso se baja hasta que (al menos) uno de ellos toca algún elemento a continuación. El desplegable se repite de alguna manera.
   Relación de aproximación: RF (I) <= 2 · OPT (I).

7. Algoritmo de Steinberg
   El algoritmo de Steinberg, indicado como M en el documento, estima un límite superior de la altura H requerida para empaquetar todos los elementos de tal manera que se demuestre que los elementos de entrada se pueden empaquetar en un rectángulo de ancho W y altura H. Luego, definen siete Procedimientos (con siete condiciones), cada uno para dividir un problema en dos más pequeños y resolverlos de forma recursiva. Se ha demostrado que cualquier problema tratable satisface una de las siete condiciones.
   Relación de aproximación: M (I) <= 2 · OPT (I).

8. Algoritmo de ajuste dividido (SF) SF divide los artículos en dos grupos, L1 con un ancho mayor que 1/2 y L2 como máximo 1/2. Todos los artículos de L1 son primero embalados por FFDH. Luego se organizan de modo que todos los elementos con un ancho superior a 2/3 estén por debajo de los que tienen un ancho máximo de 2/3. Esto crea un rectángulo R de espacio con ancho 1/3. Los artículos restantes en L2 luego se empaquetan en R y el espacio arriba de los empaquetados con L1 usando FFDH. Los niveles creados en R se consideran inferiores a los creados por encima del embalaje de L1.
   Relación de aproximación: SF (I) <= (3/2) · OPT (I) + 2; El límite asintótico de 3/2 es estrecho.

9. Algoritmo de sleator
   El algoritmo de Sleater consta de cuatro pasos:

   1. Todos los elementos de ancho superior a 1/2 se empaquetan uno encima del otro en la parte inferior de la tira. Suponga que h0 es la altura del empaque resultante. Todo empaque posterior ocurrirá por encima de h0.

   2. Los artículos restantes se ordenan por altura no creciente. Un nivel de elementos se empaqueta (en orden de altura no creciente) de izquierda a derecha a lo largo de la línea de altura h0.

   3. Luego se dibuja una línea vertical en el medio para cortar la tira en dos mitades iguales (tenga en cuenta que esta línea puede cortar un artículo que está empacado parcialmente en la mitad derecha). Dibuje dos segmentos de línea horizontal de longitud una mitad, uno a través de la mitad izquierda (llamada línea de base izquierda) y uno a través de la mitad derecha (llamada línea de base derecha) lo más bajo posible, de manera que las dos líneas no crucen ningún elemento.

   4. Elija la línea de base izquierda o derecha que es de una altura más baja y empaquete un nivel de artículos en la mitad correspondiente de la tira hasta que el siguiente artículo sea demasiado ancho.

   Se forma una nueva línea de base y el Paso (4) se repite en la línea de base inferior hasta que se empaquetan todos los elementos.
   Complejidad temporal: O (n · log n).
   La relación de aproximación del algoritmo de Sleator es 2.5, que es estrecha.