Dynamic Programming

Dynamic Programming (dynamisches Programmieren) kann Effizienzverbesserungen erzielen, indem wiederkehrende Teilprobleme (vorsorglich) gelöst werden. Das Wort Programming steht hier für Optimierung (ähnlich wie bei Linear Programming). Optimierung ist zutreffend, da mit Dynamic Progamming Optimierungsprobleme gelöst werden, also Probleme, bei denen ein Minimum bzw. Maximum gefunden werden soll. Die Methode wurde von Richard Bellmann 1940 zur Lösung von Problemen in der Regelungstechnik angewandt.

Wie bei Teile und Herrsche besteht das Ziel darin, ein großes Gesamtproblem in kleinere Subprobleme zu zerlegen und deren Lösungen zu speichern: in einer Hashmap bei Teile und Herrsche und (konzeptionell) in einer Tabelle bei Dynamischem Programmieren. Teile und Herrsche arbeitet top down mit Rekursion und Memoizing. Bei Dynamic Programming geht man bottom up vor und berechnet die Lösungen für alle möglichen Subprobleme, auch wenn einige davon zur Lösung des komplexen Ausgangsproblems gar nicht erforderlich sind. (Auf jeden Fall kann dadurch beim Zusammenbau der Gesamtlösung keine Teillösung fehlen!)

Der Hauptunterschied zwischen Teile und Herrsche einerseits ind Dynamischem Programmieren andererseits besteht also darin, dass die Ablaufsteuerung nicht durch FOR-Schleifen, sondern durch Rekursion mit Memoizing vorgenommen wird.

Wichtig ist die Gültigkeit der Optimalitätsbedingung (s.u.) bei Dynamic Programming. Da sich Teilprobleme in mehreren größeren Problemen wiederfinden können, kann durch das Speichern der Lösungen ein Effizienzgewinn erzielt werden.

Charakteristik des Dynamic Programming:

• Ein jeweils größeres Problem wird in Teilprobleme zerlegt.
• Die optimalen Lösungen der Teilprobleme werden genutzt, um die optimale Lösung eines größeren Problems zu finden.
• Die Optimalitätsbedingung (Principle of Optimality) muss gelten, d.h. die optimale Lösung des Gesamtproblems muss sich zwangsläufig aus den optimalen Lösungen der Teilprobleme ergeben.
• Trade space for time - es wird zusätzlicher Speicherplatz investiert, um den Algorithmus zu beschleunigen.

Das wichtigste Strukturierungsmittel von Dynamic Programming ist eine Tabelle. Die Felder der Tabelle enthalten Werte, die das jeweilige Optimum darstellen. Für deren Berechnung könnte man die mit Teile und Herrsche entwickelte rekursive Verschrift einsetzen. Dynamisches Programmieren sieht jedoch eine zeilenweise Bestimmung der Feldelemente vor. Bis auf ein Feld, das sich in den folgenden Beispielen rechts unten befindet, sind alle Werte Zwischenwerte, auf die die Folgezeilenberechnungen zurückgreifen, ohne sie erneut zu berechnen.

Diese Charakteristik hebt die Überlegenheit des rekursiv definierten Top-Down-Verfahrens (Teile und Herrsche) gegenüber dem Dynamic Programming Bottom-up-Verfahren hervor, denn die Herstellung der Tabellengestalt kann fehlerbehaftet sein, während die rekursive Beziehung bereits die Lösung verkörpert. Außerdem werden durch die rekursive Berechnung nicht alle Tabellenfeldinhalte ermittelt. Um Mehrfachberechnungen auszuschließen wird Memoizing eingesetzt.

Fibonacci-Zahlen

Ein Beispiel, für welches Teile und Herrsche benutzt werden kann, sind die Fibonacci-Zahlen. Es ist sehr einfach, die rekursive Bildungsvorschrift anzugeben:

Dies lässt sich auch schnell programmieren:

Rekursionsbaum

Rekursive Berechnung mit Memoizing

Analysiert man die Zeitkomplexität des oben beschriebenen Algorithmus, so ergibt sich ein exponentieller Aufwand (\Theta(\phi^n), \phi>1), und das für ein Problem, das nicht sehr komplex zu sein scheint. Memoizing kann genutzt werden, um die Fibonacci-Zahlen wesentlich schneller zu berechnen. Durch Memoizing fehlen viele Berechnungsäste des Rekursionsbaumes. Er wächst nicht exponentiell, sondern linear.

