Musterlösung Blatt 5: H-17: Der Algorithmus erzeugt die folgende Tabelle der Werte m[i,j] und s[i,j]: 2010 2 1655 1950 4 2 405 2430 1770 2 2 2 330 330 930 1860 2 2 4 4 150 360 180 3000 1500 0 0 0 0 0 0 Daraus erhält man die optimale Klammerung (M1 M2)((M3 M4)(M5 M6)) die 2010 Multiplikationen benötigt. H18: Um das Problem mit dynamischer Programmierung zu lösen, betrachtet man ein allgemeineres Problem. Definition: Z = ist monotone Teilfolge von X= mit Schranke b, falls Z eine monotone Teilfolge von X ist und außerdem zi <= b für alle i<=k ist. Das allgemeinere Problem ist: finde eine längste monotone Teilfolge (lmT) von X mit Schranke b. Das ursprüngliche Problem ergibt sich für b > max X. Das allgemeinere Problem hat die folgenden kleineren Teilprobleme, die rekursiv zu lösen sind: Finde eine lmT von Xi = mit Schranke xj. Eine optimale Lösung Z eines solchen Teilproblems sieht aus wie folgt: - Entweder ist xi>xj, dann ist Z lmT von X(i-1) mit Schranke xj, - oder es ist xi<=xj, dann ist - entweder zk = xi, und Z(k-1) ist lmT von X(i-1) mit Schranke xi, - oder zk != xi, und Z ist lmT von X(i-1) mit Schranke xj. Also erhält man folgende Rekursionsgleichung für die Länge l[i,j] einer lmT von Xi mit Schranke xj: l[i-1,j] falls xi>xj l[i,j] = { max(l[i-1,i]+1,l[i-1,j]) falls xi<=xj mit den Anfangswerten l[0,j] = 0 für alle j. Diese Werte berechnen wir für i von 1 bis n in einer Tabelle, das Ergebnis ist der größte Eintrag in der obersten Zeile, also max(l[n,j], j=1..n). Zum Auffinden einer lmT merkt man sich mit jedem Tabelleneintrag ein bit b[i,j], dass auf 1 gesetzt wird genau dann wenn l[i,j] als 1+l[i-1,i] gewählt wurde, sonst auf 0. Das folgende Programm gibt dann die lmT von X aus: Suche j mit l[n,j] maximal, rufe print_lmT(n,j) auf. print_lmT(i,j) if i=0 then return if b[i,j] = 0 then print_lmT(i-1,j) else print_lmT(i-1,i) print(xi) Zeitaufwand ist O(n^2) für das Füllen der Tabelle plus O(n) für die Maximumsuche plus O(n) für die Ausgabe, also insgesamt O(n^2). H19: Der Algorithmus benutzt die folgende greedy-Strategie: Fahre stets zur am weitesten entfernten Tankstelle, die noch erreicht werden kann. Formal etwa so: Tankstellen seien T1,...,Tm Für i <= m+1 sei di die Entfernung von Ti zu T(i+1) (wobei T0 der Start und T(m+1) das Ziel sei). E := d1+...+d(m+1) i := 0 while E>n do D := 0 while D+d(i+1) <= n do i := i+1 D := D+d if D=0 then print "Weiterfahrt nicht möglich" else print "Fahre Tankstelle" Ti "an" print "Fahre direkt zum Ziel" Beweis, dass der Algorithmus eine optimale Lösung liefert: Sei allgemein d[i,j] die Entfernung von Tankstelle Ti zu Tj. Sei i maximal mit d[0,i] <= n, also die vom greedy-Algorithmus getroffene erste Wahl. Sei eine beliebige optimale Lösung gegeben, und seien Ti1 und Ti2 die ersten bei dieser angefahrenen Tankstellen. Wenn nun in dieser optimalen Lösung Ti1 durch Ti ersetzt wird, erhalten wir eine korrekte Lösung, da d[i1,i2] >= d[i,i2] ist. Diese modifizierte Lösung ist immer noch optimal, da die Zahl der Tankstopps erhalten bleibt. Also ist die erste Auswahl korrekt. Offensichtlich wird das Problem durch die erste Auswahl von Ti auf das gleichartige Teilproblem reduziert, mit möglichst wenigen Tankstopps von Ti zum Ziel zu gelangen, und eine optimale Lösung des Gesamtproblems enthält eine optimale Lösung dieses Teilproblems. Daher kann das verbleibende Teilproblem mit der gleichen Strategie gelöst werden, was der Algorithmus auch tut. H20: Der Code, den der Algorithmus berechnet, sieht so aus: a: 1111111 b: 1111110 c: 111110 d: 11110 e: 1110 f: 110 g: 10 h: 0 Die Verallgemeinerung lautet: für das Alfabet An = {a1,...,an}, bei dem der Buchstabe ai mit Häufigkeit Fi auftritt, wird folgender Code konstruiert: a1 : 1^(n-1) ai : 1^(n-i)0 für i=2...n Zum Beweis, dass dies so ist, benötigt man die folgende Tatsache: Sei S(n) := F1 + F2 + ... + Fn. Dann gilt: S(n-1) < F(n+1) < S(n) Dies wird durch Induktion nach n bewiesen: Es ist S(2) = 2, F4 = 3 und S(3) = 4, also ist S(2) < F4 < S(3), dies gibt den Induktionsanfang. Gelte also die Annahme S(n-1) < F(n+1)