1. Inicio
  2. Pregunta y respuesta
  3. Embalaje máximo de rectángulos en un círculo

Embalaje máximo de rectángulos en un círculo

2010-10-13 20 views
9

Trabajo en un laboratorio de nanotecnología donde hago corte de obleas de silicio. (La sierra de oblea corta solo las líneas paralelas) Estamos, por supuesto, tratando de maximizar el rendimiento del dado que cortamos. Todos los dados serán del mismo tamaño, ya sean rectangulares o cuadrados, y todos los troqueles se cortan de una oblea circular. Esencialmente, estoy tratando de empacar rectángulos máximos en un círculo.Embalaje máximo de rectángulos en un círculo

Tengo solo una comprensión bastante básica de MATLAB y una comprensión intermedia del cálculo. ¿Hay alguna forma (relativamente) simple de hacer esto, o estoy por encima de mi cabeza?

Fuente

2010-10-13 Patrick

+2

Además de la sintaxis de matlab, es posible que también desee considerar http://math.stackexchange.com/ y http://mathoverflow.net/ para resolver el problema de cálculo. –

+2

No estoy seguro de cuál es su pregunta. Pero la eficiencia del empaquetamiento de cuadrados/rectángulos en un círculo se acerca al 100% a medida que el tamaño del cuadrado/rectángulo se aproxima a cero. –

+0

parece sabor interesante de un problema de mochila http://en.wikipedia.org/wiki/Knapsack_problem –

Respuesta

0

El embalaje de rectángulos arbitrarios en un círculo para cumplir con un objetivo de eficiencia de espacio es una optimización no convexa (NP-Hard) en general. Esto significa que no habrá una solución elegante o simple que resuelva este problema de manera óptima. Los métodos de solución dependerán de cualquier conocimiento de dominio específico que pueda usar para podar el árbol de búsqueda o desarrollar heurística. Si no tiene experiencia en este tipo de problema, probablemente deba consultar con un experto.

Fuente

2010-10-15 01:50:58 fairidox

+1

OP dice "Todos los troqueles serán del mismo tamaño, rectangulares o cuadrados". No tan duro para NP después de todo. –

1

Me fascinó leer su pregunta porque hice un proyecto sobre esto para mi formación como profesor de matemáticas. También estoy muy satisfecho de saber que se piensa que es un problema NP, porque mi proyecto me llevaba a la misma conclusión.

Utilizando el cálculo básico, calculé las primeras 'generaciones' de rectángulos de tamaño máximo, pero se vuelve complejo con bastante rapidez.

Usted puede leer mi proyecto aquí:

Beckett, R. paquetes de Pi: Un problema curva de embalaje. Bath Spa MEC. 2009.

espero que algunos de mis hallazgos son útiles para usted o al menos interesante. Pensé que la aplicación de esta idea probablemente sería en nanotecnología informática.

Saludos cordiales.

Fuente

2011-02-23 08:36:27

+0

¡Ese documento es fascinante! –

Cuestiones relacionadas

 Cuestiones relacionadas