Das Rucksackproblem

Letztmalig dran rumgefummelt: 01.06.17 13:38:08

	... gestoßen auf das Rucksackproblem ohne es bereits so zu nennen, sind die Alliierten bei den Vorbereitungen zur Landung in der Normandie. Rucksackproblem ist die klassische Kompromisslösung schlechthin - denn alles geht nicht!
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren Logo für das Rucksackproblem Wissen für Fortgeschrittene der Informatik Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???

1. Problembeschreibung

	Wie alle unsere
	In zwei Monaten startet die nächste Rakete zur Raumstation. Die Weltraumagentur ist etwas knapp bei Kasse und bietet deshalb kommerziellen Forschungsinstituten an, wissenschaftliche Experimente an der Raumstation durchzuführen zu lassen. Die Rakete kann neben den obligatorischen Verpflegungsrationen noch maximal 645 kg zusätzliche Last mitnehmen, die für die Experimente benutzt werden soll. Die Weltraumagentur erhält von den Forschungsinstituten verschiedene Angebote, in denen steht, wie viel Geld sie für den Transport und die Durchführung des Experiments zu zahlen bereit sind und wie schwer die Geräte für ihr Experiment sind. Welche Experimente soll die Weltraumagentur auswählen, wenn sie den Profit maximieren will? Hinter diesem Szenario verbirgt sich ein klassisches Problem der Optimierung, das so genannte Rucksackproblem: Wir stellen uns vor, dass wir einen Rucksack haben, der höchstens ein bestimmtes vorgegebenes Gewicht T trägt. T wird als Gewichtsschranke bezeichnet. Neben dem Rucksack gibt es eine Menge von n Objekten (Gegenständen), die jeweils ein Gewicht und einen Profit haben. Wir suchen eine Teilmenge der Objekte, die wir in den Rucksack packen können, ohne die Gewichtsschranke T zu verletzen, so dass der Gesamtprofit möglichst groß ist, also die Summe der Profite der eingepackten Objekte maximiert wird. Im obigen Beispiel steht der Rucksack symbolisch für die Rakete und hat eine Gewichtsschranke von T = 645. Die Objekte repräsentieren die Experimente. Wir konkretisieren dieses Beispiel und stellen uns vor, dass n = 8 Objekte (Experimente) mit den folgenden Gewichten und Profiten vorliegen. Objekt-Nr. 1 2 3 4 5 6 7 8 Gewicht in kg 153 54 191 66 239 137 148 249 Profit in 1000 Euro 232 73 201 50 141 79 48 38 Profitdichte 1.52 1.35 1.05 0.76 0.59 0.58 0.32 0.15 Intuitiv erscheint es sinnvoll, diejenigen Objekte zuerst auszuwählen, die den größten Profit pro Gewichtseinheit erzielen. Dieses Verhältnis zwischen Profit und Gewicht eines Objektes bezeichnet man auch als Profitdichte. Wir haben in der Tabelle die Profitdichten berechnet und die Objekte bereits so in der Tabelle angeordnet, dass die Profitdichte von links nach rechts immer kleiner wird. Unser erster Algorithmus startet mit dem leeren Rucksack und fügt die Objekte nacheinander in den Rucksack ein. Dabei berücksichtigen wir zunächst die Objekte, die eine höhere Profitdichte haben. Wir stoppen, sobald das nächste Objekt nicht mehr in den Rucksack passt. In unserem Beispiel würden wir also nacheinander die Objekte 1, 2, 3 und 4 einpacken. Diese haben zusammen ein zulässiges Gewicht von 464. Nummer 5 können wir nicht mehr einpacken, da dann das Gesamtgewicht mit 464 + 239 = 703 die Kapazität des Rucksacks von 645 überschreitet. Die vier Objekte im Rucksack erzielen zusammen einen Profit von 556. Ist das die beste Möglichkeit den Rucksack zu packen? Offensichtlich nicht, denn wir könnten zusätzlich noch Nummer 6 einpacken. Dann enthält unser Rucksack ein Gewicht von 601 und erzielt einen Profit von 647. Ist dies nun die beste Lösung? - Leider nein! Um garantiert die beste Lösung zu finden, kann man einfach alle möglichen Kombinationen den Rucksack zu bepacken ausprobieren. Leider gibt es sehr viele Kombinationsmöglichkeiten. Für jedes Objekt ist zu entscheiden, ob es in den Rucksack gepackt wird oder nicht. Pro Objekt sind das zwei Möglichkeiten. Bei n Objekten ergeben sich insgesamt 2n Kombinationsmöglichkeiten. In unserem Beispiel sind das 28 = 256 Möglichkeiten, die überprüft werden müssen. Wir können all diese Kombinationen graphisch in einem Gewicht-Profit Diagramm darstellen: Für jede Teilmenge von Objekten zeichnen wir entsprechend ihres Gewichts und ihres Profits einen Punkt, zum Beispiel für die Teilmenge {1,2,3,4,6} den Punkt (601,647). Verteilung der möglichen Gepäckkombinationen
	Jeder Punkt repräsentiert eine Möglichkeit den Rucksack zu packen. Allerdings sind diejenigen mit Gewicht größer als 645 zu schwer für den Rucksack. Das sind gerade die Punkte, die rechts von der roten Linie sind. Punkte, die links oder auf der schwarzen Linie liegen, sind zulässig. Von all den zulässigen Punkten möchten wir denjenigen mit dem größten Profit auswählen. Dieser Punkt entspricht der Teilmenge mit den Objekten 1, 2, 3 und 5, die zusammen Gewicht 637 und Profit 647 haben. Diese ist die so genannte optimale Lösung. Man kann die optimale Lösung offensichtlich finden, indem man alle Teilmengen ausprobiert. Dieser Algorithmus hat allerdings einen großen Nachteil. Steigt die Anzahl der Objekte nur leicht an, so "explodiert" die Anzahl der Teilmengen. Erhält die Weltraumagentur in unserem Beispiel 60 Angebote für Experimente, so gibt es bereits 260 = 1.152.921.504.606.846.976   also mehr als eine Trillion) verschiedene Möglichkeiten, eine Auswahl zu treffen. Wenn man optimistisch annimmt, dass ein Computer eine Milliarde Teilmengen pro Sekunde testen kann, so benötigt er trotzdem noch über 36 Jahre, um alle Teilmengen durchzuprobieren. So lange wollen wir den Start der Rakete aber nicht verzögern. Pareto-optimale Punkte Wie kann man die optimale Lösung schneller finden? Die Grundidee für einen effizienteren Algorithmus basiert auf folgender Beobachtung: Eine Teilmenge von Objekten kann nicht optimal sein, wenn es eine andere Teilmenge gibt, die leichter (oder gleich schwer) ist und gleichzeitig einen größeren Profit hat. Eine solche Lösung wäre unabhängig von der Gewichtsschranke des Rucksacks immer besser. Schauen wir noch mal auf unser Beispiel:   Verteilung der möglichen Gepäckkombinationen
	Die blauen Punkte können nicht optimal sein, da wir für jeden blauen Punkt einen noch besseren Punkt finden können, nämlich einen solchen, der weiter oben und weiter links im Diagramm ist. Zu den roten Punkten gibt es hingegen keine anderen Punkte, die links oberhalb dieser Punkte liegen. Derartige Punkte heißen Pareto-optimal. Eine Teilmenge heißt somit Pareto-optimal, wenn es keine andere Teilmenge gibt, die leichter (oder gleich schwer) ist und gleichzeitig einen größeren Profit hat. Nur die 17 roten Punkte entsprechen Pareto-optimalen Teilmengen. Bei der Suche nach der besten Lösung können wir uns also auf die Pareto-optimalen Teilmengen beschränken. Aber wie kann man eine Liste aller Pareto-optimalen Teilmengen berechnen, ohne explizit alle möglichen Teilmengen auszuprobieren? Betrachten wir das folgende kleine Beispiel mit zunächst nur drei Objekten. Die 23 = 8 verschiedenen Teilmengen sind wieder in ein Gewicht-Profit-Diagramm eingezeichnet. Was passiert, wenn man ein zusätzliches viertes Objekt zur Auswahl hat? Jede der 8 Teilmengen im Diagramm kann man erweitern, indem das vierte Objekt hinzufügt wird. Somit erhalten wir 8 neue Teilmengen. Jeder blaue Punkt im Diagramm erzeugt also einen neuen schwarzen Punkt, der jeweils um denselben Betrag nach rechts oben verschoben ist. Die Verschiebung nach rechts entspricht dem Gewicht, die nach oben dem Profit des zusätzlichen vierten Objektes. Die schwarze Punktmenge ist also nur eine verschobene Kopie der blauen.  Welche Punkte sind nun Pareto-optimal? Betrachten wir einen blauen Punkt, der nicht Pareto-optimal ist. Dieser wird natürlich auch nicht Pareto-optimal, wenn noch die schwarzen Punkte hinzukommen. Auch der schwarze Punkt, der aus ihm erzeugt wurde, kann nicht Pareto-optimal sein, da man für ihn ja einen anderen besseren schwarzen Punkt finden kann. Man braucht somit nur die Pareto-optimalen blauen Punkte und die aus ihnen erzeugten schwarzen Punkte zu berücksichtigen. Aus der Liste der Pareto-optimalen Punkte für drei Objekte lässt sich also leicht die Liste für vier Objekte konstruieren. Allgemein, wenn man die Liste für eine Zahl i von Objekten hat, kann man daraus die für ein Objekt mehr, also i+1 Objekte konstruieren: Als erstes erzeugt man dazu alle schwarzen Punkte, die aus den blauen Pareto-optimalen Punkten hervorgehen. Nun muss man diejenigen blauen Punkte löschen, die einen der erzeugten schwarzen Punkte links oberhalb von sich haben und somit nicht mehr Pareto-optimal sind. Umgekehrt muss man nun noch die schwarzen Punkte löschen, die einen blauen Punkt links oberhalb von sich haben. Für i = 0, wenn also gar kein Objekt zur Auswahl steht, gibt es nur den Punkt (0,0), der dem leeren Rucksack entspricht. Dieser Algorithmus wurde schon 1969 von Nemhauser und Ullmann erfunden.

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Unter Annahme der Tatsache, dass wir nicht die Kaprekartiefe, sondern die Regelmäßigkeit der Wiederkehr der einzelnen Werte selbiger suchen, fällt die Aufgabe heute typischerweise in den Bereich der nicht entscheidbaren Probleme. Und diese Beschreibung selbst zu finden, dürfte dann schon in die Klasse der komplexen Probleme fallen.

