Eine der schönsten Optimierungen, die ich kenne, ist die Optimierung nach Bellman, die Dynamische Programmierung. Daß ich sie kenne, heißt nicht, daß ich sie in allen Einzelheiten verstanden habe, geschweige denn, daß ich ihren Beweis führen könnte. Aber nun, ich kann den Beweis nachvollziehen und die Dynamische Programmierung anwenden. Und sie ist wunderschön. Allein die Idee, sie rechnerfähig zu machen, indem man das Problem diskretisiert! Die Diskretisierung kann man vielleicht am besten anhand eines Bildes beschreiben. Stellen Sie sich ein Blau vor. Nein, nicht dieses Blau. Einen Ticken dunkler! Noch etwas. Genau. Genau so. Wie viele Schattierungen von Blau gibt es denn? Es sind unendlich viele, und sie verbindet nur eines - sie sind alle blau. Um nun stets das gleiche Blau darzustellen, diskretisieren wir blau. Wir vergeben also ein Spektrum für Blau, das von nullblau bis totalblau reicht, und wir teilen dieses Spektrum in 256 gleiche Stücke ein. Wenn ich Ihnen nun sage, Sie sollen auf der vereinbarten Skala das Blau Nummer 112 auswählen, dann sollten wir alle das selbe Blau sehen. Jaja, Farbdarstellung ist ein wenig komplizierter, aber für unsere Zwecke soll es ausreichen, daß eine Strecke zwischen zwei definierten Endpunkten in eine endliche Anzahl von kleinen Teilstrecken geteilt wird. Das ist Diskretisierung. Und damit können kontinuierliche Verläufe angenähert und mit Computern berechenbar gemacht werden. Das ist toll, finde ich.
Und so wurde auch die Theorie der Dynamischen Programmierung erst so richtig spannend, als es Rechner gab und es gelang, die Diskrete Dynamische Programmierung einzusetzen. Wenn Sie damit mal herumspielen möchten: Die ETH Zürich bietet ein Skript zur Dynamischen Programmierung für MatLab an.
Aber was macht die Dynamische Programmierung eigentlich, und was macht sie so schön? Nun, die Dynamische Programmierung garantiert bei ausreichend genauer Diskretisierung Optimalität. Das heißt, sie ist innerhalb ihres Lösungsraumes nicht zu schlagen. Und, sie bietet trotz der furchtbaren Formelei einige wunderschöne Ideen.
Eine dieser wunderschönen Ideen ist der Bezug zwischen globaler und lokaler Optimalität. Das bedeutet nichts anderes als daß sich ein Satz von Entscheidungen, der global optimal ist, aus einzelnen, also lokalen, Entscheidungen zusammensetzt, die jede für sich bereits optimal sind. Ist das nicht eine tolle Idee? Und eine, die vielleicht nur auf den ersten Blick sinnvoll klingt? Könnte es denn nicht sein, daß man zuerst eine auf den ersten Blick (also lokal) unvorteilhafte Entscheidung treffen muß, um zur Möglichkeit einer späteren Entscheidung zu gelangen, die ein besseres Gesamtergebnis (also ein globales Ergebnis) zulässt?
Der nächste wunderschöne Punkt an der Dynamischen Programmierung ist die Unterscheidung von Zustands- und Kontrollgrößen. Nehmen wir ein Auto als Beispiel. Da ist die Richtung, in die Sie fahren, eine Kontrollgröße, die Sie beliebig ändern können, wenn der Verkehr das zulässt. Dagegen ist die Strecke, die Sie fahren können, durch den Füllstand des Kraftstofftanks bestimmt. Wenn der leer ist, müssen Sie schieben. Und so ganz nebenbei kann man an diesem Beispiel noch zwei tolle Dinge sehen: Auch die Kontrollgrößen unterliegen Grenzen: Sie können nicht links abbiegen, wenn da eine Wand ist. Oder Gegenverkehr. Diese Grenze kann übrigens von Ihrem Zustand abhängen, also von der bisher gefahrenen Strecke. Das kennt man aus dem Beispiel der verpassten Autobahnabfahrt. Nehme ich eben die nächste, komme ich auch ans Ziel. Nur mit etwas mehr Strecke. Und das zweite Tolle: die Kontrollgrößen beeinflussen die Zustandsgrößen! Wenn Sie sich entschließen, die nächste Abfahrt zu nehmen, gelangen Sie mit etwas Geschick ans gleiche Ziel - nur mit etwas weniger Kraftstoff im Tank. Und wenn Sie die letzte im Bunde, die Kostenggröße, entsprechend definieren, kann Ihnen das auch noch egal sein. Denn wenn Kosten für Sie nicht in Kraftstoff stattfinden, sondern in Ihrer Zeit, dann ist Ihnen der Umweg vielleicht egal, wenn Sie dafür schneller fahren können. Und so bietet Ihnen zum Beispiel jedes Navigationsgerät die kürzeste Strecke und die schnellste Strecke an. Das ist sehr toll, denn Zustands- Kontroll- und Störgrößen kennen wir aus der Regelungstechnik. Und dort funktionieren sie sogar ganz ähnlich. Deshalb wird die Dynamische Programmierung unter dem Oberbegriff der "Optimalen Steuerung" abgelegt. Seltsamerweise kommt das Prinzip von Bellman, das hinter der Dynamischen Programmierung steckt, allerdings aus der Finanzmathematik. Wann wo wieviel Geld hinschieben. Kann ich also im Prinzip auch, wenn ich Dynamische Programmierung kann. Leider braucht man dazu einen vollständig beschriebenen Zustandsraum, und da klemmt es schon bei den Finanzen. Zumindest bei mir, ich weiß ja nicht einmal, wieviel Geld ich gerade mit mir herumtrage.
Was macht sie denn nun noch Tolles, die Dynamische Programmierung, daß sie dafür einen vollständig beschriebenen Raum braucht? (Aktuelle Ansätze brauchen das nicht mehr unbedingt, denn es geht ja immer noch anders und noch besser. Das weiß man, und das gilt natürlich auch für die Dynamische Programmierung, steht allerdings im Widerspruch zum obengenannten Prinzip der Optimalität. Und das kann es auch, denn es befindet sich außerhalb des vollständig beschriebenen Raumes, und das wiederum ist ein ganz tolles Paradoxon, wie ich finde, gar einer der schönsten Knoten, die ich mir je ins Hirn gezaubert habe.) Nun, die klassische Dynamische Programmierung fängt an ihrem Ziel an, und nicht am Start.Ist das nicht schön? Wir stehen vor einem unendlich schwierigen, langen Weg, schauen sich den Start an und sagen dann: Nehmen wir mal an, wir wären schon da. Ich finde das sehr entspannend. Nehmen wir nun an, unser Ziel wäre ein Platz, ein schöner Platz im Wald, auf einer sonnigen Lichtung, zu der eine Menge an Wegen führen. Und weil wir soviel Zeit wie möglich auf dieser sonnigen Lichtung verbringen wollen, möchten wir die Strecke, die uns dahin führt, möglichst kurz halten. Und weil wir die Lichtung sonnig und schön erhalten wollen, brechen wir nicht einfach durchs Gehölz, sondern bleiben brav auf den Wegen. Wir können an jeder Kreuzung abbiegen oder geradeaus laufen, und wenn wir mal Schrödingers Katze in ihrer Kiste lassen, dann sind wir an jedem Punkt unserer Strecke eindeutig irgendwo. Das wäre dann unser Zustand. Ist es nicht tröstlich, immer irgendwo zu sein? Ganz sicher, denn nirgendwo, das ist nicht in unserer vollständigen Beschreibung, dem Nirgendwo rufen wir zu, daß das nicht gilt, drehen ihm eine lange Nase und bleiben irgendwo. Toll.
Aber zurück zum letzten Schritt. (Toll, nicht? Wir sind soweit vorne, daß wir zum letzten Schritt schon zurückgehen müssen!) Wir können also auf unterschiedlichen Wegen zur Lichtung gelangen. Alle diese Wege beginnen an je einer Kreuzung. Sonst kämen wir ja gar nicht hin zu den Wegen. Wir stehen nun auf einer dieser Kreuzungen und wissen: Der direkte Weg zur Lichtung ist der kürzeste. Alle anderen sind länger, da sie eben nicht direkt zur Lichtung führen. Damit ist für den letzten Wegabschnitt bereits ein Zusammenhang zwischen der Kontrollgröße Abbiegen und der Strecke bis zum Ziel hergestellt. Diese kürzeste Strecke notieren wir uns. Nun stellen wir uns vor, wir seien an allen letzten Kreuzungen vor dem Ziel gleichzeitig und können von dort aus die jeweils kürzesten Wege zum Ziel notieren. Was wir in der Rechnung - ganz im Gegenteil zur Wirklichkeit - nicht tun müssen, ist, die Kontrollgröße zu notieren. Es ist also egal, in welche Richtung wir abbiegen, solange wir nur die Strecke nehmen, die auf kürzestem Wege zum Ziel führt. Sowas funktioniert ja auch nur im Märchen, und deshalb kann ich Computer ja nie ganz ernst nehmen. Für jeden Weg, der zu jeder der letzten Kreuzungen vor der Lichtungen führt, können wir das gleiche tun. Das ist toll, das ist Rekursion. Und dann dürfen wir die Strecken einfach aufsummieren, schließlich müssen wir von jeder vorletzten Kreuzung zur letzten und von dort zur Lichtung laufen. Wir erhalten so nach einiger Rechnerei eine Tabelle, die für jede Kreuzung am Waldrand, auf der wir starten könnten, die kürzeste Strecke zum Ziel beschreibt. Nun können wir uns entscheiden, ob wir am Parkplatz starten, oder auf der Kreuzung, in deren Tabelle der kleinste Wert vorkommt. Beides ist rechnerisch legitim, und beides löst ein ganz anderes Problem! Allerdings nicht das des Parkplatzes, das müssen wir alleine hinbekommen. Und so machen wir uns, wie wir zuvor rückwärts unterwegs waren, nun vorwärts auf den Weg. Immer die Tabelle vor der Nase, auf der unser Zustand eingetragen ist, und die Strecken, die in alle Richtungen zu gehen wären. Und da nehmen wir jeweils die kürzeste, richten unsere Kontrollgröße des Abbiegens also an der kleinsten Reststrecke aus und gelangen so nur nächsten Kreuzung. Nehmen wir nun die Anzahl der von einer Kreuzung höchstens abzweigenden Wege (abzüglich des einen, von dem wir kommen) her, so erhalten wir übrigens die Länge unserer Tabelle. Und in der Tabelle, die zum gewünschten Wegbeginn gehört, steht auch schon die kürzeste Strecke zum Ziel. Und wenn wir das alles wissen, sparen wir uns das Laufen vielleicht sogar. Das wiederum kann der Rechner nicht, da er diskretisiert, und damit vielleicht in einem kontinuierlichen Problem Wege und Kreuzungen einzeichnet, obwohl er auch quer durch den Wald laufen könnte und nur um Hindernisse herumgehen muß. Der trifft also vielleicht nicht ganz genau einen der Wege, vielleicht nicht ganz genau eine der Kreuzungen, die er sich durch die Diskretisierung der Kontroll- und Zustandsgröße selbst angelegt hat. Daher muß er beim Vorwärtsgehen noch zwischen den beiden nächstliegenden Kreuzungen die Tabellen interpolieren. Aber das führt nun wirklich in die Irre.
Was dagegen noch sehr toll ist: Die etwas sperrige Idee von oben, daß jede global optimale Entscheidung die Summe lokal optimaler Entscheidung ist, die ist unter der Annahme richtig, daß die letzte Entscheidung vor dem Ziel optimal ist, in Sichtweite des Ziels sozusagen. Daß es ein Ziel gibt. Daß der Weg endlich ist. Daß alle Entscheidungen nacheinander getroffen werden. Schön der Reihe nach. Und daß man immer irgendwo ist. Wie toll das ist, und wie einfach dann das Leben!