G.Heyer Algorithmen und Datenstrukturen 2 1 Dynamische Programmierung Das Prinzip „Teile und Herrsche“ diente als Grundlage für die Entwicklung vieler

G.Heyer Algorithmen und Datenstrukturen 21

Dynamische ProgrammierungDas Prinzip „Teile und Herrsche“ diente als Grundlage für die Entwicklung vieler der untersuchten Algorithmen.

Um ein umfangreiches Problem zu lösen, zerlege man es in kleinere Probleme, die unabhängig voneinander gelöst werden können. In der dynamischen Programmierung wird dieses Prinzip bis zum Extrem weiterentwickelt: Wenn nicht bekannt ist, welche kleineren Probleme zu lösen sind, löst man einfach alle und speichert dann die Ergebnisse zum Zwecke der späteren Verwendung bei der Lösung größerer Probleme.Dieser Ansatz ist in „Operations Research“ weit verbreitet. Hierbei bezieht sich der Begriff „Programmierung“ auf den Prozess der Formulierung der Bedingungen eines Problems, um das Verfahren anwendbar zu machen.


Prinzip und Voraussetzung1. Charakterisiere den Lösungsraum und die Struktur der intendierten optimalen Lösung2. Definiere rekursiv, wie sich eine optimale Lösung (und der ihr zugeordnete Wert) aus kleineren optimalen Lösungen (und deren Werte) zusammensetzt.3. Konzipiere den Algorithmus in einer bottom-up Weise so, dass für n=1,2,3, ... tabellarisch optimale Teillösungen (und deren zugeordnete Werte) gefunden werden. Beim Finden einer bestimmten optimalen Teillösung der Größe k>1 ist auf alle optimalen Teillösungen der Größe < k zurückzugreifen.

Voraussetzung: Die optimale Lösung für ein Problem der Größe n setzt sich aus optimalen Teillösungen kleinerer Größe zusammen. (Bellmannsches Optimalitätsprinzip)


Bei der Anwendung der dynamischer Programmierung könnenzwei Schwierigkeiten auftreten:- Erstens muss es nicht immer möglich sein, die Lösungen

kleinerer Probleme so zu kombinieren, dass sich die Lösung eines größeren Problems ergibt.

- Zweitens kann die Anzahl der zu lösenden Probleme unvertretbar groß sein.

Es ist noch nicht gelungen, genau anzugeben, welche Probleme mit Hilfe der dynamischen Programmierung in effizienter Weise gelöst werden können; es gibt viele „schwierige“ Probleme, für die sie nicht anwendbar zu sein scheint, aber auch viele „leichte“ Probleme, für die sie weniger effizient ist als Standardalgorithmen.


Das Produkt mehrerer MatrizenEin klassischer Anwendungsfall der dynamischen

Programmierung ist das Problem der Minimierung des Rechenaufwands, der für die Multiplikation einer Reihe von Matrizen unterschiedlicher Dimension erforderlich ist.a11 a12

a21 a22

a31 a32

a41 a42

b11 b12 b13

b21 b22 b23

c11

c21

c31

d11 d12

e11 e12

e21 e22

f11 f12 f13

f21 f22 f23

4 x 2 2 x 3 3 x 1 1 x 2 2 x 2 2 x 3Ziel: Multiplikation der 6 MatrizenNatürlich muss die Anzahl der Spalten in einer Matrix stets mit der Anzahl der Zeilen in der folgenden Matrix übereinstimmen, damit die Multiplikation ausführbar ist.


Die Gesamtanzahl der erforderlichen Skalar-Multiplikationenhängt von der Reihenfolge ab, in der die Matrizen multipliziert

werden.Im Beispiel könnte man von links nach rechts vorgehen:A x B 24 Skalar-Multipl. neue Matrix M1 4 x 3M1 x C 12 Skalar-Multipl. neue Matrix M2 4 x 1M2 x D 8 Skalar-Multipl. neue Matrix M3 4 x 2. . . nach 84 Skalar-Multipl. Ergebnismatrix 4 x 3Geht man statt dessen von rechts nach links vor, erhält man als Ergebnis die gleiche Matrix der Dimension 4 x 3 nach nur 69 Skalarmultiplikationen .Es sind auch noch viele andere Reihenfolgen möglich.


