Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Dynamisches Programmieren
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 91 Zeilen
- Eigentlich ist der Ausdruck dynamisches Programmieren gar nicht glücklich gewählt. Man weiß überhaupt nicht,
- was das bedeuten soll. Was ist daran dynamisch? Was hat das mit Bewegung zu tun? Unklar. Wie man auch immer zu diesem Begriff steht, ist auf jeden Fall der Name für eine
- algorithmische Technik, um die es in diesem Video geht. Die Idee haben wir ja schon im Video über maximale Teilaries gesehen. Wir fangen an mit einem möglichst kleinen Problem.
- Bei maximalen Teilaries war das ein Problem, das nur aus dem ersten Eintrag im Erri besteht. Und da war die maximale Teil-Summe natürlich sofort zu finden,
- nämlich eben dieses ganze Erri, was nur aus einem Eintrag besteht. Und dann haben wir durch verlängern des Erris Schritt für Schritt das Problem immer weiter vergrößert. Und die
- Lösung für das nächstgrößere Problem haben wir dann berechnet nach der inkrementellen Idee aus den Lösungen für die kleineren Probleme, die wir davor schon gelöst haben.
- Und wenn wir dann immer weitermachen, dann schaffen wir es am Schluss tatsächlich, das ursprüngliche Problem zu lösen und dann sind wir fertig. Die Idee ist also, fange klein an
- und berechne iterativ, nicht rekursiv, sondern iterativ, wir haben nachher den Algorithmus ja umgedreht, dass es keine rekursiven Aufrufe mehr waren, sondern iterativ die Lösungen für immer
- größere Probleme. Und zwar aus den Lösungen der kleineren Probleme, die wir ja bereits ermittelt haben. Dabei merken wir uns immer die Lösungen der kleineren Probleme so lange,
- wie wir sie noch brauchen, um eben die Lösung für die nächstgrößeren Probleme zu berechnen. Es ist so ähnlich wie man Muskeln aufbaut im Fitnessstudio. Man fängt auch nicht gleich mit
- dem riesen Gewicht an, sondern man fängt erstmal mit einem kleinen Gewicht an und trainiert das. Und wenn man das kann, trainiert man es ein bisschen größer und so weiter, bis
- man am Schluss die riesen Handeln stemmen kann. Wir fangen eben mit einem kleinen Problem an, was wir sofort lösen können und dann erweitern wir die Problemgröße Schritt für Schritt,
- bis wir am Schluss beim ursprünglichen Problem, was wir eigentlich lösen wollten, angelangt sind. Und hier ist das Beispiel, wo wir es im letzten Video gesehen haben. Das ist Kadarnis Algorithmus
- der dynamische Programmierung zur Lösung des maximalen Teilsummenproblems verwendet. Und die Idee sehen Sie genau hier. Das ist hier quasi die Abbruchbedingung der Rekursionsgleichung.
- Hier fangen wir an, das sind die kleinsten Probleme, die man lösen kann. Er ist mit nur einem Element, da geht es los. Und dann berechnen wir hier Schritt
- für Schritt die Lösung für immer größere Probleme. Und das Gute ist, wir brauchen tatsächlich bei diesem Problem immer nur die Lösung des gerade vorangegangenen Problems.
- Und deswegen müssen wir gar keine große Speicherwirtschaft machen. Das ganze Erri, was wir beim Memo-Isa-Tion gefüllt haben für das Maximum-End-Eri, das brauchen wir hier gar
- nicht. Es reicht uns eine einzige Variable, die den Wert des letzten Durchlaufs hält. Und dann können wir eben durch diesen Schritt hier den Wert für das nächstgrößere Erri bestimmen.
- Und am Schluss haben wir in MTS dann die maximale Teilsumme von dem gesamten Erri von 1 bis n errechnet. Nun hat dynamisches Programmieren tatsächlich auch eine gewisse Ähnlichkeit mit
- Teilen und Herrschen. Es wird auch bei dynamischem Programmieren ein größeres Problem auf die Lösung von kleineren Problemen zurückgeführt. Das heißt, zuerst werden kleine Lösungen erzeugt
- und dann werden aus den Lösungen für kleine Probleme die Lösungen der großen berechnet. Nur läuft bei dynamischem Programmieren meistens die Kontrolle des Programms oder
- des Algorithmus andersherum als bei Teilen und Herrschen. Bei Teilen und Herrschen arbeiten wir gewöhnlich top down. Das heißt, wir fangen bei dem großen Problem an,
- teilen dann das Problem in Hälften, möglichst zwei gleich große zum Beispiel, wie bei MerchSort und dann lösen wir die rekursiv. Und wenn die rekursiven-Aufrufe zurückkommen,
- berechnen wir eben aus den Lösungen der kleineren Probleme die Lösung für das größere Problem. Bei dynamischem Programmieren dreht man die Kontrollstruktur normalerweise um. Das heißt,
- man fängt sofort am Anfang mit den kleinen Problemen an und wartet sie dann aus. Und dann eben meistens nicht durch Verschmelzung gleichgroßer Teilprobleme, sondern durch
- den Übergang von einem Teilproblem der Größe i auf ein Teilproblem der Größe i plus eins, bis man schließlich bei n angekommen ist. Das heißt, Teilen und Herrschen ist normalerweise top down,
- also vom großen zum kleinen und dann durch Rekursuren wieder zurück, während dynamisches Programmieren normalerweise bottom up funktioniert.
- Und das geht auch Hand in Hand mit der Programmiertechnik. Teilen und Herrschen programmiert man meistens rekursiv. Dynamisches Programmieren auf der anderen Seite kann man ganz
- einfach iterativ hinschreiben, wobei man natürlich immer rekursive Algorithmen auch in iterative Umwandeln kann und umgekehrt. Das Problem, was sie sich einhandeln beim dynamischen Programmieren,
- wenn sie nicht mehr die Rekursion verwenden, ist natürlich, dass sie sich um eine Datensstruktur kümmern müssen, die die Lösungen der kleineren Probleme hält.
- Bei unserem Problem, was wir eben gesehen haben, war das sehr einfach, da reichte eine Variable. Bei anderen Algorithmen, die wir uns demnächst anschauen werden, in einem späteren Video,
- wird es etwas komplizierter. Und dieses Problem hat man bei rekursiven Algorithmen natürlich nicht. Dort werden die Ergebnisse erzeugt und dann rekursiv wieder zurückgegeben und bei der Rückgabe
- hat man dann eben die Daten, die man braucht, um das nächste größere Problem zu berechnen. Gemeinsam haben beide Ansätze sowohl Teilen und Herrschen als auch dynamisches Programmieren.
- Eines gemeinsam, nämlich man braucht, um diese Techniken anzuwenden, jedes Mal eine Rekursionsgleichung bzw. ein System von Rekursionsgleichungen und Abbruchbedingungen.
- Und dieses System von Rekursionsgleichungen ist eben dazu da, um dem Algorithmus zu sagen, wie man aus den Teillösungen bzw.
- aus den kleineren Lösungen die Gesamtlösung bzw. die nächstgrößeren Lösungen herstellt. Beim maximalen Teilsummenproblem war das zum Beispiel dieses System von
- Rekursionsgleichungen. Wir haben zum einen für die maximale Endsumme und zum anderen für die maximale Teilsumme, MTS, eine solche Rekursionsgleichung.
- Und hier sind die beiden Abbruchbedingungen für diese Rekursionsgleichungen. Und zusammen ergeben sie eben den Algorithmus, den wir hier oben gesehen haben. Und Sie kennen
- noch ein zweites Beispiel für dynamisches Programmieren und das ist dieser schöne Algorithmus. Den haben wir bereits ziemlich am Anfang des Semesters uns angeschaut.
- Das ist der Minimumsalgorithmus und zwar der, der einfach einmal drüber läuft. Und wie hat er das gemacht? Ja, er hat es genau so gemacht,
- wie wir es eben gesagt haben beim dynamischen Programmieren. Er hat immer aus dem Minimum des kleineren Teilaries das Minimum des um eins größeren Teilaries berechnet.
- Ja, wie? Mit Hilfe einer Rekursionsgleichung. Und diese Rekursionsgleichungen gehen so. Das Minimum von einem Array von 1 bis n ist gleich dem Minimum von a von 1 bis n minus 1.
- Ja, nicht immer. Wenn jetzt bei a von n das neue Minimum wäre, das Minimum des gesamten Arrays, dann ist das natürlich a von n das Minimum.
- Eins von diesen beiden muss das Minimum sein. Ja, welches denn? Ja, das kleinere von beiden. Beachten Sie dabei,
- das hier ist ein Minimumsalgorithmus, der nur zwei Argumente nimmt. Und die Rekursionsgleichung ist dann die Grundlage für diesen Algorithmus, der das auf n Elementen,
- auf einer Liste mit n Elementen durchführt. Fehlt natürlich noch die Abbruchbedingung. Was ist denn das Minimum von a von 1 bis 1? Also die kleinste mögliche Liste, die nur aus einem
- Element besteht, ja, das ist natürlich a von 1 selbst. Und damit ist die Rekursionsgleichung fertig und den Algorithmus kann man dann danach bauen. Wir werden im Laufe der Veranstaltung noch
- etwas komplexere Beispiele für dieses Prinzip des dynamischen Programmierens uns ansehen. Jetzt für dieses Video gibt es nur noch ein Beispiel, und zwar ein einfaches Beispiel. Das
- nennt sich Fibonacci Zahlen. Und die Idee ist die, dass man berechnen möchte, wie viele Hasen es im Laufe der Zeit gibt, wenn die sich vermehren wie die Kaninchen. Also am Anfang, zum Zeitpunkt 0,
- hat man noch ein Pärchen von Hasen und die sind dann nach einem Monat ausgewachsen. Das ist dann Zeitpunkt 1. Und dann bekommen sie, sobald sie ausgewachsen sind,
- innerhalb eines Monats wieder Junge. Dann haben wir schon zwei Pärchen und dann können die aber im nächsten Monat wieder neue Junge machen. Und dann haben wir schon drei.
- Nachdem man den Monat gewartet hat und diese Kleinen hier inzwischen auch groß geworden sind, können sie dann in der Folge ebenfalls wieder
- Kleine kriegen. Und auf die Weise wächst das Ganze nach der Folge 1, 1, 2, 3, 5, 8 und so weiter. Ziel ist also herauszufinden im Monat i, das ist hier oben 1, 2, 3 und so weiter,
- wie viele Hasenpaare gibt es denn dort. Und die Idee dazu ist ganz einfach. Es gibt noch alle Hasenpaare aus dem Vormonat. In diesem Beispiel sterben Hasen nie und leben
- unendlich lang zum einen. Und hinzu kommen die neuen Kinder, die jetzt in diesem Monat geboren worden sind. Und das sind genauso viele, wie es Erwachsene Hasenpaare im Vormonat gegeben hat.
- Und die Zahl der Erwachsenen im Vormonat ist die Gesamtzahl der Hasen im Monat davor, also zwei Monate zurück. Und so ergibt sich folgende Rekursionsgleichung. Die Fibonacci Zahl n, also
- die Zahl der Hasenpaare nach n Monaten, ist gleich die Fibonacci Zahl im letzten Monat, also nach n-1 Monaten. Das sind quasi die Hasen, die einfach jetzt aus dem letzten Monat überlebt
- haben und immer noch da sind, nämlich alle aus dem letzten Monat gibt es jetzt noch. Plus die Hasen, die jetzt hinzugekommen sind, die Hasen, die es vor zwei Monaten gab,
- die sind im letzten Monat erwachsen gewesen und jedes erwachsene Hase hat eben dann in diesem Monat neuer Junge gekriegt. So und für den ganzen Sprach brauchen wir natürlich auch wieder
- eine Abbruchbedingung, in diesem Fall sogar zwei Abbruchbedingungen. Und das liegt daran, weil diesmal die Rekursion nicht nur das letzte Element berücksichtigt, sondern die zwei letzten
- Elemente. Und wir schreiben deswegen Fib von 1 gleich 1 und Fib von 2 gleich 1. Und damit sind also, wenn wir hier nochmal in die Zeichnung gehen,
- diese beiden ersten Monate hier gemeint, wo es jeweils ein Hasenpärchen gegeben hat. So und diese Rekursionsgleichung kann man natürlich ganz einfach in so
- einen rekursiven Algorithmus umwünschen. Nur Moment, das ist jetzt nicht dynamische Programmierung. Das ist eben wieder ein rekursiver Algorithmus und der hat furchtbare Laufzeiten.
- Das liegt daran, dass wir Fib für dieselbe Zahl hinten dran bei diesem Algorithmus x-mal aufrufen. Malen Sie sich ruhig mal für diesen Algorithmus so einen Aufrufbaum auf.
- Also oben an die Worte schreiben Sie Fib von n und Fib von n ruft dann auf Fib von n-1 und Fib von n-2. Und Fib von n-1 ruft dann wieder Fib von n-2 auf und Fib von n-3.
- Fib von n-3 wird dann von diesen beiden Fib von n-2 aufrufen, jeweils auch nochmal aufgerufen und so weiter. Das vergrößert sich nach unten und zwar in einer Geschwindigkeit,
- die in etwa dem entspricht, wie sich tatsächlich auch die Hasen vermehren. Und das sorgt dann im Endeffekt für eine ganz furchtbare Laufzeit. Das ist kein polynomialer Algorithmus mehr.
- Das ist aber auch jetzt nicht weiter schlimm, denn wir haben hier im Prinzip auch gar nicht dynamische Programmierung angewendet. Lassen Sie uns also jetzt mal den Algorithmus hinschreiben,
- wie er aussehen würde, wenn wir tatsächlich dynamische Programmierung machen würden. Und dazu müssen wir uns überlegen, wie wollen wir denn die Werte, die Fibonacci-Zahlen,
- die wir einmal berechnet haben, speichern, damit wir sie dann zur Berechnung größerer Fibonacci-Zahlen verwenden können. Und es bietet sich hier wieder mal ein Array an.
- Die Idee ist also die. Wir nennen den Algorithmus wieder Fib und er bekommt eine natürliche Zahl n. Und dann füllen wir ein Array, sei M von 1
- bis n ein Array. Und da füllen wir jetzt hinein die Fibonacci-Zahlen. Und zwar zunächst gehen wir hier nach der Abbruchbedingung vor. M von 1 ist 1,
- M von 2 ist 1. Und nun müssen wir nur den Rest noch ausfüllen. Also wenn das n größer als 2 ist, dann lassen wir vor i von 3 bis n laufen.
- Und dann schreiben wir in M von i einfach nach dieser Rekursionsgleichung hier den Wert der i-ten Fibonacci-Zahl. Und der ist dann natürlich M von i-1 plus M von i-2. Und wenn wir dann fertig sind,
- können wir am Schluss einfach M von n zurückgeben. Und das ist dann die gesuchte Fibonacci-Zahl. So, dieser Algorithmus hat jetzt eine spitzenmäßige Laufzeit,
- nämlich O von n. Und so muss das natürlich sein. Was er aber auch hat, ist, er hat einen Platzverbrauch von O von n. Er braucht, wenn ich die Fibonacci-Zahl,
- die n-te Fibonacci-Zahl ausrechnen will, auch ein Array der Länge n. Das heißt, je größer die Zahl ist, die ich ausrechnen will, desto mehr Platz brauche
- ich auch. Und das ist natürlich etwas übertrieben. Deswegen steht hier schon die nächste Überschrift. Der Algorithmus Platz sparend, auch mit dynamischem Programmieren.
- Und wie sparen wir Platz? Na, ganz einfach. Schauen Sie, wie viele werden denn gebraucht, wie viele Felder in dem Array? Ja, immer nur die beiden zwei Letzten, der Letzte und der Vorletzte.
- Und dann kam ich doch aus mit nur zwei Variablen, die den Letzten und den Vorletzten speichern. Und dann muss ich eben eine Variabe noch haben, wo ich das neue reinrechne. Und dann muss ich alles
- entsprechend verschieben. Und den Algorithmus schreibe ich jetzt auch noch mal schnell hin. Ich werde jetzt erstmal am Anfang tatsächlich diesen Fall, dass ich in der Abbruchbedingung bin,
- hineinnehmen. Denn sonst muss ich ja gar keine Schleife machen. Und das ist natürlich so praktischer. Und das sind jetzt die beiden Variablen,
- die ich brauche, die ich dazu benutze, um die Vorgängerzahlen abzuspeichern. F2 ist dabei die größere von den beiden. Das heißt, die,
- die etwas später kommt. Jetzt am Anfang sieht man das noch nicht. Das sind die beiden, beide eins. Aber wir werden das gleich sehen, wenn ich nun die Schleife von 3 bis n laufen
- lasse. Dann berechne ich zuerst die neue Fibonacci-Zahl F3. Das wird dann die Ithi-Fibonacci-Zahl. Die ist natürlich F1 plus F2.
- Und dann muss ich noch wieder F1 und F2 updaten. Ja, F1 sollte die kleinere von beiden sein. Und die kriegt jetzt den Wert von der größeren
- von beiden. Das war vorher die letzte Zahl und jetzt wird das die vorletzte. Und das F2 bekommt den Wert von dem F3. Und damit ist der Shift getan.
- Jetzt kann ich in den nächsten Schleifendurchlauf gehen und dann die nächste Zahl ausrechnen. Und am Schluss gebe ich einfach F2 zurück.
- Und das ist dann die Ithi-Fibonacci-Zahl. So, und das wäre hier der schöne Algorithmus, der es schafft, in Linearzeit, also Zeit O von n, die n-de Fibonacci-Zahl auszurechnen und dabei
- nur konstant viel Platz braucht, also O von 1. Leider kann man nicht bei allen Algorithmen, die dynamisches Programmieren verwenden, den Platz auf O von 1 drücken. Es gibt Algorithmen,
- wo tatsächlich viel mehr abgespeichert werden muss. Und ein Beispiel dafür werden wir uns in einem der nächsten Videos dann gleich anschauen.