Wie den Platz so gut wie möglich nutzen? Darüber werden sich auch heuer wieder Urlauber und Urlauberinnen vor ihren Koffern stehend die Köpfe zerbrechen. Für die optimale Nutzung von Raum kann ein Algorithmus von Nutzen sein, der unterschiedliche Formen in einem möglichst kleinen Raum anzuordnen versucht. Solche Algorithmen beschäftigen sich mit dem Problem der optimalen Anordnung bzw. mit dem "Packing-Problem".

Was zunächst nach einer komplexeren Version des Videospiels "Tetris" klingt, kann auch zur Lösung von Problemen in der realen Welt beitragen. Die Effizienz beim Anordnen oder Packen kann sowohl Kosten senken als auch den Transport diverser Güter ökologischer gestalten.

Optimale Ergebnisse

Um herauszufinden, welche Algorithmen helfen können, um verfügbaren Platz optimal zu nutzen, haben WissenschafterInnen ihre Algorithmen gegeneinander in einen Wettbewerb geschickt, bei dem spezielle "Packing-Problems" zu lösen waren. Zum Beispiel das Problem, wie eine Menge von unterschiedlich großen Scheiben in einen Kreis passt, ohne sich zu überlappen.
Das Team von Johannes Schneider an der Universität von Mainz hat alle bisherigen Rekorde zu dem Problem der Scheiben-Anordnung gebrochen, wie in "NewScientist" berichtet wird.

Anordnung von Scheiben

Die Anforderungen für den Wettbewerb wurden in früheren Wettbewerben mit 155 Gruppen aus 32 Ländern definiert. Der Algorithmus von Schneiders Team ist gleich schnell wie alle bisherigen - zumindest was die Anordnung von bis zu 23 Scheiben in einem Kreis betrifft. Schneller als alle anderen ist der Algorithmus allerdings für 26 bis 50 Scheiben.

Bisherige Algorithmen haben die Scheiben immer wieder von neuem gemischt, um eine effiziente Nutzung des Raumes zu erreichen. Das Geheimnis des Erfolges des "Rekord-Algorithmus" besteht darin, dass es auch die Möglichkeit gibt, einen Schritt zurückzugehen. Wenn eine Lösung für eine Anordnung gefunden wurde, werden somit beispielsweise Teillösungen beibehalten, andere Teile aber wieder herausgenommen und es werden wieder neue Versuche zur Anordnung gestartet.

Einfach nur bergauf?

Die oben beschriebene Vorgehensweise, ständig eine neue Zusammenstellung zu versuchen, erinnert laut Schneider eher an folgendes Szenario: Ein Alpinist versucht den höchsten Punkt auf der Erde zu finden, indem er immer bergauf geht und stehenbleibt, wenn es nicht mehr bergauf geht. Dann würde der Alpinist wahrscheinlich einfach auf dem nächstgelegenen Hügel landen und dort festsitzen - und es wäre reiner Zufall, wenn der Alpinist seinen Aufstieg gerade am Fuße des höchsten Berges der Welt beginnen würde.

Dadurch, dass die Algorithmen von Schneider und seinem Team erlauben, auch einen Schritt zurück zu gehen, können bessere Lösungen erreicht werden. Vollständig gelöst wurde das Problem der effizientesten Anordnung mit diesem Algorithmus nicht, aber es ist im Moment zumindest die beste Lösung.

3D-Szenarios

Marco Locatelli von der Universität Turin gehört zu dem Team, das die meisten bisherigen Rekorde - bevor Schneiders Team auf den Plan trat - hielt. Er sieht die Möglichkeit eines Rücksetzverfahrens als einen Hauptgrund für den erfolgreichen Ansatz, und die Herausarbeitung solcher Rückwärtsbewegungen sei bestimmt ein Verdienst. Aber die Algorithmen verbessern sich schnell und Rekorde halten sich selten lange, so Locatelli skeptisch gegenüber "NewScientist" über die aktuellen Rekordhalter. Interessant fände er 3D-Szenarios, welche Schneiders Team künftig auch untersuchen möchte.

"Wir haben jetzt einen Algorithmus, der Probleme mit 3D-Gütern von verschiedenen Größen löst", so Schneider. Somit werden derartige Probleme auch für die reale Welt relevant. Beispielsweise sehen sich Transportfirmen mit dem Anspruch konfrontiert, in Paket-Transportern oder Schiffen so viele Güter wie möglich unterzubringen.

Auch die Reihenfolge - zuzüglich zur Anordnung - von 3D-Objekten zu berücksichtigen ist relevant für reale Probleme. Beispielsweise, wenn ein Paket-Laster so gepackt sein soll, dass Pakete der Reihe nach an Kunden und Kundinnen ausgeliefert werden können, ohne in die hinterste Ecke des LKW kriechen zu müssen. (beaha, derStandard.at, 11.3.2009)