Wie viele Cookies sind in der Cookie-Box? - Sterne kacheln

19

Mit der bevorstehenden Ferienzeit beschloss ich, einige Zimtsterne zu machen . Das hat Spaß gemacht (und das Ergebnis war lecker), aber mein innerer Nerd schauderte, als ich das erste Tablett mit Sternen in die Schachtel legte und sie nicht in eine Schicht passten:

Bildbeschreibung hier eingeben

Fast! Gibt es eine Möglichkeit, wie sie hätten passen können? Wie gut können wir überhaupt Sterne kacheln? Angesichts der Tatsache, dass es sich um reguläre sechszackige Sterne handelt, könnten wir die bekannten hexagonalen Kacheln als Näherungswert verwenden:

Bildbeschreibung hier eingeben
Den oben rechts durcheinander gebracht, hoppla.

Aber ist das optimal? Zwischen den Spitzen ist viel Platz.

Beschränken wir uns zu diesem Zweck auf rechteckige Kästchen und sechszackige reguläre Sterne, dh es gibt dreißig Grad (oder ) zwischen jedem tipp und seinen nachbarn ecken. Die Sterne sind durch den Innenradiusri gekennzeichnetπ6rich und den Außenradius :rO

Bildbeschreibung hier eingeben
[ Quelle ]

Beachten Sie, dass wir Sechsecke für und Hexagramme fürri=1rich=32rO. Ich halte es für sinnvoll, diese Extreme (für Cookies) zu berücksichtigen und uns auf den Bereich dazwischen zu beschränken, dhririch=13rOrichr0[13,32] .

rich17mmrO25mm ignorieren Unvollkommenheiten - ich für Geschmack würde, bilden nicht einmal!

Was ist ein optimales Fliesen für Sterne wie oben gekennzeichnet? Wenn es keine statische Best-Tiling-Methode gibt, gibt es einen Algorithmus, um eine gute effizient zu finden?

Raphael
quelle
1
Ja, ich weiß: Was hast du versucht und wo steckst du fest? Dies ist nur ein echtes "Problem", über das ich dachte, es könnte Spaß machen, in der Kekssaison nachzudenken, insbesondere für diejenigen, die eher Denker als Bäcker sind. Habe Spaß!
Raphael
4
Vermutlich bist du am Zuckerguss hängen geblieben. In der Küche. * rimshot *
David Richerby

Antworten:

15

Lassen Sie mich Ihre Frage teilweise für den Hexagrammfall beantworten.

Sie können die folgenden Kacheln erstellen

Bildbeschreibung hier eingeben

Auf diese Weise decken Sie 12/14 = 6/7 der Ebene ab (zählen Sie die Dreiecke im gestrichelten Viereck).

Ist das optimal? Ich würde es mir denken. Obwohl ich keinen Beweis gebe, werde ich einige Argumente vorbringen. Man kann sich fragen, wie gut wir den Raum (Dreieck) zwischen den spitzen Stacheln ausfüllen können. In der obigen Kachel füllen wir die Hälfte davon. Können wir es besser machen?

Bildbeschreibung hier eingeben

sek2(x)23bräunen(x)+2.

Die Darstellung dieser Funktion sieht so aus und zeigt, dass unsere Intuition richtig war.

Bildbeschreibung hier eingeben

A.Schulz
quelle
0

Das Folgende wird nicht als endgültiger oder spezifischer / überlegener Angriff auf dieses möglicherweise unerwartet komplexe Problem angeboten, sondern als zusätzlicher wissenschaftlicher / theoretischer Blickwinkel / allgemeine Studie, der bisher nicht behandelt wurde.

1 st dieses allgemeine Gebiet ist bekannt als / klassifiziert „Bin Packing“ , und dies ist ein 2D - Fall. Es gibt einige berühmte Beweise aus der Mathematik, die in Zusammenhang stehen, z. B. den 3D-Fall von Keplers Untersuchung der Kugelpackung der jahrhundertelang ein offenes Problem darstellte und "vor kurzem" mit einem Computer-Beweis von Hales gelöst wurde. Ein Beispiel für einen 2D-Fall, der in der Industrie täglich verwendet wird, ist die Optimierung von Chip-Layouts. Dies ist natürlich anders als das Problem, kann jedoch auf die Komplexität dieser Problemtypen hinweisen. Zum Beispiel scheint es keine Theorie zu geben, die erfordert / anzeigt, dass ein 2D-Fall einfacher wäre als ein 3D-Fall. Beachten Sie auch, dass eine einfache rechteckige Grenze nicht unbedingt zur Vereinfachung der Lösung beiträgt, sondern lediglich eine polygonale Grenze.

Eine analytische Lösung könnte möglich sein, wenn in der Problemstellung eine grundlegende Definition / ein Schema für "reguläres Kacheln" angegeben wird, z.

Die Bedingungen des Problems (möglicherweise nicht intuitiv) scheinen nicht zu einer analytisch optimalen Lösung zu führen. Dies mag für einige überraschend sein, aber es ist bekannt, dass sehr ähnliche Probleme beim Kacheln des Flugzeugs unentscheidbar sind (dies war vor Jahren ein berühmtes Ergebnis, und es gibt viele Referenzen und sogar laufende Forschungen). Ein wesentlicher Unterschied zwischen den entscheidbaren (lösbaren / analytischen) und den unentscheidbaren Problemen besteht darin, ob die Kacheln "regelmäßig" sind. Das obige Problem bezieht sich auf "reguläre Sterne", nicht jedoch auf "reguläre Kacheln". Die andere aktuelle Antwort geht von einer Art regulären Kacheln oder Reihenfolge aus. Beachten Sie jedoch, dass das Definieren von "regulären Kacheln" formal / mathematisch sehr schwierig sein kann.

Probleme wie dieses sind im Allgemeinen genetischen Algorithmen durchaus zugänglich . ein solcher Algorithmus kann "sehr gute" Packungen finden, die wahrscheinlich nicht wesentlich verbessert werden, und vielleicht können einige Grenzen für ihre Optimalität mit sehr ausgeklügelten Methoden gesetzt werden (dh sie müssen innerhalb eines kleinen Fehlerprozentsatzes des Optimums liegen), können jedoch keine beweisen sind optimal.

hier sind einige refs gefunden, die generell direkt anwendbar sind:

vzn
quelle
ähnliche Theorie siehe auch Packung von Tetraedern von Chang / NYT. Vermutung (etwas inspiriert von dem Artikel): Für dieses spezielle Problem gibt es eine unregelmäßige Packung, die jeder normalen überlegen ist.
vzn
0

Während dieses spezielle Problem wahrscheinlich nicht untersucht wurde, wurden solche Fragen von Laszlo Fejes Toth gestellt und sind als Verpackungsprobleme bekannt. Ich empfehle dringend das dritte Kapitel des Pach-Agarwal-Buches .

domotorp
quelle
1
So wie es ist, ist dies keine Antwort, sondern ein Kommentar. Können Sie zusammenfassen, was das zitierte Buch zu diesem Thema enthält und wie es hier angewendet werden kann?
Raphael