Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Algorithmen und Datenstrukturen 1 Kapitel 3 Robert Giegerich Technische Fakultät Universität Bielefeld [email protected] Vorlesung, U. Bielefeld, Winter 2005/2006 Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Kapitel 3: Strategien der algorithmischen Problemlösung Vorbemerkungen Hier werden an einfachen Beispielen verschiedene Strategien erklärt, die zur Lösung eines wohldefinierten algorithmischen Problems benutzt werden können. In diesem Kapitel nehmen wir an, dass wir die Probleme der Modellierung (Kapitel 2) bereits erfolgreich hinter uns gelassen haben. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Unsere Beispiele sind einfach, um die Strategien in Reinform darzustellen. Für umfangreichere Aufgaben werden in der Regel Kombinationen und Mischformen der Strategien eingesetzt. Zusammen mit den Strategien betrachten wir auch den Rechenaufwand, den sie erfordern. Dies allerdings nur intuitiv – eine mathematische Behandlung wird später nachgeholt. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Zum Aufwand A[|...|] für Arithmetik: Die Annahme A[| + |] = A[|(x + y )|] ∀x, y ∈ N ist eine Vereinfachung. Sie gilt auf dem Computer für das Rechnen in einem beschränkten Zahlenbereich (32 Bit, 64 Bit) Sie gilt nicht für uns für den Computer beim Rechnen mit beliebig großen Zahlen (In Haskell: Typ Int versus Typ Integer.) Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Rechnen mit großen Zahlen hat wichtige Anwendungen, z.B. in der Verschlüsselungstechnik. Rechenaufwand hängt auch vom Zahlsystem ab. Dezimal: 05 + 12 = 17 (3 · A[| +Ziffer |] Binär: 00101 + 01100 = 10001 (9 · A[| +Ziffer |]) Unär: 11111 + 11 11111 11111 = 11 11111 11111 11111 (17 · A[|1|]) Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Leibniz hat als Erster die Binärzahlen beschrieben und bemerkt, dass durch diese Zahldarstellung das kleine 1 + 1 und 1 · 1 einfacher werden, die Zahlen und damit die Rechnungen länger werden. Er hielt die Binärzahlen für elegant, aber unpraktisch. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion 3.1 Ausrechnen von Formeln Dies ist der einfachste Fall. Die Modellierung hat schon ganze Arbeit geleistet und fertige Formeln für die Lösung aufgestellt: Beispiel: Tübinger Parkplatz Variante 1: r (p, m) = 4p + 2m Variante 2: p(n, r ) = m(n, r ) = Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 r −2n 2 n − r −2n 2 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Probleme, deren Lösungen sich allgemein als fertige Formeln beschreiben lassen, sind zugleich die einfachsten Aufgaben. Das ganze Problem wird “auf einen Schlag” gelöst. Meistens jedoch müssen Aufgaben erst in Teilaufgaben zergliedert, diese gelöst und deren Lösungen anschließend kombiniert werden. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion 3.2 Strukturelle Rekursion Allgemeines zur Rekursion: Rekursion heißt: Eine Methode M benutzt sich selbst zur Lösung von Problem X Terminierungsfall: Problem direkt lösbar Rekursiver Fall: M(X ) benutzt Lösung von M[X 0 ] Endlose Rekursion tritt auf, wenn beim Übergang M[X ] → M[X 0 ] → M[X 00 ] . . . nie der Terminierungsfall erreicht wird. Es gibt verschiedene Wege, Endlosrekursion auszuschließen. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Strukturelle Rekursion bedeutet Problemzerlegung durch direkte Zerlegung der Datenstruktur. Berechnen der Spieldauer eines Musikstückes (in Takten): playtime(P(d)) = d playtime(N(t, d)) = d playtime(m1 ∗ m2 ) = playtime(m1 ) + playtime(m2 ) playtime(m1 + m2 ) = max(playtime(m1 ), playtime(m2 )) Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Schema der Strukturellen Rekursion: Eine Gleichung pro Konstruktor des Datentyps Nicht-rekursive Konstruktoren ⇒ Terminierungsfall Rekursive Konstruktoren ⇒ rekursive Problemzerlegung Weiteres Beispiel: Funktion transponiere (s. Haskell-Vorlesung) Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Strukturelle Rekursion über Listen Kleinstes Element einer nichtleeren Liste: minimum(x : xs) = min x xs where min a[] = a min a(x : xs) = if a <= x then min a xs else min x xs Hier folgt die Hilfsfunktion min dem Schema der Strukturellen Rekursion. Die Funktion minimum selbst kann nicht durch Strukturelle Rekursion definiert werden, da sie für den Terminierungsfall gerade nicht definiert ist. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Aufwand: Entspricht der Größe der Datenstruktur – pro Konstruktor wird eine Gleichung angewandt. Das ist der Aufwand des Schemas. Hinzu kommt der Aufwand für die sonstige Operationen auf den rechten Seiten der Gleichungen. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Terminierung bei Struktureller Rekursion Terminierung ist gesichert, wenn die Datenstruktur eine endliche Formel ist. Endlos-Rekursion auf unendlichen Datenstrukturen. Beispiel: dauer (ad. libidum (P(1/2))). Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion 3.3 Wohlfundierte Rekursion (Teile-und-Herrsche) Allgemeiner als die Strukturelle ist die Wohlfundierte Rekursion. Die Zerlegung des Problems folgt nicht dem rekursiven Aufbau der Datenstruktur. Die Aufgabe wird auf beliebige Aufgaben (der gleichen Art) zurückgeführt, die in einem wohldefinierten Sinn “einfacher” sein müssen. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Eine (partielle) Ordnungsrelation ≤ auf einer Menge M erfüllt die Gesetze x ≤y x ≤y x ≤x und y ≤ z und y ≤ x impliziert x ≤ z impliziert x = y (Transitivität) (Antisymmetrie) (Reflexivität) Die Relation < ist definiert als x < y gdw x ≤ y und x 6= y und > als y > x gdw x < y Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Eine absteigende Kette aus M ist eine Folge von Elementen x1 > x2 > x3 > . . . Eine Ordnungsrelation auf M heißt wohlfundiert, wenn jede absteigende Kette aus M endlich ist (und damit ein kleinstes Element hat). Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Beispiele aus der Zahlenwelt (N, <) ist wohlfundiert (N, <) ist wohlfundiert für alle N ≤ N (Z, <) ist nicht wohlfundiert (Gegenbeispiel: 2 > 1 > 0 > −1 > −2 . . . ) (R+ 0 , <) ist nicht wohlfundiert (Gegenbeispiel: 1 > 1/2 > 1/4 > . . . ) (N × N, <) mit (a, b) ≤ (c, d) gdw a < c oder a = c und b ≤ d ist wohlfundiert. Man nennt dies lexikographische Erweiterung von (N, <). Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Schema der Wohlfundierten Rekursion zur Lösung von P, gegeben eine wohlfundierte Ordnung auf Problemen der Art P: Falls P einfach, löse P direkt. Andernfalls: Bilde Probleme P1 , . . . , Pk mit P > Pi Löse P1 , . . . , Pk (rekursiv) Kombiniere diese Lösungen zur Lösung von P Das Verfahren terminiert, weil alle so von P ausgehenden Ketten endlich sind und die Teilprobleme irgendwann “einfach” werden. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Die vier Bestandteile der Methode: “Was ist einfach?”, “Löse direkt ”, “Teile P auf!”, und “Kombiniere Teil-Lösungen!” muss man sich für jede Anwendung neu überlegen. Dabei ist die Relation < (“einfacher”) frei wählbar, nur wohlfundiert muss sie sein. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Beispiel: Quicksort Sortiere Liste von n Elementen aufsteigend. Wohlfundierte Ordnung auf Listen: `1 < `2 gdw length(`1 ) < length(`2 ) Da length(`) ∈ N, ist diese Ordnung wohlfundiert. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Beispiel: Quicksort Sortiere Liste von n Elementen aufsteigend. Wohlfundierte Ordnung auf Listen: `1 < `2 gdw length(`1 ) < length(`2 ) Da length(`) ∈ N, ist diese Ordnung wohlfundiert. Quicksort (`): Falls ` = [] oder ` = [a]: Lösung = `. Anderfalls: Wähle x aus `, so dass x nicht maximal ist. Bilde Listen `1 = [a|x ← `, a ≤ x] `2 = [a|x ← `, x < a] Berechne `ˆ1 = Quicksort(`1 ) `ˆ2 = Quicksort(`2 ) Lösung = `ˆ1 ++ `ˆ2 Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Achtung: x darf nicht maximales Element in ` sein, weil dann `1 < ` verletzt ist. Die Listen `1 und `2 sind keine Unterstrukturen der Liste `, daher liegt keine Strukturelle Rekursion vor. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Aufwand l l l1 l11 l2 l12 l21 [a1] l22 l2 [a2] l22 [a3] l22 ... 2 guter Fall Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 kritischer Fall Universität Bielefeld Strategien der algorithmischen Problemlösung guter Fall: Teile: Rekursionstiefe: Kombiniere: insgesamt kritischer Fall: Teile: Kombiniere: Rekursionstiefe: insgesamt: Ausrechnen von Formeln Strukturelle Rekursion auf jeder Ebene 2 · n Schritte log2 n Ebenen ≤ n/2 Schritte pro Ebene 3 · n · log2 n Schritte auf Ebene i 2 · (n − i) Schritte auf jeder Ebene 1 Schritt n Ebenen n−1 n X X 2(n − i) + 1 = n + 2 · i i=0 i=1 (n + 1) · n 2 n2 + 2n Schritte =n+2· Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Beispiel: Schnelle Multiplikation langer Zahlen Vorüberlegung: Wir betrachten zwei n-stellige Zahlen x = x 1 , . . . , x n , y = y 1 , . . . , yn . A[| + |] ist der Aufwand einer Ziffern-Addition. A[|x + y |] ≈ 2 · n · A[| + |] (Addition der Überträge nicht vergessen!) A[|x ∗ y |] ≈ n2 · A[| ∗ |] + 2n2 · A[| + |] Multiplikation ist also erheblich aufwendiger. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung 1 2 3 7 8 Ausrechnen von Formeln 4 4 8 3 5 0 6 9 1 8 ∗ 7 4 8 1 1 6 0 1 7 1 0 0 Strukturelle Rekursion 7 8 9 0 5 6 1 0 2 0 0 0 0 5 0 5 0 0 Schon weil jede Ziffer im Inneren des Diagramms Resultat einer Multiplikation ist, braucht man n2 elementare Multiplikationen. Besser geht es nicht — oder doch? Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Wir zerlegen die Zahlen in der Mitte x= x1 x0 x = x1 · 10n/2 + x0 y= y1 y0 y = y1 · 10n/2 + y0 x ·y = (x1 · 10n/2 + x0 ) · (y1 · 10n/2 + y0 ) = x1 · y1 · 10n + (x1 y0 + x0 y1 ) · 10n/2 + x0 y0 Jetzt haben wir 1 Mulitplikation mit Aufwand n2 durch vier 2 Multiplikationen mit Aufwand je n2 ersetzt. Nichts ist dabei eingespart. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion x1 y1 x1 y0 x0 y1 x0 y0 + xy Idee: Wir können den Wert x1 y0 + x0 y1 mit nur einer Multiplikation der Länge n/2 berechnen. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion (x0 − x1 )(y0 − y1 ) = x0 y0 − (x1 y0 + x0 y1 ) + x1 y1 Da x0 y0 und x1 y1 ohnehin berechnet werden, und Substraktionen nur Aufwand 3 · n/2 haben, erhalten wir “billig” (x1 y0 + x0 y1 ) = x1 y1 + x0 y0 + (x1 − x0 )(y0 − y1 ) Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion x1 y1 x0 y0 x1 y1 (x1 − x0 )(y0 − y1 ) x0 y0 + xy Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Die Teilaufgaben x1 y1 , x0 y0 , (x1 − x0 ) · (y0 − y1 ) der Länge n/2 werden nach der gleichen Methode (wohlfundiert rekursiv) berechnet. Wir schätzen ab A[n] ≈ 3 · A[n/2] < n2 . Ist dies eine signifikante Verbesserung? Damit werden wir uns in Kapitel 5 näher beschäftigen. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Das Problem des Handlungsreisenden Das Problem des Handlungsreisenden Ein Vertreter der Intelligent Design Corporation will 12 deutsche Elite-Universitäten besuchen. Die Standorte und ihre Entfernungen (Straßenkilometer) sind in Tabelle Dist angegeben, in Bild 1 sieht man ihre ungefähre Lage. Aber Vorsicht – Straßenkilometer sind keine Entfernungen in Luftlinie. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Das Problem des Handlungsreisenden Tabelle der Entfernungen AC Aachen Berlin Bielefeld Bremen Freiburg Hamburg Köln Leipzig München Münster Nürnberg Tübingen B 633 BI 257 390 HB 378 412 175 FB 505 819 685 730 HH 488 284 262 119 759 K 70 569 191 312 435 422 L 585 179 437 362 659 391 515 M 648 584 598 753 412 782 578 425 MS 211 466 74 171 572 271 150 438 688 N 475 437 434 580 391 609 405 278 167 506 TÜ 446 634 492 640 207 668 376 589 220 502 207 Tabelle Dist: Entfernungen in Straßenkilometern Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Das Problem des Handlungsreisenden Eine Rundtour HB 119 HH 284 B 257 AC MS 74 BI 150 K 70 179 L 278 685 N 167 TÜ 207 FB Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 220 M Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Das Problem des Handlungsreisenden Die Aufgabe Sein Ziel ist: Eine Rundtour mit beliebigem Ausgangspunkt und minimaler Gesamtstrecke. Jede Stadt darf nur einmal besucht werden (weil der Vertreter sich nach seinem Auftritt an einer Universität meistens in dieser Stadt nicht mehr blicken lassen darf). Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Das Problem des Handlungsreisenden Vorüberlegungen Vorüberlegung 1: Die Länge einer Rundtour bleibt gleich, wenn wir nur den Start/Zielort ändern. Es ist also nicht nötig, einen besten Startpunkt zu suchen. Wir können eine Tour ebensogut immer in Aachen oder immer in Bielefeld beginnen lassen. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Das Problem des Handlungsreisenden Vorüberlegung 2: Wieviele verschiedene Rundtouren gibt es allgemein für n Städte? Zahl der Permutationen p(n) = n ∗ (n − 1) ∗ . . . ∗ 1 = n! (1) Zahl derTouren t(n) = p(n − 1) (2) Für 12 Städte t(12) = 39916800 (3) Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Das Problem des Handlungsreisenden Strategie 1: Erschöpfende Suche Wir berechnen alle Permutationen der Orte (ohne den festen Startort Bielefeld) perm [ ] = [[ ]] (4) perm xs = {[x : ps|ps ∈ perm (remove x xs)]|x ∈ xs]} (5) n X gesamt[x1 , ..., xn ] = dist(xi−1 , xi ) + dist(xn , x1 ) (6) i=2 Aus allen Touren wählen wir die kürzeste aus. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Das Problem des Handlungsreisenden Strategie 2 : Opportunistische Suche (Greedy) Wir fahren von jedem Ort zum nächstgelegenen, der noch nicht besucht wurde. Sei X die Menge der Städte und z1 , z2 , ... unsere Route. Wir definieren einfach z1 = Bielefeld zi (7) = argminx {Dist(zi−1 , x)|x ∈ X \ {z1 , . . . , zi−1 }} (8) Hier bedeutet argminx dasjenige x, das den Ausdruck Dist(zi−1 , x) minimiert. Diese Lösung ist heuristisch. Sie gibt mit wenig Aufwand eine Antwort, aber vermutlich findet sie nicht die kürzeste Rundtour. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Das Problem des Handlungsreisenden Ergebnisse der Strategien Für unser Beispiel erhalten wir: Die opportunistische Strategie ab Bielefeld liefert die in der Karte eingetragene Rundtour. Sie ist 2690 km lang und nicht optimal. Von Bielefeld erst nach Bremen, das wäre besser ausgegangen! In Aachen anfangend, hätte das verfahren vermutlich eine bessere Tour gefunden. Die erschöpfende Suche soll in den Übungen implementiert werden. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Das Problem des Handlungsreisenden Abschätzung des Rechenaufwands Wir betrachten die Anzahl der berechnenten Routen, und die Berechnung einer Entfernungssumme für n Städte: Strategie 1 braucht etwa (n − 1)! ∗ n = n! Rechenschritte. Strategie 2 braucht etwa n2 Rechenschritte. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld Strategien der algorithmischen Problemlösung Ausrechnen von Formeln Strukturelle Rekursion Das Problem des Handlungsreisenden Erste Begegnung mit dem praktisch Unmöglichen Unser Problem ist unter dem Namen “Traveling Salesman Problem” (TSP) berühmt; es ist eines der meist untersuchten Probleme der Informatik. Man kennt keinen Algorithmus, die das Ergebnis mit einer (in n) polynomialen Anzahl von Rechenschritten bestimmt. Für Informatiker sind solche Probleme eine besondere Herausforderung. Robert Giegerich A&D 1 Vorlesung Winter 2005/2006 Universität Bielefeld
© Copyright 2024 ExpyDoc
