Apilamiento de rectángulos para ocupar el menor espacio posible

Question

Tengo un programa que calculará el área mínima tomada ajustando rectángulos.

Entrada: Rectángulos de diferentes alturas y ancho.
Salida: Un rectángulo que contiene todos estos rectángulos.
Reglas: No se puede girar ni hacer rodar los rectángulos y no se pueden superponer.

Entiendo que esto está relacionado o posiblemente se define como un problema de embalaje de la tolva (NP-hard). Sin embargo, los algoritmos que encontré para aquellos a menudo establecen un límite en, por ejemplo, el ancho. No tengo tales límites, el único objetivo es conseguir que el área resultante sea lo más pequeña posible.

¿Alguna sugerencia sobre qué algoritmo es apropiado para obtener una solución decente?

Answer 1

http://www-rcf.usc.edu/~skoenig/icaps/icaps04/icapspapers/ICAPS04KorfR.pdf

Al parecer, este problema es más difícil de lo que parece en un principio. Es un algoritmo interesante, ya que primero adivina una solución y luego la mejora, por lo que si no quiere esperar a la solución óptima, puede ejecutarla por un número determinado de iteraciones para obtener una solución aproximada (cuanto más tiempo lo ejecutas, mejor es la aproximación).

Answer 2

Comenzaría por hojear http://mathworld.wolfram.com - son geniales para cosas como esta.

En segundo lugar, podría imaginar un algoritmo tonto que pondría el cuadro más largo (en la dimensión X) en la parte inferior, luego el más alto (en la dimensión Y) en la parte superior de uno u otro lado. Luego continúe apilándolos de esta manera "escalonada" yendo hacia la derecha y hacia arriba (por ejemplo, vaya hacia la derecha hasta que no pueda, luego suba, etc., etc.).

Probablemente no sea ideal, y puede darte malos resultados, pero es lo primero que se te viene a la mente.

Answer 3

Recomiendo comenzar con un enfoque simple y codicioso, y ver si eso es lo suficientemente bueno para sus necesidades. Si su entrada es educada o pequeña, eso puede ser todo lo que necesita, y la complejidad aumentará rápidamente cuando intente hacer algo más sofisticado.

Por ejemplo: clasifique los rectángulos por tamaño, el más grande primero. Agregue los rectángulos uno a la vez, probando cada posición posible para el nuevo rectángulo. Elija la posición que dé como resultado el cuadro delimitador más pequeño.

Otro enfoque codicioso sería elegir un rectángulo de inicio, luego agregar repetidamente el rectángulo que resulta en la disposición más densa (donde la densidad se define como el porcentaje del área del cuadro delimitador que se llena).