(Translated by https://www.hiragana.jp/)
Mathematik im Advent: Plätzchen backen für Perfektionisten - DER SPIEGEL
Zum Inhalt springen
SPIEGEL ONLINE

Mathematik im Advent Plätzchen backen für Perfektionisten

Weihnachtsplätzchen als Herausforderung: Wie muss man die Ausstechformen auf dem Teig platzieren, damit möglichst viele Kekse herauskommen? Fraunhofer-Forscher haben das Problem mit einer Software gelöst, die sonst den Zuschnitt von Röcken und Hosen optimiert.

Wir Menschen sind faul. Wenn wir eine Sache erledigen müssen, dann versuchen wir das möglichst effizient zu tun. Statt zweimal nacheinander zu Kollegen drei Etagen tiefer zu laufen, verbindet man die Wege lieber miteinander. Das spart Zeit und Energie, und schließlich gibt es auch noch anderes zu tun.

Zur Meisterschaft in Sachen Effizienz bringen es Mathematiker. Sie haben verschiedene Instrumentarien entwickelt, um alle möglichen Dinge zu optimieren. Egal ob es um kurze Umsteigezeiten beim U-Bahnfahren geht oder um das Packen eines Kofferraums - sie finden auch für knifflige Aufgaben eine gute Lösung.

Weihnachten

Ein ganz typisches Optimierungsproblem beschäftigt kurz vor viele Hobbybäcker: Wie muss man die Plätzchen aus dem ausgerollten Teig ausstechen, damit möglichst wenige Zwischenräume übrigbleiben? Oder anders gefragt: Wie nutzt man den Teig optimal, wenn beispielsweise vier verschiedene Kekse in gleicher Menge gebacken werden sollen?

Die Aufgabe hat es in sich: Mit welcher Ausstechform beginnt man? Passen mehr Weihnachtsmänner nebeneinander, wenn sie abwechselnd aufrecht und auf dem Kopf stehen? Oder sollten zwischen den Weihnachtsmännern besser kleine Sterne platziert werden? Die Zahl der denkbaren Varianten ist riesig.

Das Weihnachtsplätzchenproblem mag belanglos erscheinen. Wer beim Ausstechen viel Teig verschwendet, muss den Restteig ja nur öfter ausrollen. In der Textilbranche ist die optimale Ausnutzung von Flächen hingegen bares Geld wert. Bei edlen Stoffen kann das Material bis zu 70 Prozent der Gesamtkosten ausmachen. Hersteller achten daher auf jedes Prozent und versuchen, die Schnittbilder etwa von Hosen oder Röcken optimal auf den Stoffbahnen zu verteilen.

Durchschütteln, bis es passt

Dafür nutzen sehr viele Hersteller eine Software, die Forscher am Fraunhofer-Institut für Algorithmen und Wissenschaftliches Rechnen (SCAI)  in St. Augustin entwickelt haben. Autonester  heißt das Paket, das auch in CADきゃど-Systeme integriert werden kann. Die Anwender geben vor, wie viele Stücke welcher Form und Größe sie aus einer Stoffbahn schneiden möchten. Und die Software findet eine Verteilung der Stücke, bei der kaum Verschnitt auftritt.

Fotostrecke

Plätzchen oder Jeans: Flächen optimal nutzen

Foto: SCAI

Das Programm kann sogar Streifen- und Karomuster berücksichtigen. Schließlich darf das Muster der Arme bei einem Hemd nicht anders orientiert sein als beim Rest des Hemdes. Im Vergleich dazu wirkt das Plätzchenausstechen geradezu einfach, denn hier dürfen die Formen nach Belieben gedreht werden.

Wie aber findet die Software die optimale Verteilung der Formen? Letztlich probiert sie einfach nur aus, und zwar Zehntausende Male. "Das ist ein bisschen wie beim Füllen eines Bonbonglases", sagt Fraunhofer-Forscher Ralf Heckmann. "Anfangs schüttelt man stärker, damit größere Löcher schnell mit Bonbons aufgefüllt werden." Später schüttle man dann nur noch ein bisschen.

Das Video zeigt im Zeitraffer, wie die verschiedenen Schnittformen auf der Stoffbahn sich nach und nach zurechtruckeln. Zu Beginn sind die Formen zufällig verteilt und liegen teils sogar übereinander. In den folgenden, tausenden Schritten werden Formen gedreht, miteinander vertauscht oder an andere Stellen positioniert.

Verschieben, vergleichen, verwerfen

Nach jedem Schritt bewertet das Programm Autonester, ob sich die Ausnutzung der Fläche verbessert hat oder nicht. So werden manche Aktionen auch wieder verworfen. Anfangs sind auch Verschlechterungen zulässig. Je nach genutztem Algorithmus dürfen sich die Formen sogar leicht überschneiden. Nähert sich die Optimierung ihrem Ende, ist das natürlich nicht mehr erlaubt.

Bei der Optimierung kombiniert Autonester verschiedene Verfahren wie Simuliertes Abkühlen und Sintflutalgorithmus (siehe Kasten links oben). Systematisches, tausendfaches Probieren allein reicht jedoch nicht aus. Bei Formen, deren Größe sich stark unterscheidet, schaut die Software auch immer wieder nach größeren Lücken, in die man die kleineren Formen platzieren könnte.

Die Suche nach einer guten Lösung erledigt ein moderner PC binnen Minuten. Die Berechnung einer effizienten Verteilung von 40 Plätzchenformen auf einem herkömmlichen Backblech hat beispielsweise zehn Minuten gedauert. Das Ergebnis - siehe Fotostrecke - kann sich sehen lassen: Der Teig wird zu 80 Prozent ausgenutzt. Und auf die Verteilung wäre man als Hobbybäcker wohl kaum von selbst gekommen.

Oft wird die Optimierung auch mehrmals nacheinander gestartet - immer mit etwas anderen Startbedingungen. Dabei können auch Ergebnisse herauskommen, die sich minimal unterscheiden. Denn Autonester findet nicht zwingend die bestmögliche Verteilung.

"Das Nesting-Problem ist NP-schwer", erklärt Ralf Heckmann. Mit zunehmender Zahl der zu verteilenden Stücke steige der Rechenaufwand deshalb enorm. Die gefundene Lösung kommt dem Optimum jedoch in der Regel sehr nahe, versichert der Forscher.

Mehr lesen über

Verwandte Artikel

Die Wiedergabe wurde unterbrochen.