3. Lösungsalgorithmen

	Für kleine und überschaubare Mengen an Einzelkomponenten ist die Lösung einfach - bei nur einem Teile steht lediglich die Frage, kann ich es überhaupt mitnehmen oder nicht. Bewertungen stehen im Falle dessen, dass es mitgenommen werden kann, nicht an. Mit zwei Komponenten, bei denen wir mindestens davon ausgehen, dass beide einzeln mitgenommen werden können, gibt es Möglichkeiten.
	... das Schatztruhenproblem   Lösungsansatz 1     das Schatztruhenproblem zum ersten ... das Schatztruhenproblem zum ersten ... das Schatztruhenproblem zum zweiten ... das Schatztruhenproblem zum zweien ...     ... die Sache mit der Schatztruhe
	... technische Lösungsansätze Lösungsansatz 1 Lösungsansatz 2     das Rucksackmodell zum ersten ... das Schatztruhenproblem zum ersten ... das Rucksackmodell zum ersten ... das Schatztruhenproblem zum ersten ... das Rucksackmodell in EXCEL ... das Rucksackmodell in EXCEL ... das Rucksackmodell mit zusätzlichen Gewichtsbetrachtungen ... das Rucksackmodell mit zusätzlichen Gewichtsbetrachtungen ... ... die Sache mit dem Rucksack Einpacken

4. Programmvorschläge

	Hannes Uhlig hat unser Vorschläge konsequent aufgegriffen und einschließlich der Problematik Oma und Katze ein Programm des Kaprekar-Algorithmus notiert, in welchem schon einige Kerngedanken eines sauberen - eben noch nicht objektorientierten Programmieirstils zusammenlaufen.

5. Zusammenfassung

6. Weiterführende Literatur

7. Links zum Thema

	http://www.mathematische-basteleien.de/kaprekarzahl.htm

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im Mai 2005