algorithm - segun - meme y memetica

Apilamiento de rectángulos para tomar 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 empaque en el contenedor (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

Comenzaría hojeando http://mathworld.wolfram.com . Son geniales para cosas como esta.

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

Eso probablemente no sea ideal, y puede darte malos resultados, pero es lo primero que se te ocurrió.

Answer 2

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, primero el más grande. 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).

Answer 3

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

Aparentemente, este problema es más difícil de lo que parece al 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).