Die Grundidee besteht darin, jeden Wert nur einmal ausrechnen zu müssen. Wurde erstmals eine Fibonacci-Zahl berechnet, so wird sie in einem Zwischenspeicher abgelegt und steht zur Verfügung, sobald sie wieder benötigt wird. Hierfür sollte eine Datenstruktur gewählt werden, mit der man in \mathcal{O}(1) den Wert für einen Key lesen kann. Natürlich bietet sich eine Hashmap an, die den Parameter n auf fib(n) abbildet, oder ein Array, bei dem die n-te Fibonacci-Zahl im Index n steht.

Dynamisches Programmieren (Bottom-up)

Klassisches Dynamic Programming ist ein Bottom-Up Verfahren, also ein Algorithmus, der bei einem Blatt des Rekursionsbaums beginnt und schrittweise die nächstgrößeren Werte berechnet. Bei den Fibonacci-Zahlen ist der Bottom-Up Ansatz relativ intuitiv: Ausgehend von den bereits gegebenen Werten von fib(0)=0 und fib(1)=1 berechnet man in einer Schleife von 2 bis n schrittweise den jeweils nächstgrößeren Wert. Da zur Berechnung einer Fibonacci-Zahl, die zwei nächstkleineren Fibonacci-Zahlen benötigt werden, ist sichergestellt, dass die jeweils benötigten Werte vorliegen, denn die Schleife arbeitet "von klein zu groß".

In folgendem nichtrekursiven Programm ist deshalb eine Zählschleife zu sehen.

In beiden Fällen müssen n Fibonacci-Zahlen berechnet werden, deren Zeitaufwände lediglich in \mathcal{O}(1) liegen, da die Werte entweder durch die Verwaltung der Rekursion (Aufstieg aus der Tiefe) oder durch die Ausführung der Schleife bereits vorliegen. Somit ergibt sich insgesamt ein Zeitaufwand in n \cdot \mathcal{O}(1) = \mathcal{O}(n).

Das 0/1-Rucksack-Problem

Um das 0/1-Rucksack-Problem zu lösen, kann Dynamic Programming ebenfalls benutzt werden. Für eine Menge von n Gegenständen, deren individuelles Gewicht und zugehöriger Wert vorgegeben sind, ist eine Auswahlentscheidung zu treffen: Mitnahme im Rucksack mit Kapazität K oder nicht. Das Ziel besteht darin, den Gesamtwert (Summe aller Werte der eingepackten Gegenstände) zu maximieren, ohne mit der Gewichtssumme die Rucksackkapazität K zu überschreiten.

In der folgenden rekursiven Definition des maximalen Gesamtwertes sind i der Index des letzten Gegenstandes in der Gegenstandsliste und K die Kapazität (das maximal zulässige Gewicht, welche der Rucksack tragen kann).

i=0 bedeutet, dass kein einziger Gegenstand in den Rucksack gepackt wird. Der Gesamtwert ist damit gleich 0. Wenn ein weiterer Gegenstand verfügbar ist, mit dessen Aufnahme jedoch die Rucksack-Restkapazität überschritten werden würde, ist der erreichbare Wert gleich dem Wert der Rucksackbefüllung ohne diesen Gegenstand, d.h. nur bis einschließlich Gegenstand i-1. (Dies bedeutet nicht, dass sich Gegenstand i-1 zwangsläufig im optimalen Rucksack befinden muss.)

Wir interpretieren nun die obige rekursive Formel. Wenn der Gegenstand prinzipiell in den Rucksack passt, d.h. die Restkapazität nicht überschreitet, fragt man nach dem größeren der beiden erzielbaren Gesamtwerte:

1. Nimmt man den Gegenstand i in den Rucksack auf, ergibt sich der Wert aus der Summe des Wertes dieses Gegenstands und dem erreichbaren Maximalwert des kleineren Rucksacks, der die Gegenstandsliste bis i-1 berücksichtigt. Die dafür verbleibende Restkapazität wird dann allerdings um das Gewicht des i-ten Gegenstands verringert.

2. Nimmt man den Gegenstand i nicht in den Rucksack auf, bleibt es bei dem über die Gegenstände 0 bis i-1 zu ermittelnden max. Gesamtwert, wofür dann allerdings eine unverminderte Restkapazität zur Verfügung steht.

