Wissenschaftssommer 2008

Bin Packing (exakt und approximiert)

Die Aufgabe(n)

Aufgabe (exakte):
Gegeben sind eine Menge von unterschiedlich großen Gegenständen sowie eine Anzahl von Behältern übereinstimmender Größe. Kann man die Gegenstände in die Behälter packen? Kein Gegenstand darf geteilt werden, kein Behälter darf überlastet werden.
Aufgabe (approximiert):
Wähle die Gegenstände so aus, daß man bei Vorgehen streng nach den folgenden Verfahren eine möglichst schlechte Näherungslösung (für die Anzahl der benötigten Behälter) erhält:

  • First Fit: packe der Reihe nach jeden Gegenstand in den ersten Behälter, der ihn noch faßt.
  • First Fit Decreasing: wie eben, aber sortiere die Gegenstände vorher absteigend.

Mathematischer Hintergrund

Man kann die Gegenstände zunächst beliebig den Behältern zuordnen und dann prüfen, ob alle Bedingungen erfüllt sind, d. h. kein Behälter überladen ist.
Das Problem gehört damit zur Komplexitätsklasse NP (dabei bedeuten sinngemaß: N = man muß die Zuordnung raten, P = man kann für jede Zuordnung die Erfüllung der Bedingungen schnell prüfen). Man kann sogar zeigen, daß Bin Packing ein NP-vollständiges Problem ist.
Wenn man ein NP-Problem durch Probieren aller Zuordnungen lösen möchte, braucht man dafür sehr viel (genauer: exponentiell viel) Zeit. Ein solches Verfahren ist nicht effizient.
Man ist deswegen unter Umständen mit Näherungslösungen zufrieden, wenn diese nicht allzuweit von der Wahrheit abweichen und sich schnell (d. h. in Polynomialzeit) berechnen lassen.

Anwendungen

Viele praktische Fragen der Ressourcenzuordnung, z. B. von Bearbeitungs- oder Transportkapazitäten oder bei der Stunden- und Raumplanung, führen auf NP-vollständige Probleme. Das entspricht der Erfahrung: solche Aufgaben sind schwer exakt zu lösen. Man läßt es nun nicht mit der Feststellung «NP-vollständig, also zu schwer» bewenden, sondern untersucht schnelle Heuristiken, die einige (hoffentlich häufige) Fälle exakt oder alle Fälle angenähert lösen.

Komplexitätsklasse: NP
Selber Ausprobieren:Hier klicken!
Weitere Infos:- TGInf - PSPACE (Skript)
- Sonstwas
Quellen / Fußnoten:[1]Michael R. Garey und David S. Johnson:
Computers and Intractability, Freeman, 1979

© HTWK