Die Reihenfolge der Multiplikation kann durch das Setzenvon Klammern ausgedrückt werden, z. B. entspricht die

Reihenfolge von links nach rechts dem Ausdruck( ( ( ( ( AB ) C ) D ) E ) F )

und die Reihenfolge von rechts nach links dem Ausdruck( A ( B ( C ( D ( EF ) ) ) ) ).

Jedes zulässige Setzen von Klammern führt zum richtigen Ergebnis, doch wann ist die Anzahl der Skalar-Multiplikation am kleinsten?Wenn große Matrizen auftreten, können beträchtliche Einsparungen erzielt werden:Wenn z. B. die Matrizen B, C und F im obigen Beispiel eine Dimension von 300 statt von 3 besitzen, sind bei der Reihenfolge von links nach rechts 6024 Skalar-Multipl. erforderlich, bei der Reihenfolge von rechts nach links dagegen die astronomische Zahl von 274 200 Multiplikationen auszuführen.


Demnach ergibt die Multiplikation einer Matrix derDimension p x q mit einer Matrix der Dimension q x r eine

Matrix der Dimension p x r, wobei jedes Element mit Hilfe von q Multiplikationen berechnet wird, so dass insgesamt

p q r Multiplikationen ausgeführt werden müssen.

Allgemeiner Fall: N Matrizen sind miteinander zu multiplizieren:

M1 M2 M3 ... Mn

wobei die Matrizen der Bedingung genügen, dass

Mi für 1 i < N ri Zeilen und ri+1 Spalten ausweist.

Ziel: Diejenigen Reihenfolge der Multiplikation der Matrizen zu finden, für die die Gesamtzahl der auszuführenden Skalar-Multiplikationen minimal wird.


Die Anzahl der Reihenfolgen ist eine kombinatorische Funktion, die Katalanische Zahl genannt wird; die Anzahl der Möglichkeiten, N Variablen zu klammern, beträgt ungefähr

4 N-1 / N N

Die Lösung des Problems mit Hilfe der dynamischen Programmierung besteht darin, „von unten nach oben“ vorzugehen und berechnete Lösungen kleiner Teilprobleme zu speichern, um eine wiederholte Rechnung zu vermeiden.

Um die beste Möglichkeit zu ermitteln, M1M2M3 zu multiplizieren, entnehmen wir zuerst der gespeicherten Tabelle die Kosten der Berechnung von M1M2 und addieren dann die Kosten der Multiplikation dieses Ergebnisses mit M3 dazu. Diese Summe wird mit den Kosten verglichen, die enstehen, wenn zuerst die Multiplikation M2M3 ausgeführt und dann mit M1 multipliziert wird, was auf die gleiche Weise berechnet werden kann.


Die kleinere der beiden Summen wird gespeichert und ebensowird mit allen anderen Tripeln verfahren. Anschließend berechnet man unter Berücksichtigung aller Informationen die beste Möglichkeit Quadrupel Matrizen zu multiplizieren. Indem man in dieser Weise fortfährt, findet man schließlich die beste Möglichkeit, alle Matrizen miteinander zu multiplizieren.Für 1 j N - 1 ermittelt man die minimalen Kosten der Berechnung von Mi M i+1 . . . M i + j‘ indem man für 1 i N-j und für jedes k zwischen i und i + j die Kosten der Berechnung von M i M i + 1 . . . Mk-1 ermittelt und dann die Kosten addiert, die bei der Multiplikation dieser Ergebnisse entstehen. Da man stets eine Gruppe in zwei kleinere Gruppen zerlegt, braucht man die minimalen Kosten für die beiden Gruppen nur aus einer Tabelle zu entnehmen und nicht neu zu berechnen.


Dies führt zu folgendem Programm:

for ( i = 1 ; i <= N ; i++ )

for ( j = i + 1 ; j < = N ; j++ ) cost [i] [j] = INT_MAX ;