Gesucht ist der Wert value(n,K). In folgendem Programm findet sich am Ende der Aufruf > value(n, K) bzw. > value_memo(n, K).

Ohne dynamisches Programmieren handelt es sich um einen Exponentialzeit-Algorithmus. k und i stellen die Problemgröße dar. Um den Wert eines Problems mit der Größe i zu berechnen, muss bis zu zweimal (im sonst-Fall) der Wert eines Problems der Größe i-1 berechnet werden. Das heißt die Zeit zur Berechnung der Lösung verdoppelt sich mit jedem Inkrement von i, was zu einer exponentiellen Laufzeit führt.

Durch dynamisches Programmieren kann dies verbessert werden. Anstatt das gleiche Teilproblem immer wieder neu zu berechnen, wird die Lösung in einem Dictionary mit dem Parameter-Paar als Schlüssel gespeichert. Memoizing! Nun kann in vielen Fällen, der Wert aus dem Dictionary wiederverwendet, d.h. in \mathcal{O}(1) gelesen, werden. Da jeder Wert nur einmal berechnet werden muss, ist die Zeit, um das Gesamtproblem zu lösen, das Produkt aus der Anzahl der Teilprobleme und der Zeit für deren Lösung.

Die Zahl der Teilprobleme ist durch die Anzahl nK aller möglichen Tupel \{1,\ldots,n\}\times\{0,\ldots,K\} beschränkt, was sich in einer dem entsprechenden Tabelle niederschlägt. Folglich liegt die Laufzeit des Problems in \mathcal{O}(nK) \cdot \mathcal{O}(1) = \mathcal{O}(nK).

Dies lässt zunächst vermuten, dass wir es geschafft haben, einen Polynomialzeit-Algorithmus für das Rucksackproblem zu entwickeln. Das trifft im Allgemeinen jedoch nicht zu, denn der Wert der Zahl K gehört zur Problemgröße. Das ist sinnvoll, da mit steigendem n auch K anwachsen muss, um eine sinnvolle Problemstellung vorzulegen.

Da Zahlen in einem Computer jedoch nicht unär, sondern mit der Basis 2, dargestellt werden, verdoppelt sich die Größe von K mit jedem Hinzufügen einer Ziffer. Auf die Stelligkeit bezogen hat der Algorithmus also eine Komplexität von \mathcal{O}(n \cdot 2^k). Man spricht in diesem Fall von einem Algorithmus mit pseudo-polynomialer Laufzeit, die als exponentiell angesehen werden muss.

Im Gegensatz zur Berechnung der Fibonacci-Zahlen bleibt das 0/1-Rucksackproblem ein solches, für dessen Lösung bisher kein Polynomzeit-Algorithmus bekannt ist. Die Chancen einen solchen zu finden, stehen leider sehr schlecht.

Das folgende Programm berechnet die Anzahl der Aufrufe für die Tabellenfelder am Beispiel von "Zufallsgegenständen". Der Einfluss von Memoizing ist sehr deutlich.

Beispiel: Zum Abschluss der Betrachtung des 0/1-Rucksackproblems wenden wir die obigen Überlegungen auf ein einfaches Beispiel an. Gegeben ist die folgende (unsortierte) Gegenstandsliste mit n=4 Elementen. Die Kapazität des Rucksacks beträgt K=5.

Die im Folgenden aufgestellte Tabelle verwendet die folgenden Ausfüllregeln.

• value[0,k]=0
• Tabelle zeilenweise ausfüllen, beginnend mit i=0.
  Wenn w[i]>k,
  dann value[i,k]=value[i-1,k],
  sonst value[i,k]=max(value[i-1,k], v[i]+value[i-1,k-w[i]])

Die Formeln geben an, dass man die erforderlichen Zwischenwerte in der vorhergehenden Zeile (i-1) in der angegebenen Spalte findet.

Der Eintrag unten rechts repräsentiert das Ergebnis: value[n,K]=value[4,5]=140.

Interessiert man sich für genau die in den Rucksack eingepackten Gegenstände, so ist eine Rückrechnung erforderlich.

i = n;
k = K;
while i, k > 0 do
    if value[i, k] != value[i - 1, k] then
        markiere das i-te Element;
        k = k - w[i];
    endif;
    i = i - 1;

