Sich verpacken lassende Probleme sind eine Klasse von Optimierungsproblemen in der Mathematik, die das Versuchen einschließen, Gegenstände zusammen (häufig innerhalb eines Behälters) so dicht einzupacken, wie möglich. Viele dieser Probleme können mit dem echten Lebensverpacken, der Lagerung und den Transport-Problemen verbunden sein. Jedes sich verpacken lassende Problem hat ein Doppelbedeckungsproblem, das fragt, wie viele derselben Gegenstände erforderlich sind, jedes Gebiet des Behälters völlig zu bedecken, wo Gegenständen erlaubt wird zu überlappen.

In einem sich verpacken lassenden Problem wird Ihnen gegeben:

• 'Behälter' (gewöhnlich einzelne zwei - oder dreidimensionales konvexes Gebiet oder ein unendlicher Raum)
• 'Waren' (gewöhnlich ein einzelner Typ der Gestalt), einige, oder von denen alle in diesen Behälter gepackt sein müssen

Gewöhnlich muss die Verpackung ohne Übergreifen zwischen Waren und anderen Waren oder den Behälterwänden sein. Das Ziel ist, die Konfiguration mit der maximalen Dichte zu finden. In einigen Varianten wird der Überschneidung (Waren mit einander und/oder mit der Grenze des Behälters) erlaubt, aber sollte minimiert werden.

Verpackung unendlichen Raums

Viele dieser Probleme, wenn die Behältergröße in allen Richtungen vergrößert wird, werden gleichwertig zum Problem, Gegenstände so dicht einzupacken, wie möglich im unendlichen Euklidischen Raum. Dieses Problem ist für mehrere wissenschaftliche Disziplinen wichtig, und hat bedeutende Aufmerksamkeit erhalten. Die Kepler-Vermutung hat eine optimale Lösung verlangt, um Bereiche Hunderte von Jahren einzupacken, bevor es richtig von Thomas Callister Hales bewiesen wurde. Viele andere Gestalten haben Aufmerksamkeit, einschließlich Ellipsoide, Platonic und Festkörper von Archimedean einschließlich tetrahedra und ungleichen Bereichs dimers erhalten.

Sechseckige Verpackung von Kreisen

Diese Probleme sind von den Ideen im Kreisverpackungslehrsatz mathematisch verschieden. Der zusammenhängende Kreis, der Problem-Geschäfte mit sich verpacken lassenden Kreisen, vielleicht verschiedener Größen, auf einer Oberfläche, zum Beispiel das Flugzeug oder ein Bereich einpackt.

Die Kopien eines Kreises in anderen Dimensionen können mit der ganzen Leistungsfähigkeit in Dimensionen nie gepackt sein, die größer sind als eine (in einem dimensionalem Weltall, die Kreisentsprechung ist gerade zwei Punkte). D. h. es wird immer unbenutzten Raum geben, wenn Sie nur Kreise einpacken. Die effizienteste Weise, Kreise, sechseckige Verpackung einzupacken, erzeugt etwa 91 %

Bereich-Verpackung in höheren Dimensionen

In drei Dimensionen bietet das flächenzentrierte Kubikgitter die beste Gitter-Verpackung von Bereichen an und wird geglaubt, die optimale von der ganzen Verpackung zu sein. Wie man auch glaubt, sind das 8-dimensionale E8 Gitter und 24-dimensionale Blutegel-Gitter optimal.

Verpackung von Platonischen Festkörpern in drei Dimensionen

Würfel können leicht eingeordnet werden, um dreidimensionalen Raum völlig, die natürlichste Verpackung zu füllen, die die Kubikhonigwabe ist. Kein anderer Platonischer Festkörper kann Raum selbstständig mit Ziegeln decken, aber einige einleitende Ergebnisse sind bekannt. Tetrahedra kann eine Verpackung von mindestens 85 % erreichen. Eine der besten Verpackung von regelmäßigem dodecahedra basiert auf dem oben erwähnten Gitter des flächenzentriert kubisch (FCC).

Tetrahedra und octahedra können zusammen den ganzen Raum in einer als die vierflächige-octahedral Honigwabe bekannten Einordnung füllen.

