Knobelkiste: Rucksack, Affenpuzzle, Damen
Fassung:
Knobelkiste: weitere schwere Probleme
Viele Probleme aus Alltag, Logistik und Spielen haben dieselbe Struktur: Es gibt riesig viele Möglichkeiten, Brute Force ist zu langsam, und man greift zu Heuristiken.
Das Rucksackproblem
Für eine Wanderung passen höchstens 10 kg in deinen Rucksack. Jeder Gegenstand hat ein Gewicht und einen Nutzen (Wert). Welche Gegenstände nimmst du mit, damit der Gesamtwert möglichst groß ist?
Rucksack packen
Aufgabe 1: Packe den Rucksack mit dem größtmöglichen Wert.
Eine Greedy-Heuristik: Berechne für jeden Gegenstand den Wert pro kg. Packe die Gegenstände in der Reihenfolge vom größten zum kleinsten Wert pro kg ein – jeden, der noch passt.
Rucksack nach Wert pro kg
Aufgabe 2: Packe den Rucksack nach der Wert-pro-kg-Heuristik. Vergleiche mit Aufgabe 1.
Wie viele Möglichkeiten gibt es?
Brute Force müsste jede mögliche Auswahl prüfen. Wir zählen sie Schritt für Schritt:
| Gegenstände | mögliche Auswahlen | Anzahl |
|---|---|---|
| Zelt | ohne Zelt · mit Zelt | 2 |
| Zelt, Stirnlampe | nichts · nur Zelt · nur Stirnlampe · beides | 4 |
Lückentext
Aufgabe 3: Mit einem dritten Gegenstand gibt es
mögliche Auswahlen, mit 4 Gegenständen
, mit 6 Gegenständen
und mit 7 Gegenständen
. Jeder weitere Gegenstand
die Zahl der Möglichkeiten.
Rückblick
- Ein Problem ist allgemein beschrieben, eine Probleminstanz hat konkrete Daten.
- Eine zulässige Lösung erfüllt alle Bedingungen der Instanz. Die optimale Lösung ist die zulässige Lösung, die in Bezug auf ein festgelegtes Kriterium die beste ist.
- Kleine Instanzen von Hand zu untersuchen, zeigt Eigenschaften eines Problems (z. B. Symmetrien) und führt zu ersten Lösungsideen.
- Brute Force probiert alle Möglichkeiten und findet die optimale Lösung – bei großen Instanzen aber viel zu langsam.
- Greedy-Algorithmen wählen in jedem Schritt das im Moment Beste. Bei kürzesten Wegen (Dijkstra) und Spannbäumen (Kruskal) ist das optimal, bei den Kameras, beim Färben, beim Handlungsreisenden und beim Rucksack nur eine Heuristik: schnell, aber nicht immer optimal.
- Der Aufwand entscheidet, ob ein Verfahren in der Praxis taugt.