Ergebnis: Genau die Gegenstände 1 und 4 werden in den Rucksack gepackt. Deren Gewichtssumme beträgt 4 (4<5) und deren Gesamtwert ist 140.

Fazit: Wie dieses Beispiel illustriert, ist die top-down-Verarbeitung, d.h. Verwendung von Rekursion in Verbindung mit Memoizing, schon deshalb eine ernst zu nehmende Alternative zur klassischen bottom-up-Strategie (mit Schleifen), da man den rekursiven Lösungsansatz schnell findet und dessen fehleranfällige Transformation in ein iteratives Verfahren nicht braucht. Die rekursive Lösung findet sich in den Ausfüllregeln für die Tabelle unmittelbar wieder.

Bellman-Ford-Algorithmus

Dynamic Programming kann auch zur Lösung des Single-Source Shortest Path Problem angewandt werden: Gesucht ist der kürzeste Weg von einer Quelle zu einem anderen Knoten in einem Graphen. Der Bellman-Ford-Algorithmus wurde in den Jahren 1956-1958 von Richard Bellman, Lester Ford und Edward F. Moore veröffentlicht. Dieser Algorithmus und darauf aufbauende Verfahren sind prinzipiell für das Routing in Netzwerken geeignet.

Da es sich um Dynamic Programming handelt, stellt sich die Frage, was die Subprobleme sind. Angenommen man hat einen Pfad von v nach u mit v=w_0, w_1,..., w_{k-1}, w_k = u, so ist offensichtlich, dass w_0, w_1, ..., w_{k-1} der kürzeste Pfad zu w_{k-1} ist. Es folgt, dass das Subproblem der kürzeste Weg zu einem der benachbarten Knoten ist, unter Nutzung von einer Kante weniger.

Beweis. Nehmen wir an, dass w_0,...,w_{k-1} nicht der kürzeste Weg zwischen w_0 und w_{k-1} ist, so gibt es einen Pfad w_0,w'_1,...,w'_j,w_{k-1} mit einer kürzeren Länge. Dadurch hat auch w_0,w'_1,...,w'_j,w_{k-1},w_k eine kürzere Länge als w_0,...,w_{k-1},w_k. Dies widerspricht jedoch der Bedingung, dass w_0,...,w_{k-1},w_k der kürzeste Pfad von w_0 nach w_k ist.

Top down

Mit dieser Erkenntnis lässt sich die folgende rekursive Gleichung aufstellen. v ist der Knoten, zu dem der kürzeste Pfad gefunden werden soll. v.adj sind die Elemente der Adjazenz-Liste von v. s ist der Startknoten. k ist die Anzahl der maximal zu benutzenden Kanten und dis(u,v) ist das Kantengewicht von (u,v), d.h. die Entfernung (Distanz) zwischen u und v:

Handelt es sich bei v um den Startknoten s, so sind die Kosten, um zu v zu gelangen 0. Beträgt die Anzahl der maximal zu benutzenden Kanten 0 und handelt es sich bei v nicht um s, so ist v nicht erreichbar und die Funktion gibt \infty zurück. Ansonsten ergibt sich die Lösung aus der kleinsten Summe aus dem Gewicht (Distanz) zu einem der benachbarten Knoten und dem kürzesten Weg dieses benachbarten Knotens unter der Verwendung von k-1 Kanten.

Während beim 0/1-Rucksackproblem nicht jeder Gegenstand zwangsläufig in den Rucksack gepackt werden konnte, muss hier in jedem Schritt einer der adjazenten Knoten auch wirklich genommen werden.

Beispiel:

In folgendem Programm werden diese Beispieldaten verwendet.

Bottom Up

Video

Auch für den Bellman-Ford-Algorithmus lässt sich ein Bottom Up-Ansatz angeben. Dabei werden zunächst der Startknoten mit der Distanz 0 und alle anderen Knoten mit der Distanz \infty initialisiert. \infty dient dabei quasi als Platzhalter und steht für "nicht erreichbar".

Danach werden alle Kanten (u, v) \in E durchiteriert und ein Wert für die Distanz zum Knoten v zugewiesen. Dieser Wert ist entweder die Summe aus der bisher gefundenen Distanz zu u und dem Gewicht (der Distanz) zwischen u und v oder dem bisherigen Wert für die Distanz zu v. Dabei wird das Minimum, also der kleinere der beiden Werte, genommen, da der kürzeste Weg gefunden werden soll.