Die Verpackung in 3-dimensionalen Behältern

Bereiche in einen Euklidischen Ball

Das Problem, den kleinsten Ball solch zu finden, dass zusammenhanglose offene Einheitsbälle darin gepackt sein können, hat eine einfache und ganze Antwort in - dimensionaler Euklidischer Raum wenn, und in einem unendlichen dimensionalen Raum von Hilbert ohne Beschränkungen. Es lohnt sich, im Detail hier zu beschreiben, einen Geschmack nach dem allgemeinen Problem zu geben. In diesem Fall ist eine Konfiguration von pairwise Tangente-Einheitsbällen verfügbar. Legen Sie die Zentren an den Scheitelpunkten eines regelmäßigen dimensionalen Simplexes mit dem Rand 2; das wird leicht begriffen, von einer orthonormalen Basis anfangend. Eine kleine Berechnung zeigt, dass die Entfernung jedes Scheitelpunkts vom barycenter ist. Außerdem hat jeder andere Punkt des Raums notwendigerweise eine größere Entfernung von mindestens einem der Scheitelpunkte. In Bezug auf Einschließungen von Bällen werden die offenen Einheitsbälle, die daran in den Mittelpunkt gestellt sind, in einen Ball des Radius eingeschlossen, der für diese Konfiguration minimal ist.

Um zu zeigen, dass diese Konfiguration optimal ist, lassen Sie, die Zentren von zusammenhanglosen offenen Einheitsbällen zu sein, die in einem Ball des an einem Punkt in den Mittelpunkt gestellten Radius enthalten sind. Denken Sie die Karte vom begrenzten Satz in die Einnahme im Entsprechen für jeden. Seitdem für alle

Bereiche in einem cuboid

Beschließen Sie, dass die Zahl von kugelförmigen Gegenständen des gegebenen Diameters d in einen cuboid der Größe ein × b × c gepackt sein kann.

Die Verpackung in 2-dimensionalen Behältern

Verpackung von Kreisen

Kreise im Kreis

Packen Sie n Einheitskreise in den kleinstmöglichen Kreis ein. Das ist nah mit dem Verbreiten von Punkten in einem Einheitskreis mit dem Ziel verbunden, die größte minimale Trennung, d zwischen Punkten zu finden.

Optimale Lösungen sind für n13 und n=19 bewiesen worden.

Kreise im Quadrat

Packen Sie n Einheitskreise ins kleinstmögliche Quadrat ein. Das ist nah mit dem Verbreiten von Punkten in einem Einheitsquadrat mit dem Ziel verbunden, die größte minimale Trennung, d zwischen Punkten zu finden. Um sich zwischen diesen zwei Formulierungen des Problems umzuwandeln, wird die Quadratseite für Einheitskreise L=2+2/d sein.

Optimale Lösungen sind für n30 bewiesen worden.

Kreise im gleichschenkligen rechtwinkligen Dreieck

Packen Sie n Einheitskreise ins kleinstmögliche gleichschenklige rechtwinklige Dreieck ein. Gute Schätzungen sind für n bekannt

Kreise im gleichseitigen Dreieck

Packen Sie n Einheitskreise ins kleinstmögliche gleichseitige Dreieck ein. Optimale Lösungen sind für n bekannt

Verpackung von Quadraten

Quadrate im Quadrat

Packen Sie n Einheitsquadrate ins kleinstmögliche Quadrat ein.

Optimale Lösungen sind für n=1-10, 14-16, 23-25, 34-36, 62-64, 79-81, 98-100, und jede quadratische ganze Zahl bewiesen worden.

Der vergeudete Raum ist asymptotisch O (a).

Quadrate im Kreis

Packen Sie n Quadrate im kleinstmöglichen Kreis ein.

Minimale Lösungen:

Verpackung von Rechtecken

Identische Rechtecke in einem Rechteck

Das Problem, vielfache Beispiele eines einzelnen Rechtecks der Größe (l, w) einzupacken, 90 ° Folge, in einem größeren Rechteck der Größe (L, W) berücksichtigend, hat einige Anwendungen wie das Laden von Kästen auf Paletten und, spezifisch, Holzstoff-Stauraum.

