Imballaggio massimo di rettangoli in un cerchio

Question

Lavoro in un laboratorio di nanotecnologie in cui faccio il taglio del wafer al silicio. (Il wafer sega solo linee parallele) Cerchiamo, naturalmente, di massimizzare la resa del dado che tagliamo. Tutti i die avranno dimensioni uguali, sia rettangolari o quadrati, e tutti i fili saranno tagliati da un wafer circolare. In sostanza, sto cercando di impacchettare i rettangoli massimi in un cerchio.

Ho solo una conoscenza di base di MATLAB e una comprensione intermedia del calcolo. C'è un modo (relativamente) semplice per farlo, o sono sopra la mia testa?

Answer 1

L'imballaggio di rettangoli arbitrari in un cerchio per soddisfare un obiettivo di efficienza spaziale è un ottimizzazione non convessa (NP-Hard) in generale. Ciò significa che non ci sarà una soluzione elegante o semplice che risolverà questo problema in modo ottimale. I metodi di soluzione dipendono da qualsiasi conoscenza di dominio specifica che è possibile utilizzare per potare l'albero di ricerca o sviluppare l'euristica. Se non hai esperienza in questo tipo di problema, probabilmente dovresti consultare un esperto.

Answer 2

andare da qui, e buona fortuna:

http://en.wikipedia.org/wiki/Knapsack_problem

e ottenere qui:

http://www-sop.inria.fr/mascotte/WorkshopScheduling/2Dpacking.pdf

Almeno avrete qualche idea di cosa stai affrontando qui.

Answer 3

non è simile al problema del cerchio di Gauss? Vedere http://mathworld.wolfram.com/GausssCircleProblem.html

o, questo può essere visto come un "problema di imballaggio" http://en.wikipedia.org/wiki/Packing_problem#Squares_in_circle

Answer 4

ero affascinato di leggere la tua domanda, perché ho fatto un progetto su questo per la mia formazione come insegnante di matematica. Sono anche abbastanza contento di sapere che si pensa che sia un problema di NP, perché il mio progetto mi stava portando alla stessa conclusione.

Utilizzando il calcolo di base, ho calcolato le prime "generazioni" di rettangoli di dimensione massima, ma diventa complesso abbastanza rapidamente.

Potete leggere il mio progetto qui:

Beckett, R. Pacchi di Pi: Un problema curva imballaggio. Bagno Spa MEC. 2009.

• Pages 1 - 15
• Pages 16 - 30

spero che alcuni dei miei risultati sono utili a voi, o almeno interessante. Ho pensato che l'applicazione di questa idea sarebbe molto probabilmente nella tecnologia computer nano.

Cordiali saluti.