Dieser Vorgang wird \lvert V \rvert - 1 mal wiederholt, da der kürzeste Weg zwischen zwei Knoten maximal über \lvert V \rvert - 1 Knoten verläuft, da er sonst mehrfach durch den gleichen Knoten gehen würde und es sich somit um einen Kreis innerhalb des Weges handelt, welcher nicht der kürzeste Weg sein kann. Sollte sich herausstellen, dass für \lvert V \rvert Iterationen sich kürzere Wege ergeben als nach \lvert V \rvert - 1 Iterationen, so muss es einen negativen Kreis (negative weight cycle) innerhalb des Graphen geben. Andernfalls wurden die kürzesten Wege ausgehend vom Startknoten gefunden und es existiert kein negativer Kreis im Graphen.

Für die Implementation dieser Variante des Bellman-Ford Algorithmus wird nicht die oben definierte Datenstruktur Node, sondern eine Liste aller Knoten (identifiziert als String) und eine Liste aller Kanten genutzt.

Dieser Ausgabe lässt sich entnehmen, dass der kürzeste Weg von d nach a das Gewicht -2 hat: d (-3) e (2) b (-1) a. -3 + 2 -1 = -2.

Durch die zwei Schleifen ist ersichtlich, dass der Bellman-Ford Algorithmus eine Laufzeit von \mathcal{O}(\lvert V \rvert \cdot \lvert E \rvert) hat. Damit ist er ineffizienter als vergleichbare Algorithmen, wie der Dijkstra Algorithmus, jedoch hat Bellman-Ford den Vorteil, dass er mit negativen Gewichten der Kanten umgehen kann und das korrekte Ergebnis liefert.

Sucht man die kürzesten Wege zwischen allen Knotenpaaren eines Graphen, liegt der Zeitaufwand in \mathcal{O}(|V|^2\cdot |E|). Dann ist ggf. der Floyd-Warshall-Algorithmus vorzuziehen: Er basiert auch auf Dynamischem Programmieren und hat einen Aufwand in \mathcal{O}(|V|^3).

Rundreiseproblem

Ein ganz ähnliches Problem wie die Kürzeste-Wege-Fragestellung ist die Frage nach der kürzesten Rundreise, die alle vorgegebenen Städte genau einmal besucht. Es ist unter dem Namen Traveling Salesman Problem (TSP) bekannt. Die Planung solcher Touren ist sicher nicht nur für die Auftrittsplanung von Künstlern und für Reiseunternehmen mit logistischem Anspruch von Interesse.

Intuitiv stellt sich die Vermutung ein, dass es sich hierbei um einen Sonderfall des o.g. Problems handelt, für das sich eine Lösung mit den vorgestellten bzw. genannten Algorithmen in \mathcal{O}(n^3) oder sogar \mathcal{O}(n^2) ergibt. n ist die Anzahl der beteiligten Städte. Die Intuition trügt: Bis heute ist kein Verfahren bekannt, dass das Rundreiseproblem mit weniger als exponentiellem Zeitaufwand (exakt) löst. Nur Näherungsverfahren schaffen das.

Leider kann dynamisches Programmieren an dieser Tatsache nichts ändern. Wir prüfen die Anwendbarkeit: In der Tat ist die Optimalitätsbedingung erfüllt. Ein Weg, der o.B.d.A. bei Stadt i=1 beginnt (und endet), direkt zu der e_{i,j} entfernten Stadt j führt und danach auf dem Weg zurück zu Stadt 1 alle Städte aus \{2,3,4,\ldots,n\}\setminus\{j\} genau einmal besucht, ist minimal, wenn eben dieser Weg von j nach 1 minimal ist.

Auf dieser Basis können wir ein Top-Down-Lösung wie folgt beschreiben. Natürlich gehen wir davon aus, dass eine Adjazenzmatrix mit den entsprechenden Entfernungen e zwischen je zwei Stäten vorliegt. Mit S=\{2,3,4,\ldots, n\} gilt

Der Funktionswert weg(1,S) liefert den kürzesten Rundweg.

