Das ewig unlösbare Rätsel: Wie steche ich Weihnachtsplätzchen am besten aus?

Wie können wir den Teig beim Ausstechen von Weihnachtsplätzchen maximieren? Wie packen wir einen Koffer oder füllen einen Küchenschrank und nutzen dabei den Platz optimal aus? Man mag sich gedacht haben: „Es muss doch einen besten Weg geben, dies zu tun.“

Ab sofort scheint das Kopfzerbrechen über dieses Real-Live-Tetris reine Zeitverschwendung zu sein. Mathematiker haben – trotz Supercomputer – herausgefunden, dass es vorläufig unmöglich ist, DIE beste Anordnung für mehr als vier oder fünf würzige Lebkuchenmänner oder Weihnachtsplätzchen zu bestimmen.

Kein Weihnachtswunder zu erwarten

Assistenzprofessor Mikkel Abrahamsen von der Fakultät für Informatik der Universität von Kopenhagen (Dänemark) hat mit zwei Forscherkollegen untersucht, wie schwierig es ist, den optimalen Weg zu finden, um Objekte in zwei Dimensionen ohne Überlappung zu packen. An diesem Rätsel tüfteln Informatiker nicht erst in der Weihnachtszeit, sondern bereits seit Jahrzehnten.

„Während Algorithmen uns in die Lage versetzen, ernsthaft komplexe Probleme zu lösen, ist dies eines, das für die heutigen Computer zu viel des Guten ist“, sagte Prof. Abrahamsen. Weiter sagte er:

Im Moment ist es nicht möglich, mehr als 5 bis 10 Objekte optimal zu packen. Unsere [Studie] deutet darauf hin, dass sich diese Zahl in nächster Zeit wahrscheinlich nicht wesentlich erhöhen wird.“

Dinge optimal zu verpacken ist nicht nur ein gelegentliches Problem im Haushalt, sondern in einer Vielzahl von Industrien. Dazu gehört auch die Textilindustrie oder die Metallverarbeitung. Letztere können die Abfälle ähnlich wie beim Plätzchenteig immerhin wieder einschmelzen und „neu ausrollen“. In der Schifffahrt gilt das für das Packen von Containern.

Bei mehr als vier Pfefferkuchen wird’s kritisch

Wir kennen die Größe des kleinsten quadratischen Containers, in den wir bis zu 10 quadratische Paletten packen können. Aber wenn wir nur eine zusätzliche Palette hinzufügen, wird es unmöglich, die optimale Größe des Containers zu berechnen. Abrahamsen erklärt:

„Wenn mehr Paletten hinzugefügt werden, steigt die Berechnungszeit über-exponentiell an. Da können nicht einmal die besten Computer mithalten. Theoretisch ist es möglich. Aber basierend auf der Geschwindigkeit, mit der die Rechenleistung wächst, wird es wahrscheinlich Millionen von Jahren dauern, bis wir in der Lage sind, das Handling von ein paar zusätzlichen Objekten zu optimieren.“

Links: Optimale Platzierung von fünf quadratischen Kisten oder Weihnachtsplätzchen. Rechts: Die derzeit platzsparendste Anordnung von elf Einheitsquadraten in einem größeren Quadrat. Foto: Mikkel Abrahamsen, Universität Kopenhagen

Außerdem, wenn man mit komplizierteren Formen arbeitet, wie zum Beispiel Lebkuchenmännchen oder Weihnachtsbaum-Plätzchen steigt der Rechenaufwand enorm. Laut Abrahamsen steigen dann auch die besten Computer bei mehr als vier Weihnachtsplätzchen aus.

Sowohl in der Weihnachtsbäckerei als auch beim Beladen von Containern gibt es also keine besseren Lösungen für Packprobleme als die, die wir Menschen uns ausdenken können.

Eine unendliche Anzahl von Weihnachtsplätzchen

Was macht es so schwierig? Das Problem ähnelt laut Abrahamsen dem Lösen von Gleichungen fünften Grades oder höher und mit vielen Unbekannten. Hier ist bekannt, dass eine solche Lösung nicht immer mit regulären Rechenoperationen aufgeschrieben werden kann.

„Unsere Studie beweist, dass das Problem eine Natur hat, die wir in der Mathematik als kontinuierlich bezeichnen“, erklärt Abrahamsen. Mit anderen Worten: Man muss alle Stellen und Winkel kennen, an denen Weihnachtsplätzchen platziert beziehungsweise, in die sie gedreht werden können“.

Da die möglichen Kombinationen unendlich sind, ist es unmöglich eine Liste aller Möglichkeiten zu erstellen, die man ausprobieren muss, um eine optimale Packlösung zu finden. Stattdessen müssen Algorithmen das Packproblem eher analytisch vorgehen. Das ist zeitaufwändig und steht im Gegensatz zu vielen anderen bekannten algorithmischen Problemen. Häufig kann man eine begrenzte – wenn auch ungeheuer große – Anzahl von Kombinationen ausprobieren, um DIE optimale zu finden.

„Sowohl in der Industrie als auch an der Küchentheke müssen wir uns weiterhin mit unseren weniger als optimalen Lösungen zufriedengeben“, schließt Prof. Abrahamsen, „und uns darauf verlassen, dass wir Menschen für diese Art von Aufgaben – bis auf Weiteres – immer noch besser sind als Computer.“

(Mit Material der Universität Kopenhagen)