for ( i = 1 ; i <= N ; i++ ) cost [i] [i] = 0 ;

for ( j = 1 ; j < N ; j++ )

for ( i = 1 ; i <= N - j ; i++ )

for ( k = i + 1 ; k <= i + j ; k++ )

{ t = cost [i][k - 1] + cost [k][i+j] + r[i] * r[k] * r[i+j+1];

if ( t < cost [i][i+j] )

{ cost [i][i+j] = t ; best [i][i+j] = k ; }

}


cost [l][r] gibt die minimalen Kosten der Berechnung vonMl M l+1 . . . Mr an;

die Kosten für die erste oben angegebene Gruppe betragen cost [i][k-1],

die Kosten für die zweite Gruppe cost [k][i + j] .

Die Kosten für die abschließenden Multiplikationen lassen sich leicht bestimmen: Mi Mi+1 . . M k-1 ist eine Matrix der Dimension r i x r k‘ und M k M k+1 ... M i+j ist eine Matrix der Dimension rk x r i+j+1, so dass die Kosten der Multiplikation dieser beiden Matrizen ri rk r i+j+1 betragen. Auf diese Weise berechnet das Programm cost [i][i+j] für 1 i N - j, wobei j von 1 bis N-1 wächst. Wenn man j = N - 1 erreicht

(und i = 1), hat man die gesuchten minimalen Kosten der Berechnung M1 M2 . . . MN gefunden.


Die getroffenen Entscheidungen werden in einem getrenntenFeld best registriert, um sie später, wenn die tatsächliche

Folge der Multiplikationen erzeugt werden soll, wieder bestimmen zu können.Das folgende Programm stellt die Implementation dieses Prozesses der Ermittlung der optimalen Anordnung der Klammern anhand der mit Hilfe des obigen Programms berechneten Felder cost und best dar. order (int i, int j )

{ if (i == j ) printf ( „%c“ , name ( i ) ) ; else { printf ( „(„ ) ; order ( i, best [i][j] -1) ; order (best[i][j], j );

printf ( „)“ ) ;}

}


Lösung des Problems der Multiplikation mehrerer MatrizenB C D E F

A 24 14 22 26 36[A][B] [A][BC] [ABC][D] [ABC][DE] [ABC][DEF]

B 6 10 14 22 [B][C] [BC][D] [BC][DE] [BC][DEF]

C 6 10 19 [C][D] [C][DE] [C][DEF]

D 4 10 [D][E] [DE][F]

E 12 [E][F]


Beschreibung zur TabelleSie zeigt den Ablauf der oben gezeigten Programme für das

