Maximale Packung von Rechtecken in einem Kreis

Question

Ich arbeite in einem Nanotech-Labor, wo ich Silizium-Wafer-Dicing mache. (Die Wafersäge schneidet nur parallele Linien.) Wir versuchen natürlich, den Ertrag der Stanzform, die wir schneiden, zu maximieren. Alle Würfel sind gleich groß, entweder rechteckig oder quadratisch, und die Würfel sind alle aus einem kreisförmigen Wafer geschnitten. Im Wesentlichen versuche ich, maximale Rechtecke in einen Kreis zu packen.

Ich habe nur ein ziemlich grundlegendes Verständnis von MATLAB und ein mittleres Verständnis von Kalkül. Gibt es einen (relativ) einfachen Weg dies zu tun, oder bin ich weit über meinem Kopf?

Answer 1

Das Packen beliebiger Rechtecke in einen Kreis, um ein Ziel der Raumeffizienz zu erreichen, ist eine nicht-konvexe (NP-Hard) Optimierung im Allgemeinen. Dies bedeutet, dass es keine elegante oder einfache Lösung geben wird, die dieses Problem optimal löst. Die Lösungsmethoden hängen alle von einem bestimmten Domänenwissen ab, mit dem Sie den Suchbaum beschneiden oder Heuristiken entwickeln können. Wenn Sie keine Erfahrung in dieser Art von Problem haben, sollten Sie wahrscheinlich einen Experten konsultieren.

Answer 2

Go von hier, und viel Glück:

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

und hier:

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

Zumindest werden Sie eine Vorstellung haben, was Sie hier Bewältigung sind.

Answer 3

ähnelt das nicht dem Gauss'schen Kreisproblem? Siehe http://mathworld.wolfram.com/GausssCircleProblem.html

oder dies als „Verpackungsproblem“ gesehen werden kann http://en.wikipedia.org/wiki/Packing_problem#Squares_in_circle

Answer 4

Ich war fasziniert Ihre Frage zu lesen, weil ich auf diese ein Projekt tat für meine Ausbildung als Mathematiklehrer. Ich bin auch sehr erfreut zu wissen, dass es sich um ein NP-Problem handelt, weil mein Projekt mich zu demselben Ergebnis geführt hat.

Mit Hilfe der Grundrechnung berechnete ich die ersten 'Generationen' von Rechtecken maximaler Größe, aber es wird ziemlich schnell komplex.

Sie können mein Projekt hier lesen:

Beckett, R. Parcels von Pi: Eine Kurve-Packing-Problem. Badekurort MEC. 2009.

• Pages 1 - 15
• Pages 16 - 30

Ich hoffe, dass Ihnen einige meiner Erkenntnisse nützlich sind, oder zumindest interessant. Ich dachte, dass die Anwendung dieser Idee höchstwahrscheinlich in der Computer-Nanotechnologie erfolgen würde.

Mit freundlichen Grüßen.