Kapitel 3 - Ich packe meinen Koffer und ....pdf

3. Ich packe meinen Koffer und... Es war einmal ein tapferer Mann aus dem Volk, der rettete die Prinzessin Tausend- schön vor dem Räuber Abi Lala und seinen zweiundvierzig Schergen. Leider musste sich der König nun etwas als Belohnung ausdenken: Wäre der Mann ein Prinz ge- wesen, hätte er ihm einfac...

3. Ich packe meinen Koffer und... Es war einmal ein tapferer Mann aus dem Volk, der rettete die Prinzessin Tausend- schön vor dem Räuber Abi Lala und seinen zweiundvierzig Schergen. Leider musste sich der König nun etwas als Belohnung ausdenken: Wäre der Mann ein Prinz ge- wesen, hätte er ihm einfach die Hand der Prinzessin anbieten können. Für einen ge- wöhnlichen Bürger würde der König aber wohl oder übel seine Schatzkammer öffnen müssen. Um den Schaden jedoch zu begrenzen, gab der König dem Mann eine Holzkiste und sprach: „Du darfst dir alles aus der Schatzkammer nehmen, was in die Kiste passt, so dass sich der Deckel noch schließen lässt.“ Er dachte, dass jener sicher so von den Schätzen geblendet wäre, dass er eher billigen Tand als wirklich wertvolle Stücke aus- wählen würde. Hier hat er jedoch nicht mit unserer Beteiligung gerechnet! Die Informatik hat dem Mann aus dem Volk sogar eine eigene Kategorie von Aufgaben gewidmet, genannt „Rucksackprobleme“. Das Rucksackproblem Bereits in den vorherigen Kapiteln haben wir sehr viel mit Abstraktion gearbeitet und das Problem zunächst vereinfacht, um darüber besser nachdenken zu können. Hier nehme ich diesen Schritt schon jetzt vorweg und biete Ihnen die gesammelten „abs- trakten“ Schätze als Bastelbogen oder Kopiervorlage 3.K1 – rechteckig und aus einer glatten Zahl von Quadraten zusammengesetzt. Schneiden Sie sie aus und versuchen damit, die Kiste am Buchrand möglichst op- timal zu füllen. Wir gehen hier einfach davon aus, dass jedem Schatz ein Zertifikat mit einem genauen Wert (selbstverständlich einheitlich in Golddublonen bemessen) beiliegt – dieser steht als ganze Zahl neben der Abbildung. Die sogenannten „Trivialfälle“ sind hier übrigens bereits eliminiert: Nehmen wir an, es existierten zwei Gegenstände mit exakt der gleichen Größe, aber unterschiedlichem Wert. Dann legt man selbstverständlich den billigeren Gegenstand im Vorfeld bereits als „uninteressant“ ab. Daher steht hier nur ein Objekt pro Größe zur Wahl (eben das jeweils teuerste). Sie sehen bereits an dem einfachen Beispiel, dass es gar nicht so einfach ist, das Opti- mum aus allen Möglichkeiten herauszufinden: Es passen sechs Edelsteine in die Kis- te, aber auch eine Vase und zwei Ringe. Vielleicht sind aber drei Münzen wertvoller? Oder gar die goldene Waage – dann passt aber sonst nicht viel mehr in die Kiste... Wie auch bereits zuvor, können wir hier die Lösung durch stures Ausprobieren finden: Alle Möglichkeiten werden systematisch durchgegangen, die wertvollste Kombination wird beibehalten. Das ist für das vorliegende Beispiel machbar, aber bereits sehr zeit- 85  aufwendig. Überlegen Sie, wie viele Möglichkeiten Sie bereits hätten, wenn die Kiste auch nur doppelt so groß wäre... Abbildung 3.1 Gefüllte Schatzkiste mit einem Wert von 54 Dublonen. 43 11 Geht das noch besser? Über die Problematik des sturen Probierens hatten wir bereits im Kapitel über Routen- planung philosophiert, das möchte ich an dieser Stelle nicht wiederholen. Allerdings versichere ich Ihnen, dass der Aufwand zum Probieren hier mit der Größe der Kiste ebenfalls sehr stark anwächst. Die Lösungsansätze werden damit schnell unübersicht- lich und sind zumindest in sinnvoller Zeit nicht zielführend. Mehr ist weniger Statt herumzuprobieren wollen wir daher das Problem konsequent angehen. Eine ent- Divide et impera „Teile und herrsche“ – er- scheidende Strategie der Informatik haben Sie ja bereits mit „divide et impera“ ken- innern Sie sich noch daran? nengelernt: Wenn das Gesamtproblem zu groß zum Lösen ist, versuchen wir es in Wenn nicht: In Kapitel 2 wird kleinere Pakete zu zerteilen. Das machen wir so lange, bis die Teilprobleme handhab- dieses Prinzip ausführlich bar klein sind. erörtert. Um das Problem in kleinere Happen zu unterteilen, müssen wir allerdings zunächst feststellen, wodurch überhaupt ein Problem dieser Art als „groß“ oder „klein“ gilt – wir bestimmen die Problemgröße. Beim Routenplaner ist das zum Beispiel die Anzahl der Orte auf einer Landkarte, beim Sortieren die Anzahl der zu sortierenden Objekte. Ihre Aufgabe: Überlegen Sie, was beim Packen des Rucksacks die Problemgröße ist. ▶ ▶ ▶ ◀ ◀ ◀ Zugegeben: Die Frage war vielleicht ein wenig unfair formuliert, aber ansonsten hätte ich schon zu viel verraten. Sie sind bestimmt trotzdem auf die korrekte Antwort ge- kommen. Ist „Größe der Kiste“ vielleicht eine Problemgröße? Ist „Anzahl unterschiedlicher Gegenstände“ vielleicht eine Problemgröße? Beides ist richtig: Wie bereits oben ausgeführt, wird eine Lösung immer schwieriger, je größer die Kiste ist und je mehr Gegenstände man daher gleichzeitig einpacken muss (das gilt übrigens nur, wenn man wirklich an einer exakten Lösung interessiert ist, aber dazu mehr weiter unten). Zusätzlich steigt die Problemgröße selbstverständ- lich auch an, wenn man mehr unterschiedliche Gegenstände zur Wahl hat und aus- probieren muss. Sie können Ihre Vermutung über eine Problemgröße normalerweise leicht untermau- ern: Überlegen Sie, welches das „kleinste Problem“ ist, wenn Sie Ihre Überlegungen zugrunde legen. „Größe der Kiste“: Nehmen Sie eine sehr kleine Kiste, zum Beispiel die nebenstehen- de. Ist hier die Lösung des Problems besonders schwierig? Nein, denn es gibt über- haupt nur zwei Möglichkeiten: 86 3. Ich packe meinen Koffer und...  die Kiste leer lassen (und das wäre wirklich dumm) oder einen Edelstein hineinladen, was immerhin sechs Dublonen bringt. „Anzahl unterschiedlicher Gegenstände“: Benutzen Sie immer die große Kiste, aber gehen Sie davon aus, in der Schatzkammer befände sich nur eine einzige Sorte Schatz, zum Beispiel Edelsteine. Auch in diesem Fall gibt es nicht viel zu entscheiden: Man lädt so viele Edelsteine in die Kiste, wie hineinpassen. Abbildung 3.2 zeigt eine solche Kiste. Abbildung 3.2 7 7 7 7 7 7 Schatzkiste nur mit Edelstei- nen, immerhin 42 Dublonen wert Beim Sortieren von Karten war eine mögliche Vorgehensweise, mit einer einzelnen Karte anzufangen (die per Definition sortiert ist). Dann wurde die Problemgröße je- weils um eine Karte erweitert, die in die bereits sortierte Folge leicht eingefügt werden konnte. Vielleicht finden Sie ja auf dieser Basis auch eine Lösung für das Rucksackprob- lem? Versuchen Sie es: Fangen Sie mit kleinen Kisten oder wenigen unterschiedli- chen Objekten an und erhöhen Sie dann die Problemgröße langsam. ▶ ▶ ▶ ◀ ◀ ◀ Die Lösung gestaltet sich schwieriger als erwartet: Fängt man mit einer kleinen Kiste an und steigert deren Größe, kommt man recht schnell auf optimale Ergebnisse für Kisten mit 2, 3, 4 und 5 Quadraten (wir nennen diese fortan 2er-Kiste, 3er-Kiste usw. oder Kisten der Größen 2, 3, 4 usw.). Danach fängt das Rätseln an: Welche der Teillösungen müssen kombiniert werden, um eine noch größere Kiste zu packen? Auch hier können wir nur alle Möglichkeiten auspro- bieren, was uns zum Ausgangspunkt unserer Betrachtungen zurückwirft. Versuchen wir also, gleich die große 13er-Kiste zu nehmen, fangen aber zunächst an, sie ausschließlich mit Edelsteinen zu füllen, wie schon in Abbildung 3.2 gezeigt. Da- nach erweitern wir die Problemgröße: Auch Ringe sind nun erlaubt. Recht schnell kann man feststellen, dass vier Ringe (mit 44 Dublonen Wert) besser sind als die sechs Goldbarren (die nur 42 Dublonen wert waren). Offenbar sind also Edelsteine nicht so günstig wie Ringe, wir können sie also für die folgenden Betrachtungen außer Acht lassen. Weiter geht es und auch die Goldtaler mit 16 Dublonen Wert sollen nun im Angebot sein. Wiederum können wir den Wert unserer Kiste steigern, indem wir die Ringe entsorgen und stattdessen drei Goldtaler einladen. 48 Dublonen sind nun das Ergebnis. Als Nächstes nehmen wir den wertvollen Kompass hinzu, der so ausladend ist, dass er fünf Plätze ausfüllt. In unsere Kiste passen daher nur zwei Kompasse mit einem Ge- samtwert von 48 Dublonen. Das ist genauso viel, wie wir bereits haben. Daher bleiben wir bei den Goldtalern, oder? Ganz so einfach ist es nicht, denn legen wir zu den zwei Kompassen noch einen Ring (was gut passt), steigt der Wert unserer Kiste sogar auf 59. Unsere Entscheidung, die Ringe als „zu billig“ außer Acht zu lassen, war also ziemlich voreilig! Auch mit die- sem Lösungsansatz müssen wir im späteren Verlauf der Problemlösung immer wieder Mehr ist weniger 87  ganz an den Anfang zurückspringen, um das Optimum herauszuholen, was effektiv auch einfach das Durchspielen aller Möglichkeiten bedeutet. Ist hier also „divide et impera“ gar nicht zu gebrauchen? Müssen wir uns bei diesem Problem geschlagen geben? Selbstverständlich nicht: Die Informatik hat noch ein paar Tricks auf Lager. In diesem Fall heißt der Trick: „Mehr ist weniger“, oder anders gesagt „Wenn man mehr Proble- me löst, hat man letztlich weniger Arbeit.“ Wie ist das genau zu verstehen? Das Teilen von Problemen ist manchmal schwierig und man weiß nicht genau, welche Teilprobleme man genau lösen muss, um sie dann zu einer Gesamtlösung zu kombinieren. In solchen Fällen ist es manchmal hilfreich, einfach alle möglichen Teilprobleme zu lösen und danach zu entscheiden, welche man kombiniert. So etwas nennt man dynamische Programmierung. Dynamische Programmierung Strategie zur Lösung komplexer Probleme, besonders zur Lösung von Optimie- rungsaufgaben. Man löst zunächst viele Teilprobleme und verwendet diese Bau- steine – optimale Zwischenergebnisse –, um die nächstgrößeren Probleme zu lösen usw., bis das Gesamtproblem gelöst ist. Um dieses Prinzip auf unser Rucksackproblem anzuwenden, benötigen wir viele Kis- ten: von einer ganz kleinen Kiste (mit überhaupt keinem Platz darin) bis zur größten Richard Ernest Bellman Kiste mit 13 Quadraten Platz. Sie finden dies im Bastelbogen und Abbildung 3.K2 – (1920 – 1984) studierte Ma- sogar mit zwei weiteren Feldern für Ihre eigenen Experimente. Ich nenne das Gebilde thematik und beschäftigte im Folgenden „Maxikiste“, da die Kisten aller ganzer Größen enthalten sind. sich danach mit theoretischer Physik. Ab 1952 befasste er Jetzt fangen wir ganz klein an: Gehen Sie davon aus, es gäbe nur die kleinste Sorte sich dann bei der Rand-Cor- poration mit Optimierungs- Schatz zur Auswahl – Edelsteine. Gemäß dem Prinzip der dynamischen Programmie- problemen und adaptierte ein rung ermitteln wir nun für den anderen Typ Problemgröße – die Kistengröße – nicht vorher nur von Physikern ver- nur eine Lösung, sondern gleich alle bis zur Größe 13. Die entsprechenden Kisten wendetes Prinzip für die In- finden wir in der Maxikiste. formatik, das er „dynamische Programmierung“ nannte. Mit nur einer Sorte Schatz ist es leicht, die Kisten entsprechend optimal zu füllen. Heute ist ein Algorithmus zur Machen Sie das! Zur Verdeutlichung können Sie links auf Klebezetteln daneben Erstellung optimaler Binär- bäume nach ihm benannt. den Wert jeder Kiste vermerken. ▶ ▶ ▶ ◀ ◀ ◀ Abbildung 3.3 zeigt die Maxikiste. Selbstverständlich kann man in die kleinste Kiste mit der Größe 0 nichts hineingeben. Auch in die Kiste mit nur einem Quadrat Platz passt kein Edelstein – sie bleibt daher frei. Die restlichen Kisten können mit ein bis sechs Edelsteinen gefüllt werden, man stopft einfach so viele hinein, wie passen. Die größte Kiste enthält sechs Barren zu je sieben Dublonen, hat also einen Wert von 42 Dublonen. Um es noch einmal festzuhalten: Die Maxikiste zeigt nun die optimale Lösung mit der kleinsten Problemgröße – nur die kleinsten Schätze dürfen ausgewählt werden. Wie können wir diese Ergebnisse verwenden, um nun den nächstgrößeren Schatz ein- zubeziehen? Diesmal zeige ich Ihnen, was dafür zu tun ist, und wir überlegen hinter- her zusammen, warum diese Strategie sinnvoll ist. 88 3. Ich packe meinen Koffer und...  Abbildung 3.3 Lösung des Rucksackprob- 0 lems bis zur Kistengröße 13, wenn nur Edelsteine zur Wahl stehen 0 7 7 7 7 14 7 7 14 7 7 21 7 7 7 21 7 7 7 28 7 7 7 7 28 7 7 7 7 35 7 7 7 7 7 35 7 7 7 7 7 42 7 7 7 7 7 7 42 7 7 7 7 7 7 Nehmen Sie einen Schatz „Ring“ und legen ihn rechts an die kleinste Kiste an – das ist die Kiste mit Größe 0. Sie haben jetzt sozusagen den neuen Schatz zu der Kiste hinzu- gelegt. In welche (größere) Kiste würden die Inhalte nun passen? Selbstverständlich in die Kiste der Größe 3, wie Sie auch ablesen können, wenn Sie die grünen Linien nach unten verfolgen. Abbildung 3.4 zeigt das. Mehr ist weniger 89  Abbildung 3.4 Den „Inhalt“ der Kiste mit Größe 0 und einen Schatz der 0 11 Größe 3 könnten wir zusam- men in die Kiste der Größe 3 packen. 0 7 7 7 7 14 7 7 Bestimmen 14 Sie nun 7 den Wert 7 beider markierter Zeilen: Der Wert der unteren Zeile steht bereits links davon, er beträgt sieben Dublonen. Der Wert der oberen Zeile ist die Summe aus dem Wert der Kiste (0) und dem Wert des neuen Schatzes – 11 Dublonen. 21gibt nun zwei7Möglichkeiten: Es 7 7 Der Wert der oberen Zeile ist höher. Die neue Kombination aus dem vorigen In- halt der kleineren Kiste plus dem neuen Schatz ist also wertvoller als der vorher 7 21 bestimmte „optimale“ 7 7 ist daher unter Berücksichtigung des neuen Inhalt. Dieser Schatzes nicht mehr optimal, wir tauschen ihn aus gegen die obere Kombination (das heißt, wir entfernen die Schätze aus der Kiste und setzen neue vom Schatz- 7 die untere 28 vorrat ein, bis 7 markierte7 Kiste genau 7 die gleichen Schätze enthält wie die obere plus dem neuen Schatz). Der Wert der oberen Zeile ist nicht höher. Offenbar gilt das alte Optimum auch 28 noch unter 7 7 des neuen Berücksichtigung 7 Schatzes.7 Es wird nichts verändert. Im Beispiel beträgt der Wert der oberen Zeile 11 Dublonen, der Wert der unteren Zeile liegt bei lediglich sieben Dublonen. Es lohnt sich also, die Kiste neu zu packen. 35 7 7 7 7 7 Tun Sie das! Selbstverständlich müssen Sie auch den Wert links von der Kiste auf den neuesten Stand bringen. Das Ergebnis sehen Sie in Abbildung 3.5. Abbildung 3.5 35 7 7 7 7 7 Der „Inhalt“ der Kiste mit Größe 0 und ein Schatz der 0 11 Größe 3 wurden nun in die Kiste der Größe 3 gepackt. 42 7 7 7 7 7 7 0 42 7 7 7 7 7 7 7 7 7 11 11 14 7 7 90 14 7 7 3. Ich packe meinen Koffer und... 21 7 7 7 21 7 7 7  Abbildung 3.6 Ist die vorhandene 4er-Kiste 0 mit zwei Edelsteinen günsti- ger als die neue Kombination aus Ringe und dem (leeren) 0 11 Inhalt der 1er-Kiste? 7 7 7 11 11 14 7 7 Nun 14 verschieben7wir den Schatz 7 um eine Position nach unten und legen ihn rechts an die nächstgrößere Kiste an. Jetzt vergleichen wir den neuen, kombinierten Inhalt mit dem vorhandenen Inhalt der 4er-Kiste. Abbildung 3.6 zeigt das Vorgehen. Wieder 21 vergleichen7 Sie den7Wert der bisher 7 optimalen 4er-Kiste (14) und den Wert der neuen Kombination (11). Diesmal ist die alte Kombination günstiger und Sie ver- ändern den Inhalt der Kisten nicht. 21 wird der7neue Schatz Erneut 7 eine Position 7 nach unten verschoben. Versuchen Sie diesmal, erst selbst die Entscheidung zu treffen, ob Kisteninhalte ausgetauscht werden (und wenn ja, welche). 28 7 7 7 7 ▶ ▶ ▶ ◀ ◀ ◀ 0 28 7 7 7 7 Selbstverständlich ist hier der neue Inhalt vorzuziehen, da er einen Wert von 18 ge- genüber dem vorhandenen Wert von 14 hat. Wieder wird der Ring eine Zeile tiefer geschoben. 0 Nun liegt es an einer Kiste, die wir bereits umgepackt haben. Abbildung 7 35zeigt die Situation. 3.7 7 7 7 7 7 7 35 7 7 7 7 7 Abbildung 3.7 Kann die 6er-Kiste noch güns- tiger gefüllt werden, indem 7 11 11 man den Inhalt der optimalen 42 11 7 7 7 7 7 7 3er-Kiste mit dem Schatz „Ring“ kombiniert? 14 7 7 42 7 7 7 7 7 7 14 7 11 18 21 7 7 7 21 7 7 7 Mehr ist weniger 91 28 7 7 7 7 28 7 7 7 7 35 7 7 7 7 7  Das ist aber gar kein Problem – folgen Sie einfach dem bisherigen Schema und verglei- chen Sie die Kombination mit der 6er-Kiste. Auch hier tauschen wir den Inhalt aus, weil wir eine Verbesserung erzielen, wie in Abbildung 3.8 zu sehen ist. Sehen Sie an diesem Beispiel, dass es klug ist, die Kisten von klein nach groß zu füllen? Auf diese Weise hatten wir bereits die neue, optimal gefüllte 3er-Kiste als Grundlage der Neubetrachtung für die 6er-Kiste zur Verfügung. Wäre in der 3er-Kiste noch der alte Inhalt gewesen (mit sieben Dublonen Wert), hätten wir den Tausch verworfen – eine in diesem Fall ungünstige Variante. Führen Sie nun das Verfahren für die gesamte Maxikiste durch! ▶ ▶ ▶ ◀ ◀ ◀ Das Ergebnis sehen Sie in Abbildung 3.9. Die meisten Kisten enthalten nun einen oder mehrere wertvolle Ringe. Der Übersichtlichkeit halber habe ich die Werte direkt neu eingetragen, ohne die alten auszustreichen. Weiter geht es und der nächstgrößere Schatz – der Goldtaler – steht nun ebenfalls zur Auswahl. Füllen Sie gleich die gesamte Maxikiste neu. ▶ ▶ ▶ ◀ ◀ ◀ Sie sehen das Ergebnis in Abbildung 3.10 auf der nächsten Doppelseite. Die 2er-, 3er- und 5er-Kisten bleiben bestehen, bei allen anderen lohnt es sich, den neuen Schatz einfach oder mehrfach zu verwenden. Bitte richten Sie Ihr besonderes Augenmerk auch auf die Veränderung bei der 6er-Kis- te: Dort war im zweiten Schritt der Edelstein zugunsten zweier Ringe weggefallen. Un- sere Vorgehensweise macht das jedoch keinesfalls endgültig, denn im dritten Schritt 0 wurden die Ringe wieder durch einen Edelstein und einen Goldtaler ersetzt. Als Nächstes ist der Kompass an der Reihe. Wie sieht die optimale Maxikiste nun aus? 0 ▶ ▶ ▶ ◀ ◀ ◀ Abbildung 3.8 7 7 Die 6er-Kiste hat nach dem Tausch des Inhalts einen Wert von 22. 7 11 11 11 14 7 7 14 7 11 18 21 11 11 22 21 7 7 7 92 3. Ich packe meinen Koffer und... 28 7 7 7 7 28 7 7 7 7 35 7 7 7 7 7  Abbildung 3.9 Nun ist auch das Geldbündel 0 als Schatz berücksichtigt. 0 7 7 11 11 14 7 7 18 7 11 22 11 11 25 7 7 11 29 7 11 11 33 11 11 11 36 7 7 11 11 40 7 11 11 11 44 11 11 11 11 47 7 7 11 11 11 In Abbildung 3.11 sehen Sie, dass eine optimal gefüllte Kiste keinesfalls randvoll sein muss. Der Kompass ist offenbar so viel wert, dass es sich sogar lohnt, bei 6er- und 11er-Kisten ein Feld frei zu lassen. Das zeigt auch, warum es in unserem Verfahren sehr wichtig ist, die 1er-Kiste jedes Mal zu betrachten, auch wenn diese immer leer bleibt: Nur durch Anlegen des Kompasses an die 1er-Kiste konnte die Verbesserung des Wertes der 6er-Kiste erreicht werden. Mehr ist weniger 93  Abbildung 3.10 Die Schmuckschatulle verän- dert die optimalen Ergebnisse 0 erneut. 0 7 7 11 11 16 16 18 7 11 23 7 16 27 11 16 32 16 16 34 7 11 16 39 7 16 16 43 11 16 16 48 16 16 16 50 7 11 16 16 Es stehen aber immer noch größere Schätze zur Verfügung. Als Nächstes sind die bunten Vasen an der Reihe. ▶ ▶ ▶ ◀ ◀ ◀ 94 3. Ich packe meinen Koffer und...  Abbildung 3.11 Der Kompass verändert die 0 optimalen Füllungen noch- mals. 0 7 7 11 11 16 16 24 24 24 24 31 7 24 35 11 24 40 16 24 48 24 24 48 24 24 55 7 24 24 59 11 24 24 Sie kommen nur in wenige Kisten, wie Abbildung 3.12 zeigt. Über eine weitere Be- sonderheit sind Sie wahrscheinlich gestolpert, als Sie die 11er-Kiste optimiert haben. Hier ist der Wert ohne und mit dem neuen Schatz absolut identisch. Sie können sich daher frei entscheiden oder aber zusätzliche Kriterien definieren wie etwa die mög- lichst vollständige Ausnutzung des Platzes. In diesem Fall würde man dann – wie im Beispiel geschehen – die Schätze tauschen. Mehr ist weniger 95  Abbildung 3.12 Die Vase verändert die opti- malen Ergebnisse leicht. 0 0 7 7 11 11 16 16 24 24 24 24 32 32 35 11 24 40 16 24 48 24 24 48 16 32 56 24 32 59 11 24 24 Führen Sie nun noch die letzten beiden Schritte durch und ergänzen nacheinander die Krone und die Waage. ▶ ▶ ▶ ◀ ◀ ◀ 96 3. Ich packe meinen Koffer und...  Abbildung 3.13 Mit Krone 0 0 7 7 11 11 16 16 24 24 24 24 32 32 36 36 40 16 24 48 24 24 48 16 32 56 24 32 60 24 36 Die Abbildungen 3.13 und 3.14 zeigen den nächsten Zwischenschritt sowie das Ender- gebnis. Obwohl die Krone nur zwei Kisten beeinflusst, ist die entscheidende 13er-Kis- te dabei, deren Wert nun auf 60 gesteigert werden kann. Die Waage sorgt danach noch für eine Verbesserung bei 9er- und 11er-Kiste, was aber am Resultat nichts verändert, da uns ja letztlich die 13er-Kiste interessiert und alle anderen nur dazu gedient haben, uns zum optimalen Ergebnis zu führen. Mehr ist weniger 97  Abbildung 3.14 Endergebnis 0 0 7 7 11 11 16 16 24 24 24 24 32 32 36 36 43 43 48 24 24 50 7 43 56 24 32 60 24 36 Unser Held vom Beginn des Kapitels sollte sich also einen Kompass und eine Krone einpacken und erhält damit einen Belohnung im Gegenwert von 60 Dublonen. Unser Algorithmus nach dem Prinzip der dynamischen Programmierung hat sich bereits ausgezahlt! 98 3. Ich packe meinen Koffer und... Funktioniert das denn auch immer? Bei der Durchführung des Verfahrens oben bin ich Ihnen noch eine Begründung schuldig geblieben, ob, warum und wie es funktioniert. Gehen wir nochmals zum Start zurück, als es sozusagen nur einen Schatz gab: den Edelstein. Die einzelnen Kisten sind bis zum Rand mit Edelsteinen – dem einzig verfügbaren Schatz – gefüllt, mehr passen nicht hinein. Wir können daher festhalten, dass alle Kis- ten optimal gefüllt sind. Jetzt nehmen wir den nächstgrößeren Schatz hinzu. Wir fan- gen mit der kleinsten (optimal gepackten) Kiste an und schauen, was passiert, wenn man deren Inhalt mit dem neuen Schatz kombiniert. Das machen wir nacheinander mit allen Kisten, bis der Inhalt zu groß wird. Allgemein gesprochen kombinieren wir also den Inhalt einer Kiste A mit dem neuen Schatz S. Um das unterzubringen, benötigen wir eine Kiste B mit der Größe von Kiste A plus der Größe des Schatzes S. Wie erreicht man, dass die Kiste B optimal gepackt ist? Hierfür gibt es nur zwei Mög- lichkeiten: In einer optimal gepackten Kiste B kommt Schatz S nicht vor – in diesem Fall besteht die optimale Kiste aus dem, was schon vor der Betrachtung von Schatz S als optimal festgestellt wurde: dem Inhalt der Kiste aus dem letzten Durchlauf. Kiste B benötigt Schatz S, um optimal gepackt zu sein – in diesem Fall packen wir schon einmal Schatz S in die Kiste (denn wir haben diesen ja gerade als nötig iden- tifiziert). Wie viel Platz haben wir jetzt noch? Genau! Es steht noch so viel Platz zur Verfügung, wie auch Kiste A bietet. Kiste A war aber nach der Voraussetzung bereits optimal gepackt, also liegt es nahe, deren Inhalt zusätzlich zu Schatz S in die Kiste B zu sortieren. Genau das machen wir auch in obigem Verfahren! Abbildung 3.15 zeigt das graphisch. Indem wir also immer bei den kleineren Kisten anfangen, stellen wir sicher, dass diese bereits optimal sind, wenn wir zu den größeren Kisten kommen. Auf diese Weise können wir die kleineren Kisten schon zur „Kon- struktion“ der größeren benutzen. Für jede Kistengröße, in die der neue Schatz passt, beantworten wir die einfache Frage, um die neue, optimal gefüllte Kiste einschließlich ggf. des neuen Schatzes zu ermitteln. Abbildung 3.15 Optimal gefüllt mit Schätzen kleiner als Entweder der neue Schatz ist sinnvoll in der Kiste unter- Kiste B Enthält die optimale Kiste zubringen oder nicht – eine ? den neuen Schatz Nein Ja weitere Möglichkeit gibt es nicht. Optimal gefüllt mit Schätzen kleiner als ? ? ? ? Kiste B Kiste B = + Optimal gefüllt Kiste A Funktioniert das denn auch immer? 99  Wozu dient diese Erkenntnis? Könige sind rar geworden! Die Schatzkammern sind Bankkonten gewichen, und die stehen meistens unter der starken Überwachung der Parlamente. Prinzessinnen sind emanzipiert und lassen sich nicht mehr leichtfertig von bösen Räubern entführen. Wozu also die Vorbereitung auf einen Gang durch die Schatzkammer? Selbstverständ- lich gibt es für die Lösung des Rucksackproblems sehr viele ernsthafte Anwendungen. Auf der Hand liegt der Einsatz bei einer Spedition: Ein Fuhrunternehmer hat ei- nen LKW zur Verfügung und kann verschiedene Waren mit unterschiedlichen Ge- winnspannen transportieren. Wie packt er den LKW, um den größtmöglichen Nutzen zu haben? Bei einer erweiterten Version geht es gleich um eine ganze LKW-Flotte: Stellen Sie sich vor, der Spediteur hat einen Auftrag angenommen, eine ganze Reihe unterschiedlicher Objekte zu transportieren – egal wie viele Fuhren er hierfür benötigt. Wenn er es dank dichter Packung schafft, die Ladung optimal auf die LKWs aufzuteilen (also mit wenig ungenutztem Raum), kann er unter Umständen ganze Fuhren einsparen und damit seinen Gewinn steigern. Denken Sie auch an Arbeitsabläufe: Ein Softwareprojekt muss in einem Monat fertig werden. Wie verteilt man die verschiedenen Aufgabenpakete auf die zehn vorhande- nen Mitarbeiter, so dass möglichst alle gleichmäßig bis zum Ende ausgelastet sind und somit das Projekt in der kürzesten Zeit fertig wird? Während man bei menschlichen Mitarbeitern nicht immer genau schätzen kann, wie lange sie tatsächlich für die Durchführung eines Arbeitspakets brauchen, geht das bei Computern deutlich besser: Eine entsprechende Aufgabe muss gelöst werden, wenn ein Programm von einem Computer mit vielen Prozessoren möglichst schnell ausge- führt werden soll. Auch hier gilt es, die vorhandenen Teilprogramme so auf die Pro- zessoren zu verteilen, dass alle ungefähr die gleiche Last haben und so alle nahezu gleichzeitig fertig werden. Das funktioniert natürlich sowohl im menschlichen als auch im Computer-Fall nur, wenn die einzelnen Teilaufgaben voneinander unabhän- gig bearbeitet werden können. Der Algorithmus Jetzt sind Sie wieder gefragt: Können Sie aus dem Beispiel von oben einen allge- meinen Algorithmus ableiten, der dann künftig für alle Rucksackprobleme dieser Art verwendbar ist? Um die Reihenfolge der einzelnen Operationen besser kenntlich zu machen, dürfen Sie gerne auch wieder Zeiger verwenden, zum Beispiel „Kiste A“ und „Kiste B“ aus dem Bastelbogen! Tipp: In der Lösung werden Sie einige sogenannte „Schleifen“ benutzen. Dies sind die Konstrukte der Art: „Wiederhole das Folgende, bis eine bestimmte Bedingung zu- trifft.“ In der bisher verwendeten Notation für Algorithmen können Sie diese „kopf- gesteuerten Schleifen“ darstellen wie in Abbildung 3.16. Wenn die Bedingung von Anfang an nicht stimmt, werden die Anweisungen aus dem grauen Kästchen kein einziges Mal ausgeführt. 100 3. Ich packe meinen Koffer und...  Abbildung 3.16 Wiederhole das Folgende, solange Notation für die kopfgesteu- die Bedingung „...” zutrifft: erte Schleife Beliebige Anweisung A Beliebige Anweisung B (es sind so viele Anweisungen möglich, wie Sie benötigen) Hier geht es dann auf jeden Fall weiter mit der Ausführung des Algorithmus Im Gegensatz dazu stehen die „fußgesteuerten Schleifen“ der Art: „Wiederhole das Obenstehende, solange eine bestimmte Bedingung zutrifft.“ Die Notation sehen Sie in Abbildung 3.17. Hier werden die Anweisungen aus dem grauen Kästchen auf jeden Fall einmal ausgeführt, bevor die Bedingung überprüft wird. Abbildung 3.17 Beliebige Anweisung A Notation für die fußgesteuer- te Schleife Beliebige Anweisung B (es sind so viele Anweisungen möglich, wie Sie benötigen) Wiederhole das Obenstehende, solange die Bedingung „...” zutrifft Hier geht es dann auf jeden Fall weiter mit der Ausführung des Algorithmus ▶ ▶ ▶ ◀ ◀ ◀ Sie dürfen die Zeiger verwenden, um die Kisten zu markieren, die miteinander ver- glichen werden sollen. Der Algorithmus kann dann wie in Abbildung 3.18 auf der nächsten Seite aussehen. Wenn Sie bereits firm in der Durchführung der Algorithmen sind und sich merken, welche Kisten Sie gerade betrachten, lässt sich das Verfahren auch etwas knapper dar- stellen wie in Abbildung 3.19. Diese Beispiele sollen unterstreichen, dass es keinen all- gemeingültigen Weg gibt, Ihre Ideen aufzuschreiben. Gute Notationen unterscheiden sich in Ausführlichkeit, Formtreue und anderen Parametern. Sie sind dann gut, wenn sie für den jeweiligen Leser verständlich sind. Sie sehen: Es ist günstig, dieses Buch auch im nächsten Urlaub griffbereit zu haben, wenn es darum geht, die wertvollsten Schnäppchen und Mitbringsel im knappen Fluggepäck unterzubringen... Der Algorithmus 101  Abbildung 3.18 Der Rucksack-Algorithmus Setze Kiste A neben die Kiste mit Größe 1 Wiederhole das Folgende, solange Kiste A auf eine Kiste zeigt: Fülle die Kiste neben Kiste A bis zum Anschlag mit dem kleinsten Schatz Schiebe Kiste A um eine Position nach unten Nehme den zweitkleinsten Schatz zur Hand Solange man noch einen Schatz in der Hand hält: Setze Kiste A neben die Kiste mit Größe 0 Wiederhole das Folgende, solange Kiste A auf eine Kiste zeigt: Lege den Schatz rechts an die Kiste, auf die Kiste A zeigt Lege Kiste B neben die Kiste, die so groß ist wie die neben Kiste A und der Schatz zusammen Überprüfe, ob der Inhalt von Kiste A plus dem Schatz wertvoller ist als der Inhalt von Kiste B Wenn JA: Fülle Kiste B so, dass sie dem Inhalt von Kiste A plus dem Schatz entspricht Schiebe Kiste A um eine Position nach unten Lege den Schatz aus der Hand und nimm den nächstgrößeren Schatz in die Hand, falls es noch einen größeren gibt Was steckt dahinter? Vielleicht erkennen Sie, dass Sie das Prinzip der dynamischen Programmierung be- reits kennen gelernt haben: Beim Routenplaner war es ebenfalls einfacher, sämtliche Routen zu Orten zu bestimmen, die weniger weit weg als unser Ziel waren. 102 3. Ich packe meinen Koffer und...  Abbildung 3.19 Wiederhole das Folgende mit allen Kisten aller Größen: Der Rucksack-Algorithmus, etwas kürzer gefasst Fülle die Kiste bis zum Anschlag mit dem kleinsten Schatz Für alle Schätze, beginnend mit dem zweitkleinsten Schatz bis zum größten Schatz: Für alle Kisten: Beginnend mit der Kiste der Größe 0 bis zur größten Kiste nennen wir sie KisteA: Lege den Schatz rechts an die KisteA Bestimme die KisteB, die so groß ist wie die KisteA und der Schatz zusammen Überprüfe, ob der Inhalt der KisteA plus dem Schatz wertvoller ist als der Inhalt von KisteB Wenn JA: Fülle KisteB, so dass sie dem Inhalt von KisteA plus dem Schatz entspricht Genau das machten auch die Ameisen: Sie erkundeten gleichzeitig alle möglichen Orte, bis sie am Ziel ankamen. Etwas Entsprechendes haben wir auch beim Packen der Kisten getan: Wir haben alle kleineren Kisten gepackt und darauf aufbauend den optimalen Inhalt der größeren bestimmt. Das erinnert stark an ein Prinzip, das in der Mathematik bereits sehr lange bekannt ist und auch in der Informatik eine entscheidende Rolle spielt: die vollständige Induk- tion. Vollständige Induktion kennt man prinzipiell, seit 1654 der französische Mathematiker Vollständige Induktion und Philosoph Blaise Pascal Die vollständige Induktion ist ein zweistufiges mathematisches Beweisverfah- mathematische Beweise nach diesem Schema durchgeführt ren. Es funktioniert insbesondere für Aussagen in Bezug auf ganze Zahlen. Man hat. Erst mit der Einführung beweist, dass die Aussage für eine bestimmte kleine Zahl a gilt. Ferner beweise eines formalen Systems für man: Falls die Aussage für die Zahl n – 1 gilt, dann gilt sie auch für die Zahl n. natürliche Zahlen um 1880 wurde daraus dann ein Damit hat man dann bewiesen, dass die Aussage für alle ganzen Zahlen größer allgemeingültiges Beweisver- oder gleich a gilt. fahren, das heute auch in der Informatik häufig eingesetzt wird. Beispielsweise möchten wir beweisen, dass folgender Satz gilt: n ⋅ (n + 1) 1 + 2 + 3 +... + n = 2 Was steckt dahinter? 103  Der kleine Gauß ist eine Zunächst kommt die sogenannte Induktionsverankerung: der Beweis, dass der Satz bekannte Bezeichnung für für eine bestimmte kleine Zahl gilt. In diesem Fall wählen wir n = 1. Die Rechnung ist den Satz, der hier als Beispiel für vollständige Induktion 1 ⋅ (1 + 1) genutzt wird. 1= Hintergrund ist eine Ge- 2 schichte über den jungen Wir sehen leicht, dass diese Rechnung stimmt. Als Nächstes kommt der sogenannte Karl Friedrich Gauß, der in Schluss. Dabei nehmen wir an, dass wir den Satz für alle Fälle bis zur Zahl n − 1 bereits der Volksschule als Beschäf- bewiesen haben und versuchen, ihn mit dieser Annahme ebenfalls für die Zahl n zu tigungstherapie die Zahlen 1 bis 100 addieren sollte. Er beweisen. legte das Ergebnis seinem Als Formel ausgedrückt nehmen wir als gegeben an: Lehrer in kürzester Zeit vor, indem er die kleinste und die (n − 1) ⋅ n größte Zahl addierte (=101) 1 + 2 + 3 +... + (n − 1) = und diese Summer mit 50 2 multiplizierte, denn 1 + 100 Zu beweisen ist: = 2 + 99 = 3 + 98 usw., und von solchen Paarungen gibt n ⋅ (n + 1) 1 + 2 + 3 +... + n = es 50 Stück. 2 Den ersten Teil vor dem Gleichheitszeichen können wir erweitern und (n − 1) explizit aufführen. Dadurch ändert sich an der Aussage nichts: n ⋅ (n + 1) 1 + 2 + 3 +... + (n − 1) + n = 2 Den ersten Teil der neuen linken Seite kennen wir bereits aus unserer Annahme. Wir setzen hierfür die Formel ein, die wir bereits als bewiesen angenommen hatten: (n − 1) ⋅ n n ⋅ (n + 1) +n = 2 2 Eine kleine Umformung der rechten Seite, bei der wir den einzelnen Summanden n in den Bruch holen, führt zu: (n − 1) ⋅ n + 2 ⋅ n n ⋅ (n + 1) = 2 2 Nun kann man die beiden Summanden im linken Zähler leicht zusammenführen und sehen, dass die Gleichung gilt. Wir haben bewiesen, dass der Satz für n gilt unter der Voraussetzung, dass er auch für n − 1 gilt. Da wir ihn für n = 1 bewiesen hatten, folgt daraus also, dass er ebenfalls für n = 1 + 1 = 2 gilt. Wenn er für n = 2 gilt, ist er ebenfalls für n = 3 bewiesen usw. Insgesamt können wir also sagen, dass die Behauptung für alle n ≥ 1 gilt. Kommen wir nach diesem mathematischen Intermezzo zur dynamischen Program- mierung zurück. Auch hier gibt es quasi eine Verankerung, bei der das Problem für eine kleine Problemgröße gelöst wird. Im Laufe des Algorithmus leiten wir dann je- weils aus einer kleineren Lösung die nächstgrößere ab. Im Beispiel des Rucksackproblems bestand die Verankerung darin, das Problem für den Fall zu lösen, dass nur ein einziger Schatz zur Wahl steht: der kleinste. Danach konstruierten wir aus der Problemlösung der Größe n (eine optimal gefüllte Kiste der Größe n) und dem nächsten Schatz der Größe s die Problemlösung der Grö- ße n + s : Die Kiste der Größe n + s wird optimal gefüllt, wenn man sie entweder so lässt, wie sie ist, oder mit dem Inhalt der Kiste n + Schatz s füllt – je nachdem, welche der Möglichkeiten wertvoller ist. Die Begründung habe ich bereits weiter oben angeführt. Sie setzt voraus, dass man tatsächlich eine optimale Kiste der Größe n hat. Genau genommen handelt es sich hier 104 3. Ich packe meinen Koffer und... um eine Art Induktionsschluss. Auf diese Weise wird gezeigt, dass das Verfahren für immer höhere Problemgrößen ebenfalls korrekt funktioniert. Versuchen Sie jetzt, für den Dijkstra-Algorithmus aus dem ersten Kapitel die Ver- ankerung und den Induktionsschluss zu finden! ▶ ▶ ▶ ◀ ◀ ◀ Verankerung: Der kürzeste Weg vom Startort S zu sich selbst ist 0. Schluss: Angenommen, wir haben den (tatsächlich) kürzesten Weg vom Startort S zu den Or- ten O1 bis On–1 bestimmt. Dann ist der nächste Ort On derjenige, der einem Ort Ox aus der Menge der Orte O1 bis On–1 benachbart ist und bei dem die Summe aus dem (bereits bestimmten optimalen) Weg von S nach Ox und dem Weg von Ox nach On minimal ist. Sie erkennen hier, dass der Übergang zwischen Informatik und Mathematik fließend ist. Viele Teilgebiete haben beide Wissenschaften gemeinsam, so die diskrete Mathe- matik (oder Mathematik ganzer Zahlen), die auch hier verwendet wurde. Das verflixte NP Eines der großen Probleme bei der vorgestellten Lösung des Rucksackproblems lässt sich aber an der Beziehung zwischen dynamischer Programmierung und vollständi- ger Induktion auch ablesen: Die hier vorgestellte Lösung funktioniert nur für „ganzzahlige“ Problemgrößen. Was bedeutet das? Alle Kisten waren sozusagen „linear“, sie bestanden aus einer ganz- zahligen Anzahl von Quadraten, ebenso die Schätze. Hier konnte man leicht von einer kleineren Kiste auf eine entsprechend größere schließen. Reale Probleme arbeiten selbstverständlich mit dreidimensionalen Kisten. Jeder Polynomiell, nicht polyno- „Schatz“ hat unterschiedliche Ausmaße in Länge, Breite und Höhe (oder ist sogar völ- miell lig unregelmäßig, wie bei einer lose Krone). Außerdem lassen sich reale Schätze nicht Auch in Kapitel 1 haben wir im Abschnitt „Was steckt in ganzzahlige Kästchen (zum Beispiel glatte Zentimeter-Werte) einteilen. Darüber dahinter?“ bereits einführend hinaus geben die echten Schatzkammern oft nicht beliebig viele Schätze einer Sorte über dieses Thema philoso- her. Was passiert, wenn unser Algorithmus anzeigt, dass man zwei Kronen einpacken phiert. Lesen Sie am besten soll, aber nur eine da ist? dort nochmals nach, falls hier etwas unklar bleiben sollte! Hier versagt das Verfahren! Sie sehen, dass oft eine kleine Veränderung der Aufga- Dort steht übrigens auch, was das Travelling-Salesman-Prob- benstellung ausreicht, um aus einem „einfachen“ Problem eines zu machen, für des- lem eigentlich ist... sen Lösung kein Algorithmus existiert, der in polynomieller Zeit arbeitet. Bereits im Zusammenhang mit dem Dijkstra-Algorithmus diskutierten wir ausführlich darüber. Man hat eine ganze Menge von Problemen, die man momentan nicht in polynomieller Zeit lösen kann, in eine Kategorie gepackt, die sogenannten „NP-vollständigen Pro- bleme“. Dazu gehören zum Beispiel das allgemeine Rucksackproblem und auch das Travelling-Salesman-Problem (allerdings sind längst nicht alle Probleme, die nicht in polynomineller Zeit lösbar sind, NP-vollständig). Das verflixte NP 105  Man konnte bisher für keines der Probleme eine Lösung in polynomieller Zeit fin- den, aber auch keinen Beweis dafür, dass eine solche Lösung nicht existieren könnte. Gleichzeitig hat man aber nachgewiesen, dass – sollte es eine entsprechende Lösung für eines der Probleme geben – alle Probleme dieser Art in polynomieller Zeit lösbar sind. Das Thema wird uns weiter beschäftigen, zum Beispiel im Zusammenhang mit dem Affenpuzzle. Vielleicht dient es als kleiner Appetitmacher, wenn ich hier schon einmal erwähne, dass ein Preisgeld von einer Million Dollar dafür ausgesetzt ist, die Frage endgültig zu klären, ob es möglich ist, Probleme der Kategorie „NP-vollständig“ in polynomieller Zeit zu lösen. Im Klartext: Wenn Sie sich hinsetzen und für eines der beschriebenen Probleme einen Algorithmus basteln, der mit einer (beliebig schlechten, aber) polynomiellen Rechen- zeit im Verhältnis zur Problemgröße auskommt, sind Sie der Held der Informatik für die nächsten Jahre! Aber dazu später mehr. Resümee Sie haben in diesem Kapitel mit der dynamischen Programmierung erfahren, dass es manchmal durchaus effektiver sein kann, alle Lösungen eines Problems bis zu einer Größe n zu bestimmen, als sich nur auf die Lösung der gewünschten Problemgröße zu konzentrieren. Neben dem vorher behandelten Lösungsschema „top down“, bei dem man große Auf- gaben Schritt für Schritt handhabbar macht, indem man sie immer weiter aufteilt, sollten Sie also auch „bottom up“ im Blick haben: Hier fangen Sie gleich ganz unten an und lösen zunächst einfachste Bausteine, um diese dann zur „großen“ Problemlösung zusammenzusetzen. Gleichzeitig ist das hier behandelte Rucksackproblem ein schönes Beispiel dafür, wie wenige Veränderungen der Aufgabenstellung manchmal ausreichen, aus einem ein- fachen Problem eines zu machen, das quasi nur noch durch mehr oder weniger ge- schicktes Ausprobieren lösbar ist. 106 3. Ich packe meinen Koffer und...  Abbildung 3.K1 Kopiervorlage für Schätze, Sie brauchen diese drei Mal 43 16 43 16 43 16 36 24 36 24 36 24 32 16 7 32 16 7 32 16 7 32 16 7 24 16 7 7 24 7 7 7 7 24 7 7 7 7 11 11 11 7 7 11 11 11 7 7 11 11 11 7 7 11 11 11 7 7 107 108 Abbildung 3.K2 Maxikiste als Spielfeld 109