Greedy-Algorithmen

ca 15min-20min ---was sind greedy algorithmen? ---Wie ist der allgemeine Aufbau? ---Template zeigen und auf Bsp anwenden ---evtl Beispiele für extremfälle vorstellen-globales optimum, lokales optimum, fall in dem der greedy algorithmus versagt

Greedy-Algorithmen oder auch gierige Algorithmen zeichnen sich dadurch aus, dass sie schrittweise und ohne zurückzusetzen, eine Lösung aufbauen indem sie anhand lokaler Informationen den Folgezustand auswählen, welcher zum Zeitpunkt der Wahl das beste Ergebnis verspricht. Es werden dabei nicht mehr Teillösungen konstruiert als unbedingt nötig.

Greedy-Algorithmen sind oft schnell, lösen viele Probleme aber nicht optimal.

Aufbau

Im Allgemeinen besteht ein Greedy-Algorithmus aus folgenden Bestandteilen:

• eine sich verbrauchende Kandidatenliste,
• eine sich aufbauende Resultatenliste
• eine Funktion Loesung?, welche überprüft,ob die aktuelle Resultatenliste eine (nicht unbediingt optimale) Lösung des Problems darstellt
• eine Funktion OK?, welche überprüft, ob die Erweiterung einer Resultatenliste durch den nächsten Kandidaten zulässig ist.
• eine Auswahlfunktion NEXT, die aus der Kandidatenliste den jeweils besten "Happen" auswählt.
• eine Modifikationsfunktion MOD+, die die KAndidatenliste im positiven Fall, also wenn eine Erweiterung zulässig ist, modifizert.
• eine Modifikationsfunktion MOD-, die die KAndidatenliste im negativen Fall, also wenn eine Erweiterung nicht zulässig ist, modifizert.
• eine Funktion ZIEL, die den Wert einer Lösung ausgibt.

Greedy Template

• (define greedy
• (lambda (vorgabewert) ; zB Kapazität des Rucksacks
• (let
• ((Kandidatenliste '(....))
• (loesung? (lambda (ls) ...)
• (okey? (lambda (ls) ...)
• (naechster (lambda (ls)...)
• (mod+ (lambda (x ls)...)
• (mod- (lambda (x ls)...)
• (ziel (lambda (ls)...)))
• (letrec
• ((helfer
• (lambda (kandidaten resultat)
• (cond
• ((loesung? resultat)(ziel resultat)
• ((and (null? Kandidaten)(not(loesung? resultat)))
• (error 'greedy "es gibt keine Lösung"))
• (else
• let* ((neuer-Kandidat (nächster Kandidat))
• (neues resultat (cons neuer-kandidat resultat))
• (if(okay? neues-resultat)
• (helfer (mod+ neuer-kandidat kandidaten) neues-resultat)
• (helfer (mod- neuer-kandidat kandidaten) resultat))))))
• (helfer kandidatenliste '())))))

Globales und lokales Optimum

ca 20-25min ---Warum funktioniert der allgorithmus nur manchmal? ---Lokales Globales Optimum ---Matroide erklären

Ein Greedy-Algorithmus findet für ein Optimierungsproblem auf Unabhängigkeitssystemen genau dann die optimale Lösung, wenn die zulässigen Lösungen die unabhängigen Mengen eines Matroids sind. Sonst führt der Algorithmus lediglich zu einem lokalen Optimum.

Matroide

Unabhängigkeit

erklärung an graph, bipartitem matching, vektoren

heranführung an definition...

Beispiele

ca 15-20min ---Algorithmen aus vorangegangenen Vorträgen vorstellen und erklären warum das ergebnis ein globales Optimum ist ---evtl weitere übungen um in kleineren graphen zu erkennen ob greedy ein lokales oder globales optimum liefern wird