Für ein iteratives Verfahren einer Bottom-up-Lösung organisiert man eine Tabelle mit n Spalten, nämlich für 2,3,4,\ldots,n,1, und 2^{n-1} Zeilen für alle möglichen Städtemengen, d.h. für die Potenzmenge \wp(S). Das ergebnistragende Feld in der Tabelle ist das in Zeile \{2,3,4,\ldots,n\}, Spalte 1. Wenn man zur Berechnung jedes Tabellenfeldes einen linearen Aufwand veranschlagt, ergibt sich insgesamt \mathcal{O}(n^22^n).

Beispiel: Wir betrachten ein asymmetrisches TSP mit folgender Entfernungsmatrix

Die Tabelle für Dynamic Programming (Buttom up) hat folgende Struktur. Zu beachten ist der, dass sich der erste Parameter von >weg(i,S) aus dem Spaltenindex ergibt.

Die Ausfüllregeln der Tabelle folgen der obigen rekursiven Vorschrift, die für das top-down-Verfahren entwickelt wurde.

Geldwechselproblem

Beim Geldwechselproblem geht es darum, einem Kunden für die Restgeldbetrag-Rückgabe möglichst wenige Münzen heraus zu geben. Es wird also zunächst nach allen möglichen Münzkombinationen, die einen vorgegebenen Betrag ergeben, gefragt. Unter diesen sucht man dann die mit den wenigsten Geldstücken heraus. Dabei ist eine Liste aller verfügbaren (positiven) Münzprägungen (1ct, 2ct, 5ct, 10ct, 50ct, 1€, 2€) gegeben. Es wird angenommen, dass alle Münzwerte beliebig oft zur Verfügung stehen.

Für die Lösung des Geldwechselproblems gibt es auch ein Greedy-Verfahren.

Ein entsprechender Dynamic-Programming-Ansatz ergibt sich folgendermaßen: Angenommen, man möchte 54ct wechseln und die verfügbaren Münzprägungen sind: 20ct, 10ct, 5ct und 2ct. Wir betrachten nur die erste dieser vier Münzprägungen, nämlich 20ct. Zunächst könnte man sich entscheiden, kein 20ct-Stück zu benutzen und lediglich die in der sortierten Liste der Münzprägungen nachfolgenden Münzstücke verwenden. Man könnte sich auch entscheiden, genau ein 20ct-Stück zu verwenden. In diesem Fall müssen mit den restlichen Münzen nur noch 34ct gewechselt werden. Genauso könnten genau zwei 20ct-Stücke verwendet werden und entsprechend 14ct mit den restlichen Münzen zusammengelegt werden. Die Möglichkeit, drei 20ct-Stücke zu verwenden, steht nicht zur Verfügung, da dies bereits die 54ct überschreiten würde.

Allgemein gilt: Sei N der zu wechselnde Betrag und k der Wert der zu untersuchenden Münze, so kann die Münze 0-mal bis n = \left\lfloor\frac{N}{k}\right\rfloor-mal verwendet werden.

Hinweis. f: \mathbb{R} \to \mathbb{Z} mit f(x) = \lfloor x \rfloor beschreibt die floor-Funktion, bei der die Zahl auf die nächst kleinere ganze Zahl abgerundet wird.

Jetzt müssen für die rekursive Definition noch die Elementarfälle gebildet werden. Beträgt der zu wechselnde Betrag N = 0, so gibt es genau eine Möglichkeit, diesen Betrag zu bilden, nämlich indem man keine Münze verwendet. Ist der zu wechselnde Betrag N negativ, so gibt es keine Möglichkeit diesen Betrag zu bilden, da alle Münzen einen positiven Wert haben.

 N  coin change ways
 0                 1
 1                 1
 2                 2
 3                 2
 4                 3
 5                 4
 6                 5
 7                 6
 8                 7
 9                 8
10                11
11                12
12                15
13                16
14                19
15                22
16                25
17                28
18                31
19                34
20                41

Weitere Dynamic-Programming-Algorithmen

Es gibt eine Reihe von Verfahren, die nach dem Dynamic-Programming-Prinzip arbeiten. Zwei davon sind:

• CYK-Verfahren zur Feststellung, ob ein Wort der Länge n zur Sprache L(G) gehört oder nicht. G ist eine kontextfreie Grammatik in Chomsky-Normalform. Die Komplexität von CYK beträgt \mathcal{O}(n^3).
• Die Matrix-Kettenmultiplikation gewinnt eine verbesserte Komplexität in Höhe von \mathcal{O}(n^3) durch Veränderung der Auswertungsreihenfolge der Multiplikation der n Matrizen.