Teile und Herrsche; Divide et impera
Allgemeine Problem-unabhängige Formulierung des Prinzips:
D&C-Verfahren = Methode V zur Lösung des Problems P der Größe n:
1. (Direkte Lösung) Falls n < d, löse das Problem direkt, sonst 2. (Divide) Teile P in zwei oder mehr kleine Teile 3. (Conquer) Löse jedes Teilproblem Pi rekursiv mit der Methode V (auf gleiche Art) 4. (Merge) Setze die Teillösungen zusammen
Merkmale von D&C-Verfahren:
• Breite Anwendbarkeit: Suchen, Sortieren, Geometrie, DFT • Laufzeitanalyse über Lösungen von Rekursionsgleichungssystemen • Effizienz des Merge-Schritts (# und Größe der Teilprobleme) ist entscheidend
Produkt von Polynomen in Koeffizientendarstellung (1)
Seien
Polynome vom Grad , d.h. mit Koeffizienten; o.B.d.A.
Problem: Berechne c(x) = a(x) · b(x) in Koeffizientendarstellung mit möglichst
wenig Multiplikationen:
Naives Verfahren benötigt n2 viele Koeffizientenmultiplikationen.
Geht es besser?
Produkt von Polynomen in Koeffizientendarstellung (2)
Betrachte
al(x) und bl(x) bestehen aus den niedrigeren Koeffizienten von a(x) bzw. b(x) während ar(x) und br(x) die höheren Koeffizienten enthalten. Der Polynomgrad hat sich jeweils halbiert.
Direkte Umsetzung in rekursives Verfahren führt zu
Produkt von Polynomen in Koeffizientendarstellung (3)
Was ist ?
Es sind also jetzt nur noch 3 Teilprobleme halber Größe zu lösen: Die Bestimmung von A, B und C!
Produkt von Polynomen in Koeffizientendarstellung (4)
Die Abschätzung ergibt jetzt
Es geht noch besser mit anderem D&C-Verfahren: Ο(n log n)
Produkt von Polynomen in Koeffizientendarstellung (5)
public static int[] prod (int[] a, int[] b) {
int n = a.length, // Problemgroesse
nh = n/2; // halbe Problemgroesse
int[] r = new int [2*n]; // Ergebnisarray
if (n==1) { // Kleines Teilproblem:
r[0] = a[0] * b[0]; // Direkte Loesung
} else { // sonst:
int[] al = new int [nh], ar = new int [nh], // ********
bl = new int [nh], br = new int [nh], // * *
alr = new int [nh], blr = new int [nh]; // * *
for (int i=0; i
Greedy-Verfahren (1)
(Gierige Verfahren: Das teuerste (größte, beste) zuerst)
Typische Anwendungsgebiete: Optimierungsprobleme, etwa
• beste Bearbeitungsreihenfolge für Jobs in Computer • Kürzeste Wege in einem Graphen • minimale Zahl von Münzen in beim Geldwechseln
Bedingungen für die Anwendbarkeit:
• Die Problemlösung besteht aus einer optimalen Auswahl (Kombination, Reihenfolge, . . . ) der Elemente einer Kandidatmenge • Mit Hilfe einer speziellen Funktion kann geprüft werden, ob eine Kandidatmenge zulässig (feasible) ist. • Eine Bewertungsfunktion erlaubt eine Reihung von und damit Entscheidung zwischen noch nicht gewählten Kandidaten
Greedy-Verfahren (2)
Bsp: Das Münzwechsel-Problem:
Gegeben: Wert W des Wechselgeldes und eine Reihe von Münzwerten, etwa: 1, 2, 5, 10, 20, 50, 100, 200
Gesucht: Eine Folge von Münzwerten minimaler Länge mit Gesamtwert W
Frage: Wie findet man eine minimale Münzfolge — möglichst effizient?
W 0 sei gegeben wähle B = Wert der größten Münze solange W 0 { solange B W } zahle B aus W := W – B } }
Greedy-Verfahren (3)
Frage: Ist die gefundene Lösung beim Münzwechsel-Problem immer optimal?
Betrachte etwa Münzwerte 1, 20, 41 und W = 60:
Greedy-Lösung: 60 = 1 · 41 + 19 · 1 (20 Münzen) optimale Lösung: 60 = 3 · 20 (3 Münzen)
Antwort: Das hängt entscheidend vom Münzsystem ab!
Das Verhältnis V aus #Münzen nach Greedy zu optimaler #Münzen kann beliebig schlecht werden:
Münzwerte: 1,B, 2B + 1 W = 3 B
Greedy-Verfahren (4)
Allgemeine Formulierung des Greedy-Verfahrens:
solution = Ø; // wird zur Lösungsmenge erweitert while (!solution.complete() && !candidates.empty()){ x := candidates.best(); // x wird aus candidates entfernt if (!solution.add(x).feasible()) solution.remove(x); } if (solution.complete()) return solution else return solution.setEmpty();
Beachte: Einmal getroffene Entscheidung über Auswahl eines bestmöglichen Elementes wird bei Greedy-Verfahren nicht revidiert.
Dynamische Programmierung (1)
Name deutet nicht auf Art der Programmerstellung sondern auf Tabellierungstechnik hin.
Rekursiver Ansatz: Lösen eines Problems durch Lösen mehrerer kleinerer Teilprobleme, aus denen sich die Lösung für das Ausgangsproblem zusammensetzt.
Phänomen: Mehrfachberechnungen von Lösungen.
Methode: Speichern einmal berechneter Lösungen in einer Tabelle für spätere Zugriffe.
Beispiel: Fibonacci Zahlen
Dynamische Programmierung (2)
F6 F5 F4 F3 F2 F1 F0 F4 F3 F3 F2 F2 F1 F2 F1 F2 F1 F1 F0 F1 F0 F1 F0 F1 F0 Erster Ansatz:
F := proc (n::integer)
if n<0 then NULL
elif n=0 then 0
elif n=1 then 1
else F(n-1)+F(n-2) fi
end;
Nachteil: Laufzeit (# Knotenexp.) T(n) exponentiell in n:
Dynamische Programmierung (3)
Die # der rekursiven Aufrufe nimmt mit wachendem Argument exponentiell zu:
Problem: Es werden mehrfach die gleichen Teilprobleme gelöst
Vermeidung : Durch Tabellierung; Lege Tabelle für auftretende Funktionswerte an; jeder Wert wird nur einmal berechnet und später dann über die Tabelle zugegriffen
Bemerkung: Es gibt Programmiersprachen, bei denen sich die Tabellierung durch eine Option einschalten lässt, etwa Maple:
F:=proc (n::integer) option remember; if n<0 then NULL elif n=0 then 0 elif n=1 then 1 else F(n-1)+F(n-2) fi
end;
Dynamische Programmierung (4)
Bsp: Das Münzwechsel2-Problem:
Gegeben: Wert G des Wechselgeldes und eine Reihe von Münzwerten,
Werte: 1 2 5 10 20 50 100 200
Indices: 0 1 2 3 4 5 6 7
Gesucht: Die # der verschiedenen Möglichkeiten G in Münzen auszuzahlen
Frage: Wie findet man diese # — möglichst effizient?
Sei W(G, i) = # der verschiedenen Möglichkeiten, G auszuzahlen unter Nutzung von Münzen höchstens mit Index i
Dynamische Programmierung (5)
public class Geldwechsel {
static int betrag [] = {1, 2, 5, 10, 20, 50, 100, 200};
// Muenz-Nummern : 0 1 2 3 4 5 6 7
static long Tab [][];
public static long w (int G, int i){ // auf wieviele Arten kann
// man den Betrag G mit Muenzen bis zur Nummer <= i herausgeben ?
return (G < 0) ? 0 :
(i == 0) ? 1 :
(Tab [G][i] != 0) ? Tab [G][i] :
(Tab [G][i] = w (G,i-1) + w (G-betrag[i],i));
}
public static void main (String[] args){
int G = Integer.parseInt (args[0]);
Tab = new long [G+1][8];
System.out.println("Den Betrag von "+G+" kann man auf "+
w (G,7)+ " verschiedene Arten herausgeben.");
}
}
Dynamische Programmierung (6)
Es wurde eine 2-dim. Tabelle mit Indices 0 . . . 7 und 0 . . .G benutzt: Größe in O(G)
Geht es besser?
Ja, in O(1)
Vollständige Aufzählung (1)
Beispiel: Travelling Salesperson-Problem (TSP) Problem-Instanz:
Städte: 1 2 . . . n Entfernungen: mit
Zulässige Lösung: Permutation von (1, 2, . . . , n)
Zielfunktion:
Optimale Lösung: Zulässige Lösung mit minimalem Prinzip: Systematische Erzeugung aller potentiellen Kombinationen (Reihenfolgen), welche zu einer Lösung des Problems führen können. Dabei Auswahl einer (optimalen) Lösung.
Anwendbarkeit: Probleme, bei denen es viele Kandidaten für eine Lösung gibt, von denen eine ausgewählt werden soll, etwa bei Optimierungsproblemen.
Effizienz: Meist schlecht, nicht polynomiell.
Vollständige Aufzählung (2)
public static void main (String[] arg){ System.out.println ("TSP"); int N = 5; int[][] mat = { {0, 2, 2, 5, 4}, {3, 0, 5, 2, 2}, {6, 7, 0, 1, 6}, {3, 2, 7, 0, 3}, {5, 4, 3, 8, 0} }; // Matrix der Kosten Perm p = new Perm (N); // Kann Permutationen von 0 .. N-1 liefern int cost = Integer.MAX_VALUE; int [] c, best = { }; while ((c = p.getNext()) != null) { // Naechste Permutation int actcost = 0; for (int j=0; j "+actcost); if (actcost < cost){ cost = actcost; best = c; } } System.out.println("Die geringsten Kosten "+cost+ " verursacht "+arrStr(best)); } // main
Comments