angegebene Beispiel.Sie gibt die Gesamtkosten und die optimale „letzte“ Multiplikation für jede Teilfolge in der Liste der Matrizen an. Z. B. besagt die Eintragung in der Zeile A und der Spalte F, dass 36 Skalar-Multiplikationen erforderlich sind, um die Matrizen A bis F zu multiplizieren, und dass dies erreicht werden kann, indem A bis C auf optimale Weise multipliziert werden, dann D bis F auf optimale Weise multipliziert werden und danach die erhaltenen Matrizen miteinander multipliziert werden. Nur D ist in dem Feld best enthalten.Für obiges Beispiel ist die ermittelte Anordnung der Klammern ( (A ( BC ) ) ( ( DE ) F ) , wofür nur 36 Skalar-Multiplikationen benötigt werden. Für das Beispiel, wo die Dimension von 3 auf 300 geändert wurde, ist die gleiche Anordnung der Klammern optimal, wobei hier 2412 Skalar-Multiplikationen erforderlich sind.


Eigenschaft: Mit Hilfe der dynamischen Programmierung kann das Problem der Multiplikation mehrerer Matrizen in einer zu N3 proportionalen Zeit und mit einem zu N2 proportionalen Speicheraufwand gelöst werden.


Beispiel: Traveling Salesman Problem (TSP)

Gegeben: n Städte, Entfernungsmatrix M = (mij), mij Entfernung von Stadt i nach Stadt j.

Gesucht: Rundreise über alle Städte mit minimaler Länge, also Permutation : {1,...,n} -> {1,...,n} so daß

NP-vollständig (Rechenzeit mit großer Sicherheit exponentiell)

Naiver Algorithmus: alle (n-1)! viele Reihenfolgen betrachten.

c(p) = m(i),(i+1) + m(n),(1) minimal.n-1

i=1


Dynamische Programmierung:

Sei g (i,S) Länge des kürzesten Weges von i über jede Stadt in S (jeweils genau 1 Besuch) nach Stadt

1. Lösung des TSP also g(1, {2,...,n}). (Stadt 1 kann beliebig gewählt werden, da Rundreise gesucht wird)

Es gilt:

g(i,S) = mi1 falls S = {}minjS (mij + g ( j, S -{ j } ) sonst


Algorithmus konstruiert Tabelle :

for ( i = 2 ; i = n; i++) g[i,{}] = mi1

for ( k = 1; k = n-2 ; k++ ) for (S, |S| = k, 1S ) for (i {2,...,n} - S ) Berechne g[i,S] gemäß FormelBerechne g[1,{ 2,...,n } gemäß Formel

Komplexität: Tabellengröße * Aufwand TabelleneintragGröße: < n 2n (Anzahl der i's mal Anzahl betrachtete

Teilmengen)Tabelleneintrag: Suche nach Minimum unter j aus S: O(n)Insgesamt: O(n22n), deutlich besser als (n-1)! .


Beispiel: 4 Städte, symmetrische Entfernungen, M:

1 2 3 4 1 0 4 9 8 2 4 0 12 2 3 9 12 0 10 4 8 2 10 0

Tabelleneinträge:

g[2,{}] = 4g[3,{}] = 9g[4,{}] = 8

g[2,{3}] = 12 + 9 = 21g[2,{4}] = 2 + 8 = 10g[3,{2}] = 12 + 4 = 16g[3,{4}] = 10 + 9 = 19g[4,{2}] = 2 + 4 = 6g[4,{3}] = 10 + 9 = 19


Lösung: 1, 2, 4, 3, 1

g[2,{3,4}] = min(m23 + g[3,{4}] , m24 + g[4,{3}] ) = 21g[3,{2,4}] = min(m32 + g[2,{4}] , m34 + g[4,{2}] ) = 16g[4,{2,3}] = min(m42 + g[2,{3}] , m43 + g[3,{2}] ) = 23

g[1,{2,3,4}] = min(m12 + g[2,{3,4}] , m13 + g[3,{2,4}], m14 + g[4,{2,3}])

= 25


Das Rucksack-ProblemEin Dieb, der einen Safe ausraubt, findet in ihm N Typen von Gegenständen unterschiedlicher Größe und unterschiedlichen Werts, hat aber nur einen kleinen Rucksack der Größe M zur Verfügung, um die Gegenstände zu tragen.Das Rucksack-Problem besteht darin, diejenige Kombination von Gegenständen zu finden, die der Dieb für seinen Rucksack auswählen sollte, so dass der Gesamtwert der von ihm geraubten Gegenstände maximal wird.

Beispiel: Der Rucksack besitzt ein Fassungsvermögen von 17, der Safe enthält viele Gegenstände mit unterschiedlichen Größen und den angegebenen Werten.(Die Bezeichnungen der Gegenstände werden im Programm in Indizes umgewandelt.)


Abbildung zum Rucksack-Problem

3 4 7 8 9

Größe

Wert 4 5 10 11 13Bezeichnung A B C D EDer Dieb kann dann 5 Gegenstände A ( jedoch nicht 6) mitnehmen, so dass die gesamte Beute den Wert 20 hat, oder er kann seinen Rucksack mit einem D und einem E füllen, was einen Gesamtwert von 24 ergibt, oder er kann andere Kombinationen ausprobieren. Doch für welche Kombination wird der Gesamtwert maximal?


Bedeutung des Rucksack-Problems auch imkommerziellen Bereich:z. B. ist es für eine Reederei von Interesse, die beste Möglichkeit zu kennen, wie ein Lastkraftwagen oder ein Transportflugzeug mit Gütern für die Verschiffung beladen werden kann.

Bei solchen Anwendungsfällen können auch andere Varianten des Problems auftreten: Es könnte z. B. sein, dass von jedem Gegenstand nur eine begrenzte Anzahl vorhanden ist.

Für viele solche Varianten ist der gleiche Ansatz geeignet.

Zur Lösung des Rucksack-Problems mit Hilfe der dynamischen Programmierung berechnet man die beste Kombination für alle Größen eines Rucksacks bis M.


Diese Berechnung kann in sehr effizienter Weise realisiertwerden, indem die Operationen in einer zweckmäßigen

Reihenfolge ausgeführt werden:

for ( j = 1 ; j <= N ; j ++ )

{ for ( i = 1 ; i <= M ; i++ )

if ( i >= size [ j ] )

if ( cost [i] < cost [i - size [j] ] + val [j] )

{

cost [i] = cost [i - size [j]] + val [j];

best [i] = j ;

}

}


In diesem Beispiel ist:cost [i] der größte Wert, der mit einem Rucksack mit

dem Fassungsvermögen i erzielt werden kann,best [i] ist das letzte Element, das hinzugefügt wurde, um

das Maximum zu realisieren.Zuerst berechnet man für alle Größen des Rucksacks den maximalen Wert, wenn nur Elemente vom Typ A verwendet werden, danach berechnet man den maximalen Wert, wenn nur Elemente A und B verwendet werden usw. Die Lösung reduziert sich auf eine einfache Berechnung von cost [i].Annahme: Auswahl des Elements j für den Rucksack, dann wäre der beste Gesamtwert, der erzielt werden könnteval [j] (für das Element) + cost [i - size [j]] (um den Rest des Rucksacks aufzufüllen) . Wenn dieser Wert den besten Wert übersteigt, der ohne ein Element j erreicht werden kann, aktualisiert man cost [i] und best [i]; andernfalls lässt man diese Größen unverändert.


Lösung des Rucksack-Problems k 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17j = 1 cost [k] 4 4 4 8 8 8 12 12 12 16 16 16 20 20 20 best [k] A A A A A A A A A A A A A A Aj = 2 cost [k] 4 5 5 8 9 10 12 13 14 16 17 18 20 21 22 best [k] A B B A B B A B B A B B A B Bj = 3 cost [k] 4 5 5 8 10 10 12 14 15 16 18 20 20 22 24 best [k] A B B A C D A C C A C C D C Cj = 4 cost [k] 4 5 5 8 10 11 12 14 15 16 18 20 21 22 24 best [k] A B B A C D A C C A C C D C Cj = 5 cost [k] 4 5 5 8 10 11 13 14 15 17 18 20 21 23 24 best [k] A B B A C D E C C E C C D E C


Erklärung zur Lösung des BeispielsDas erste Zeilenpaar zeigt den maximalen Wert (den Inhalt

der Felder cost und best ), wenn nur Elemente A benutzt werden;das zweite Zeilenpaar zeigt den maximalen Wert, wenn nur Elemente A und B verwendet werden, usw.Der höchste Wert, der mit einem Rucksack der Größe 17 erreicht werden kann, ist 24.Im Verlaufe der Berechnung dieses Ergebnisses hat man auch viele Teilprobleme gelöst, z. B. ist der größte Wert, der mit einem Rucksack der Größe 16 erreicht werden kann, 22, wenn nur Elemente A, B und C verwendet werden.Der tatsächliche Inhalt des optimalen Rucksacks kann mit Hilfe des Feldes best berechnet werden. Per Definition ist best[M] in ihm enthalten, und der restliche Inhalt ist der gleiche wie im optimalen Rucksack der Größe

M - size [best [M]] usw.


Eigenschaft:Für die Lösung des Rucksack-Problems mit Hilfe der

dynamischen Programmierung wird eine zu N M proportionale Zeit benötigt.Somit kann das Rucksack-Problem leicht gelöst werden, wenn M nicht groß ist; für große Fassungsvermögen kann die Laufzeit jedoch unvertretbar groß werden.Eine grundlegende Schwierigkeit ist es, das das Verfahren nicht anwendbar ist, wenn M und die Größen oder Werte z. B. reelle Zahlen anstatt ganzer Zahlen sind.Wenn jedoch die Fassungsvermögen sowie die Größen und Werte der Gegenstände ganze Zahlen sind, so gilt das grundlegende Prinzip, dass optimale Entscheidungen nicht geändert werden müssen, nachdem sie einmal getroffen wurden.Jedesmal, wenn dieses allgemeine Prinzip zur Anwendung gebracht werden kann, ist die dynamische Programmierung anwendbar.


Optimale binäre SuchbäumeBei vielen Suchanwendungen ist bekannt, dass die

Suchschlüssel mit stark variierenden Häufigkeiten auftreten können, z. B. wird ein Programm, das die Schreibweise von Wörtern in einem deutschen Text prüft, wahrscheinlich viel öfter nach Wörtern wie „und“ und „der“ suchen, als nach Wörtern wie „dynamische“ und „Programmierung“.In ähnlicher Weise wird ein C-Compiler sicher weit häufiger Schlüsselwörter wie „if“ und „for“ aufsuchen, als „goto“ oder „ main“.Wenn Suche in einem Binärbaum angewandt wird, ist es vorteilhaft, die am häufigsten gesuchten Schlüssel in der Nähe der Spitze des Baumes anzuordnen. Um zu bestimmen, wie die Schlüssel im Baum anzuordnen sind, so dass die Gesamtkosten der Suche minimiert werden, kann ein Algorithmus der dynamischen Programmierung benutzt werden.


Jeder Knoten im binären Suchbaum ist mit einer ganzen Zahlgekennzeichnet, von der angenommen wird, dass sie der

Häufigkeit des Zugriffs auf diesen Knoten entspricht.

Das besagt, dass zu erwarten ist, dass bei jeweils 18 Suchvorgängen (im Beispielbaum) in diesem Baum viermal nach A gesucht wird, zweimal nach B, einmal nach C usw.

Bei jedem der vier Suchvorgänge, die A betreffen, sind zwei Zugriffe auf Knoten erforderlich, bei jedem der zwei Suchvorgänge, die B betreffen, drei Zugriffe auf Knoten usw. Man kann ein Maß für die „Kosten“ des Baumes berechnen, indem man die jedem Knoten zugeordnete Häufigkeit mit seinem Abstand von der Wurzel multipliziert und dann die Summe dieser Produkte bildet. Dies ist die gewichtete innere Pfadlänge des Baumes.


Ein binärer Suchbaum mit HäufigkeitenC

E

D

F

B

A

G

1

32

4

5

1

2

Für diesen Baum beträgt die gewichtete innere Pfadlänge

4 * 2 + 2 * 3 + 1 * 1 + 3 * 3 + 5 * 4 + 2 * 2 + 1 * 3 = 51 .

Ziel: Für die gegebenen Schlüssel mit den gegebenen Häufigkeiten den binären Suchbaum bestimmen, der unter allen solchen Bäumen die kleinste innere Pfadlänge besitzt.


Dieses Problem weist Ähnlichkeiten zu dem Problem der

Minimierung der gewichteten äußeren Pfadlänge auf, das bei der Betrachtung der Huffman-Codierung untersucht wurde.

Bei der Huffman-Codierung war es jedoch nicht erforderlich, die Reihenfolge der Schlüssel beizubehalten; bei dem binären Suchbaum muss die Eigenschaft erhalten bleiben, dass alle links von der Wurzel befindlichen Knoten Schlüssel besitzen, die kleiner sind usw.

Diese Forderung bewirkt, dass das Problem dem oben betrachteten Problem der Multiplikation mehrerer Matrizen sehr ähnlich ist; es kann praktisch das gleiche Programm verwendet werden.


Annahme: Gegeben: Menge von Suchschlüsseln K1 < K2 < ... < KN und

Menge von zugehörigen Häufigkeiten r0, r1, . . . ,rN

wobei ri die vermutete Häufigkeit des Zugriffs auf den Schlüssel Ki ist.Ziel: Bestimmung des binären Suchbaums, für den die über alle Schlüssel gebildete Summe der Produkte dieser Häufigkeiten mit den Abständen des Schlüssels von der Wurzel ( den Kosten des Zugriffs auf den entsprechenden Knoten) minimal wird.Der Zugang zu diesem Problem mittels dynamischer Programmierung besteht darin, der Reihe nach für jedes

1 j N - 1 die beste Möglichkeit zu berechnen, einen Unterbaum zu erzeugen, der

Ki, Ki+1, ... , Ki + j für 1 i N - j enthält.


Implementierungfor ( i = 1 ; i <= N ; i++ ) for ( j = i +1; j <= N+1 ; j++ ) cost[i] [j] = INT_MAX ;for ( i = 1 ; i <= N ; i++ ) cost[i] [i] = f [i];for ( i = 1 ; i <= N+1; i++ ) cost[i] [i-1] = 0 ;for ( j = 1 ; j <= N - 1 ; j++ ) for ( i = 1 ; i <= N - j ; i++ )

{ for ( k = i ; k <= i + j ; k++ ) { t = cost[i] [k - 1] + cost[k+1] [i + j] ;

if ( t < cost[i] [i+j] ) { cost[i] [i + j] = t ; best[i] [i+j] = k ; }

} for ( k = i ; k <= i + j ; cost[i] [i+j] += f[k++] ) ; }


Für jedes j wird die Berechnung ausgeführt, indem jeder Knoten als Wurzel ausprobiert wird und im voraus berechnete Werte verwendet werden, um die beste Möglichkeit zur Erzeugung der Unterbäume zu ermitteln.

Für jedes i k i + j möchte man den optimalen Baum mit Kk als Wurzel finden, der Ki , Ki+1 , . . . , Ki+j enthält.

Dieser Baum wird gebildet, indem der optimale Baum für

Ki , Ki+1 , . . . , Kk-1 als der linke Unterbaum und der optimale Baum für Kk+1 , K k+2 , . . . , K i+j als der rechte Unterbaum verwendet wird. Die innere Pfadlänge dieses Baumes ist gleich der Summe der inneren Pfadlänge der beiden Unterbäume und der Summe der Häufigkeiten für alle Knoten (da jeder Knoten in dem neuen Baum einen Schritt weiter von der Wurzel entfernt ist).


Optimaler binärer Suchbaum D

E

F

GC

B

A4

1

2

53

2

1Die gewichtete innere Pfadlänge dieses Baumes beträgt 41.Man muss beachten, dass die Summe aller Häufigkeiten jedesmal zu den Kosten addiert wird, weshalb sie für die Bestimmung des Minimums nicht benötigt wird. Weiterhin muss cost[i][i - 1] = 0 gelten, um die Möglichkeit zu berücksichtigen, dass ein Knoten nur einen Nachfolger hat (beim Problem der Multiplikation mehrerer Matrizen gab es keine analoge Möglichkeit).Wie zuvor ist ein kurzes rekursives Programm erforderlich, um anhand des mit Hilfe des Programms berechneten Felds best den eigentlichen Baum zu rekonstruieren.


Eigenschaft:Das Verfahren der dynamischen Programmierung zur

Bestimmung eines optimalen binären Suchbaums erfordert einen zu N3 proportionale Zeit und einen zu N2 proportionalen Speicherplatz.

Der Algorithmus arbeitet wieder mit einer Matrix der Größe N2 und benötigt für jedes Element eine zu N proportionale Zeit.

In Wirklichkeit ist es in diesem Falle möglich, die erforderliche Zeit auf N2 zu reduzieren, indem man die Tatsache ausnutzt, dass die optimale Position der Wurzel eines Baumes nicht zu weit von der optimalen Position für die Wurzel eines etwas kleineren Baumes entfernt sein kann, so dass k in dem obigen Programm nicht alle Werte von i bis i+j durchlaufen muss.

Documents

G.Heyer Algorithmen und Datenstrukturen 2 1 Dynamische Programmierung Das Prinzip „Teile und Herrsche“ diente als Grundlage für die Entwicklung vieler