Zum Beispiel ist es möglich, 147 Rechtecke der Größe (137,95) in einem Rechteck der Größe (1600,1230) einzupacken.

Verschiedene Rechtecke in einem Rechteck

Das Problem, vielfache Rechtecke unterschiedlicher Breiten und Höhen in einem Umgeben-Rechteck des minimalen Gebiets (aber ohne Grenzen auf der Umgeben-Rechteck-Breite oder Höhe) einzupacken, hat eine wichtige Anwendung in sich verbindenden Images in ein einzelnes größeres Image. Eine Webseite, die ein einzelnes größeres Image häufig lädt, macht schneller im Browser als dieselbe Seite, die vielfache kleine Images wegen des oberirdischen lädt, das an der Anforderung jedes Images vom Webserver beteiligt ist.

Ein Beispiel eines schnellen Algorithmus, der Rechtecke unterschiedlicher Breiten und Höhen in ein Umgeben-Rechteck des minimalen Gebiets einpackt, ist hier.

Zusammenhängende Felder

es mit Ziegeln deckt oder tessellation Problemen, gibt es, keine Lücken, noch Übergreifen zu sein. Viele der Rätsel dieses Typs schließen sich verpacken lassende Rechtecke oder polyominoes in ein größeres Rechteck oder andere quadratähnliche Gestalt ein.

Es gibt bedeutende Lehrsätze dabei, Rechtecke (und cuboids) in Rechtecken (cuboids) ohne Lücken oder Übergreifen mit Ziegeln zu decken:

:An × b Rechteck kann mit 1 &times gepackt sein; n zieht sich aus iff teilt n a, oder n teilt b.

:de-Lehrsatz von Bruijn: Ein Kasten kann mit einem harmonischen Ziegel &times gepackt sein; ein b × ein b c, wenn der Kasten Dimensionen ein p &times hat; ein b q × ein b c r für einige natürliche Zahlen p, q, r (d. h., ist der Kasten ein Vielfache des Ziegels.)

Die Studie von polyomino tilings betrifft größtenteils zwei Klassen von Problemen: Ein Rechteck mit kongruenten Ziegeln mit Ziegeln zu decken, und einen jedes n-omino in ein Rechteck einzupacken.

Ein klassisches Rätsel der zweiten Art soll alle zwölf pentominoes in Rechtecke nach Größen geordnet 3×20, 4×15, 5×12 oder 6×10 einordnen.

Verpackung von unregelmäßigen Gegenständen

Die Verpackung von unregelmäßigen Gegenständen ist ein Problem, sich gut zu geschlossenen Form-Lösungen nicht leihend; jedoch ist die Anwendbarkeit auf die praktische Umweltwissenschaft ziemlich wichtig. Zum Beispiel lassen sich Boden-Partikeln in der unregelmäßigen Form verschieden als die Größen verpacken, und Gestalten ändern sich, zu wichtigen Ergebnissen für die Pflanzenart führend, um Wurzelbildungen anzupassen und Wasserbewegung im Boden zu erlauben.

Siehe auch

• Satz, der sich verpacken lässt
• Behälter-Verpackungsproblem
• Slothouber-Graatsma verwirren
• Rätsel von Conway
• Tetris
• Bedeckung des Problems
• Rucksack-Problem
• Tetraeder, das sich verpacken lässt
• Der Ausschnitt des Aktienproblems
• Das Küssen des Zahl-Problems

Referenzen

Links

Viele Rätsel-Bücher sowie mathematische Zeitschriften enthalten Artikel über sich verpacken lassende Probleme.

• Verbindungen zu verschiedenen Artikeln MathWorld über die Verpackung
• MathWorld bemerkt auf sich verpacken lassenden Quadraten.
• Das sich verpacken lassende Zentrum von Erich
• www.packomania.com Eine Seite mit Tischen, Graphen, Rechenmaschinen, Verweisungen, usw.
• "Kasten, der Sich" durch Ed Pegg den Jüngeren Verpacken lässt. das Wolfram-Demonstrationsprojekt, 2007.
• Am besten bekannte Verpackung von gleichen Kreisen in einem Kreis, bis zu 1100
• Das Beheben des Verpackungsproblems in PHP