Microsoft PowerPoint Presentation: 06_Greedy_Verfahren

 Documents

 45 views
of 23
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Algorithmentheorie 6 – Greedy-Verfahren Tobias Lauer WS 06/07 Greedy-Verfahren 1. Allgemeine Vorbemerkungen 2. Einfache Beispiele ã Münzwechselproblem ã…
Share
Transcript
Algorithmentheorie 6 – Greedy-Verfahren Tobias Lauer WS 06/07 Greedy-Verfahren 1. Allgemeine Vorbemerkungen 2. Einfache Beispiele • Münzwechselproblem • Handlungsreisenden-Problem 3. Das Aktivitäten-Auswahlproblem WS 06/07 2 Greedy-Verfahren zur Lösung eines Optimierungsproblems Treffe in jedem Verfahrensschritt diejenige Entscheidung, die im Moment am besten ist! Möglichkeiten: 1. Wir erhalten stets die optimale Gesamtlösung. 2. Wir erhalten eine Lösung, die zwar nicht immer optimal ist, aber vom Optimum stets nur wenig abweicht. 3. Die berechnete Lösung kann beliebig schlecht werden. WS 06/07 3 Einfaches Beispiel: Münzwechselproblem EUR Bargeld-Werte: 500, 200, 100, 50, 20, 10, 5, 2, 1 Beobachtung Jeder ganze EUR Betrag kann durch Münzen und Banknoten mit diesen Werten bezahlt werden. Ziel Bezahlung eines Betrages n mit möglichst wenig Münzen bzw. Banknoten WS 06/07 4 Münzwechselproblem Greedy-Verfahren Wähle die maximale Zahl von Banknoten und Münzen mit jeweils größtmöglichem Wert, bis der gewünschte Betrag n erreicht ist. Beispiel: n = 487 500 200 100 50 20 10 5 2 1 WS 06/07 5 Allgemeines Münzwechselproblem Werte von Münzen und Banknoten: n1, n2, ..., nk n1 > n2 > ... > nk , und nk = 1. Greedy-Zahlungsverfahren: 1. w = n 2. for i = 1 to k do mi = # Münzen mit Wert ni = w / ni  w = w – m i∙ni Jeder Geldbetrag kann bezahlt werden! Liefert das Greedy-Verfahren immer eine optimale Lösung? WS 06/07 6 Land Absurdia Drei Münzen: n3 = 1, n2 > 1 beliebig, n1 = 2 n2 + 1 Beispiel: 41, 20, 1 Zu zahlender Betrag: n = 3 n2 (z.B. n = 60) Optimale Zahlungsweise: Greedy-Zahlungsverfahren: WS 06/07 7 Handlungsreisenden-Problem (TSP) Gegeben: n Orte und Kosten c(i, j), um von Ort i nach j zu reisen Gesucht: Eine billigste Rundreise, die alle Orte genau einmal besucht. Formal: Eine Permutation p von {1, 2, ..., n}, so dass c(p(1), p(2)) + ... + c(p(n-1), p(n)) + c(p(n), p(1)) minimal ist. WS 06/07 8 Handlungsreisenden-Problem (TSP) Greedy-Verfahren zur Lösung von TSP Beginne mit Ort 1 und gehe jeweils zum nächsten bisher noch nicht besuchten Ort. Wenn alle Orte besucht sind, kehre zum Ausgangsort 1 zurück. WS 06/07 9 Handlungsreisenden-Problem (TSP) Beispiel: c(i, i+1) = 1 für i = 1, ..., n - 1 c(n,1) = M für eine sehr große Zahl M c(i, j) = 2 sonst Vom Greedy Verfahren berechnete Tour: 1 2 3 n–2 n–1 n Optimale Tour: 1 2 3 n–2 n–1 n WS 06/07 10 Das Aktivitäten-Auswahl-Problem Gegeben: S = {a1,...,an} Menge von n Aktivitäten, die alle eine Ressource benötigen, z.B. einen Hörsaal. Aktivität ai: Beginn bi und Ende ei Aktivitäten ai und aj heißen kompatibel, falls [bi, ei)  [bj, ej) =  Gesucht: Eine größtmögliche Menge A  S paarweise kompatibler Aktivitäten. WS 06/07 11 1. Versuch Sortiere die Aktivitäten nach Anfangszeitpunkt, d.h. b1  b2  b3  ...  bn und nimm immer die nächste Aktivität hinzu, die zur bisherigen Menge kompatibel ist. Beispiel: 1 2 3 4 5 6 7 8 9 10 11 t WS 06/07 0 12 12 Das Aktivitäten-Auswahl-Problem 2 bi ei 1 3 1 0 6 4 1 1 4 5 2 13 1 6 3 5 1 3 8 7 1 5 7 8 5 9 1 6 10 9 1 8 8 11 10 8 12 1 8 11 12 14 1 8 1 8 11 WS 06/07 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1. Versuch Sortiere die Aktivitäten nach Anfangszeitpunkt, d.h. b1  b2  b3  ...  bn und nimm immer die nächste Aktivität hinzu, die zur bisherigen Menge kompatibel ist. Problem: Dieses Verfahren ist nicht optimal! Beispiel: WS 06/07 14 2. Versuch Greedy-Strategie zur Lösung des Aktivitäten-Auswahl-Problems: Sortiere die Aktivitäten nach aufsteigendem Endzeitpunkt: e1  e2  e3  ...  en Wähle immer die Aktivität mit frühestem Endzeitpunkt, die legal eingeplant werden kann! Insbesondere ist die erste gewählte Aktivität die mit frühestem Endzeitpunkt. WS 06/07 15 2. Versuch Sortiere die Aktivitäten nach Endzeitpunkt, d.h. e1  e2  e3  ...  en 1 2 3 4 5 6 7 8 9 10 11 t 0 12 WS 06/07 16 Das Aktivitäten-Auswahl-Problem 2 bi ei 1 1 4 3 1 3 5 4 1 0 6 5 5 7 1 4 3 8 6 1 4 5 9 7 6 10 1 4 8 8 11 1 4 8 12 9 2 13 1 4 8 10 12 14 1 4 8 11 1 4 8 1 4 8 11 WS 06/07 17 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Aktivitäten-Auswahl Algorithmus Greedy-Aktivitäten Input: n Aktivitätenintervalle [bi, ei), 1  i  n mit ei  ei+1 Output: Eine maximal große Menge von paarweise kompatiblen Aktivitäten 1 A1 = {a1} 2 last = 1 /* last ist Index der zuletzt hinzugefügten Aktivität */ 3 for i = 2 to n do 4 if bi < elast 5 then Ai = Ai-1 6 else /* bi  elast */ 7 Ai = Ai-1  {ai} 8 last = i 9 return An Laufzeit: O(n) WS 06/07 18 Optimalität des Greedy-Verfahrens Satz Das Greedy-Verfahren liefert eine optimale Lösung. Beweis Wir zeigen: Für alle 1  i  n gilt: Es gibt eine optimale Gesamtlösung A* mit A*  {a1 ,...., ai} = Ai i = 1: Wähle A*  {a1 ,...., an}, A* ist optimal, A* = {ai1 ,...., aik} A* = a i1 a i2 a i3 a ik a1 WS 06/07 19 Optimalität des Greedy-Verfahrens i –1 i: wähle A* {a1, ..., an}, A* ist optimal mit A* {a1,...,ai-1 } = Ai-1 betrachte R = A* \ Ai-1 Beobachtung: R ist eine optimale Lösung für die Menge der Aktivitäten in {ai, ..., an}, die zu den Aktivitäten in Ai-1 kompatibel sind. WS 06/07 20 Optimalität des Greedy-Verfahrens Fall 1: bi < elast elast Ai-1 = alast ai bi ai ist nicht kompatibel zu Ai-1 ai ist nicht enthalten in A* A* {a1,...,ai} = Ai-1 = Ai WS 06/07 21 Optimalität des Greedy-Verfahrens Fall 2: bi elast elast Ai-1= alast ai ai ist kompatibel zu Ai-1 bi Es gilt: R {ai, ..., an} R= c1 c2 c3 cl ai A*neu = Ai-1 (R \ {c1}) {ai} ist optimal A*neu {a1,...,ai} = Ai-1 {ai} = Ai WS 06/07 22 Greedy-Verfahren Greedy-Wahl-Eigenschaft: Wenn man optimale Teillösung hat und man trifft eine lokal optimale Wahl, dann gibt es eine global optimale Lösung, die diese Wahl enthält. Optimalität von Teillösungen: Eine Teillösung einer optimalen Lösung ist eine optimale Lösung des Teilproblems.  nach jeder lokal optimalen Wahl erhalten wir ein zur Ausgangssituation analoges Problem WS 06/07 23
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks