Greedy-Algorithmen SS11
Aus ProgrammingWiki
Inhaltsverzeichnis |
Idee
Bei vielen Optimierungsproblemen ist eine Verwendung der dynamischen Programmierung zur Bestimmung der besten Wahl übertrieben. Dann genügen einfachere, effizientere Greedy-Algorithmen. Greedy bedeutet gefräßig - eine gefräßige Strategie, die nach der Methode "Nimm immer den besten Happen, den du kriegen kannst." arbeitet.
Diese Methode ist recht leistungsfähig und deshalb arbeiten Greedy-Algorithmen für einen großen Bereich von Problemen gut.
Aber was ist nun der beste "Happen"? Greedy-Algorithmen treffen die Entscheidung rechnerisch auf der Basis lokaler Information, d.h. ohne Rückgriff auf Werte, die für frühere Situationen ermittelt wurden. Daraus resultiert, dass keine Tabelle, die alle Teilproblemlösungen bereithält, mitgeführt wird, wie das beim dynamischen Programmieren der Fall ist.
Außerdem wird eine einmal getroffene Entscheidung nicht korrigiert. Es gibt kein Zurücknehmen und Erproben von Alternativen, wie beim systematischen Probieren mit Backtracking.
Der Aufwand eines solchen Verfahrens ist sicher nicht exponentiell. Allerdings stellen wir die universelle Anwendbarkeit dieses "Superverfahrens" stark in Frage, da wir uns um effiziente Algorithmen bemühen.
Greedy-Algorithmen brauchen für die Auswahl des besten "Happens" eine vorsortierte Kandidatenliste. Neu aufzunehmende Elemente werden immer gleich an der richtigen Stelle eingefügt, so dass die Sortierung erhalten bleibt.
Der zugehörige Datentyp ist eine Prioritätswarteschlange (priority queue), die wir bereits bei Verzweigen und Beschränken kennengelernt haben. Für Greedy-Algorithmen, insbesondere für den Dijkstra- und den Prim-Algorithmus, eignen sich besonders gut Heaps.
Bruchteil-Rucksackproblem
Im Gegensatz zu dem 0/1 Rucksackproblem gibt das Bruchteil-Rucksackproblem uns die Möglichkeit, Gegenstände auch teilweise, also Bruchstücke einpacken zu dürfen.
Bezüglich der Gegenstandswerte gehen wir von einer homogenen Verteilung aus. Dies bedeutet, dass ein Gegenstand, der beispielsweise zu 80 % eingepackt wird, einen Wertzuwachs von 80 % seines vollen Wertes erbringt.
Nehmen wir also an, wir haben einen Rucksack mit einer gewissen Kapazität und einer bestimmten Anzahl an Gegenständen, diese wiederum einen Wert
und ein Gewicht
besitzen.
Nun sortieren wir diese Gegenstände absteigend nach ihrem Wert.
Der Gegenstand mit dem größten spezifischen Wert erhält die Nummer , danach folgen
,
,
,
in dieser Reihenfolge.
Nach der Greedy-Strategie stecken wir nun die ersten Gegenstände in den Rucksack.
ergibt sich, wenn Gegenstand
der Erste ist, der nicht vollständig in den Rucksack passt. Die eventuell vorhandene Restkapazität kann aber durch einen Teil
mit
des Gegenstandsgewichtes
ausgefüllt werden.
Der Gesamtwert des so gefüllten Rucksacks beträgt
Kann man wirklich sicher sein, dass auf diese Weise der größtmögliche Gesamtwert erreicht wird? Könnte es nicht besser sein, von einem der ursprünglich vollständig eingepackten Gegenstände, sagen wir (mit
) nur einen Teil, sagen wir
(mit
) zu nehmen. Dann hat man so viel Platz, dass ein Teil
eines Gegenstandes
(
) mit kleinerem spezifischem Wert als der von
eingepackt werden kann. Dies ergibt den folgenden Gesamtwert.
Da das Gewicht des -ten Teiles von
gerade mit dem Restgewicht
übereinstimmt, d.h.
, gilt
.
Dann kann man für den Gesamtwert
schreiben. Eine einfache Umformung ergibt
Da ergibt sich wegen
kein Wertzuwachs. Ganz im Gegenteil, es gilt sogar .
Wir können also sicher sein, dass die Greedy-Methode das Bruchteil-Rucksackproblem effizient löst.
Allerdings versagt diese Methode beim 0/1 Rucksackproblem. Deshalb fragen wir uns, wie gut die Anwendbarkeit von Greedy-Algorithmen aussieht. Die Antwort lautet: Ein Greedy-Algorithmus führt immer zum optimalen Ergebnis, wenn die zugrunde liegende algebraische Struktur ein Matroid ist.
Die folgende Prozedur bruchteilrucksack nimmt als Eingabe die Kapazität des verwendeten Rucksacks und liefert aus der vorgegebenen Kandidatenliste die beste Einpackungsmöglichkeit. Ausgegeben werden der Bruchteil des letzten eingepackten Elements, das Gesamtgewicht und der Gesamtwert aller eingepackten Elemente.
Aufbau von Greedy-Algorithmen
Im Allgemeinen bestehen Greedy-Algorithmen aus den folgenden Bestandteilen:
- eine (sich verbrauchende) Kandidatenliste
- eine (sich aufbauende) Resultatliste
- eine Funktion loesung?, die überprüft, ob die aktuelle Resultatliste eine (nicht unbedingt optimale) Lösung des Problems darstellt
- eine Funktion okay?, die überprüft, ob die Erweiterung einer Resultatliste durch den nächsten Kandidaten zulässig ist
- eine Auswahlfunktion naechster, die aus der Kandidatenliste den jeweils besten "Happen" auswählt
- eine Modifikationsfunktion modify+, die die Kandidatenliste im positiven Fall verändert, demzufolge wenn die Erweiterung zu einer zulässigen Liste führt
- eine Modifikationsfunktion modify-, die die Kandidatenliste im negativen Fall verändert, also wenn die Erweiterung zu einer unzulässigen Liste führt
- eine Funktion ziel, die den Wert einer Lösung angibt
In SCHEME können wir eine Prozedur angeben, die eine Struktur aufweist, die für alle Greedy-Algorithmen unverändert übernommen werden kann. An den durch Punkte gekennzeichneten Stellen werden die Werte eingefügt, die dann den jeweils entsprechenden Algorithmus spezifizieren. Eine solche Prozedur wird demnach wie eine Schablone, ein sog. Template, benutzt.
(define greedy
(lambda (vorgabewert) ; z.B.: Kapazitaet der Rucksacks
(let
((kandidatenliste '(......))
(loesung? (lambda (ls) ... ))
(okay? (lambda (ls) ... ))
(naechster (lambda (ls) ... ))
(modify+ (lambda (x ls) ... ))
(modify- (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 Loesung."))
(else
(let* ((neuer-kandidat (naechster kandidaten))
(neues-resultat (cons neuer-kandidat resultat)))
(if (okay? neues-resultat)
(helfer (modify+ neuer-kandidat kandidaten) neues-resultat)
(helfer (modify- neuer-kandidat kandidaten) resultat))))))))
(helfer kandidatenliste '())))))
Beispiel Geldwechsel
Die Verwendung dieser Greedy-Schablone illustrieren wir am folgenden Beispiel der Prozedur geldwechsel.
Einem Kunden wird Wechselgeld herausgegeben, wobei möglichst wenige Münzen verwendet werden sollen.
- Die Kandidatenliste besteht aus allen verfügbaren Euro-Münzen (1-, 2-, 5-, 10-, 20-, 50-Cent und 1- und 2-Euro-Münzen), die wir seit 01.01.2002 zusammen mit den Euro-Scheinen in Europa als Zahlungsmittel benutzen. Die Münzen werden mit absteigendem Cent-Wert vorsortiert.
- loesung? gibt #t zurück, wenn die Summe der verwendeten Münzen genau den auszuzahlenden Betrag ergibt.
- okay? gibt an, wenn eine Menge ausgewählter Münzen okay ist, wenn deren Summe höchstens dem zu zahlenden Betrag entspricht.
- Ist dies nicht der Fall, wird dieser Wert aus der Liste der (aussichtsreichen) Kandidaten entfernt. Dies erledigt die Prozedur modify-.
- modify+ lässt die Kandidatenliste unverändert. Dadurch wird erreicht, dass sich potenziell unendlich viele Münzen jeden Wertes in der Kandidatenliste befinden, so dass jeder beliebige Restbetrag immer ausgezahlt werden kann.
- Die Prozedur naechster wählt unter den verbleibenden Münzen die jenige mit dem jeweils höchsten Wert aus, ganz gleich, ob damit der zu zahlende Betrag überschritten wird oder nicht. (Dafür gibt es ja okay?) Es wird immer das erste Element zurückgegeben, da zu jedem Zeitpunkt die Kandidatenliste absteigend sortiert ist.
- Die Funktion ziel gibt die Liste der verwendeten Münzen zurück.
Die Prozedur wird benutzt um 12,93 Euro (1293 Euro-Cent) herauszugeben.
Verschiedene Greedy-Algorithmen
Allgemeines zur Graphentheorie
Ein Graph ist eine mathematische Struktur, die aus Knoten und Kanten besteht. Diese Knoten können durch Kanten verbunden werden. Jede Kante verbindet in der Regel zwei Knoten miteinander. Die Kanten können, je nach Problemstellung, gerichtet oder ungerichtet, bewertet (gewichtet) oder unbewertet (ungewichtet) sein.
Eigenschaften des Graphen:
- gerichtet - wenn die Kanten einseitig gerichtete Pfeile sind
- ungerichtet - wenn die Kanten in beide Richtungen gelten
- bewertet - ist wenn jeder Kante ein Wert zugeordnet wird
- unbewertet - ist wenn keiner Kante ein Wert zugeordnet wird
- zusammenhängend - ist, wenn von jedem Knoten zu jedem anderen Knoten ein Weg vorhanden ist
- Ein Graph ohne Zyklen entspricht einem Baum.
- Ein aufspannender Baum ist ein Teil des Graphen, der alle Knoten enthält, aber nur so viele Kanten besitzt, dass er einen Baum bildet.
Dijkstra-Algorithmus
Edsger W. Dijkstra auf Wikipedia
Kürzeste Wege in Graphen
Die Suche nach der kürzesten Rundreise, die n gegebene Städte genau einmal besucht, gehört zu den schwierigsten Problemen, für die bisher nur Lösungsverfahren mit exponentieller Rechenzeit bekannt sind (siehe: Verzweigen und beschränken: Das Rundreiseproblem).
Das folgende Problem klingt noch schwieriger. Gesucht ist der kürzeste Weg von Stadt A zu Stadt B, wobei für die n betrachteten Städte eine Entfernungsmatrix gegeben ist. Man muss alle Zwischenstädtefolgen (Wege) betrachten, auch solche, die nicht alle Städte enthalten.
Edsger W. Dijkstra fand 1959 einen Algorithmus zur Lösung des Kürzeste-Wege-Problems dessen Rechenzeit in liegt. Ein nach Robert Floyd und Stephen Warshall benanntes Verfahren löst eine etwas weiter gehende Fragestellung in
. Dabei werden die kürzesten Wege für alle Städtepaare bestimmt.
Das Problem ist, mathematisch gesehen, eine Sache der Graphentheorie.
Unter einem endlichen Graph G versteht man ein Paar (V, E), wobei V eine endliche Knotenmenge (Knoten = vertex) und E eine endliche Menge von Kanten (edges) bezeichnet. Eine Kante verbindet genau zwei Knoten. Es ist nicht verlangt, dass alle Knotenpaare durch je eine Kante verbunden sind. Es kann auch Mehrfachkanten geben.
Zur Speicherung von Graphen verwendet man Matrizen. Eine gängige Form sind sog. Adjazenmatrizen, die für jedes Knotenpaar vermerken, ob die durch die aktuelle Zeile bzw. Spalte bestimmten Knoten durch eine Kante verbunden sind.
Handelt es sich um einen gewichteten Graph, dessen Kanten z.B. mit je einer Zahl für eine bestimmte Länge, Masse oder einen Euro-Betrag markiert sind, werden diese Gewichte in der Adjazenmatrix angegeben. Nicht vorhandene Kanten werden durch einen vereinbarten Wert, meist 0, x oder eine sehr große Zahl, beschrieben. Die folgende Matrix zu dem Graphen aus Bild 4.1 ist ein solches Beispiel.
Der Algorithmus lässt sich durch die folgenden Schritte beschreiben:
- 1. Der Startknoten wird als aktueller Knoten mit der Distanz 0 zum Vorgängerknoten gespeichert. Auf diese Weise entsteht ein Tripel bestehend aus aktuellem Knoten, Distanz zum Startknoten und Vorgängerknoten. (Der Startknoten ist zugleich aktueller Knoten und Vorgängerknoten)
- 2. Speichere alle unbesuchten Nachbarknoten, die Distanz zum Startknoten und den Vorgängerknoten.
- 3. Wähle das Tripel mit der minimalsten Distanz zum Startknoten und speicher dieses als aktuellen Knoten.
- 4. Wiederhole Schritt 2 und nimm alle bereits gespeicherten Tripel hinzu. Falls ein Knoten über einen anderen Vorgängerknoten in kürzerer Distanz erreicht wird, streiche den schlechteren Weg (das Tripel mit der höheren Distanz zum Startknoten).
- 5. Wiederhole Schritt 3.
- 6. Wiederhole dieses Verfahren, bis der Zielknoten erreicht wird.
Die Prioritätswarteschlange stellt sicher, dass der Aufwand gleich bleibt, auch wenn der Algorithmus merkt, dass ein neuer Weg besser ist als der aktuell verwendete.
Im folgenden Beispiel wird dieser Vorgang illustriert:
Gegeben ist der Graph in Bild 4.1 mit den 7 Knoten A, B, C, D, E, F und G. Gesucht ist die kürzeste Strecke von A nach D.
Zur Bestimmung eines kürzesten Weges von s nach z, mit s, z Element V, für einen gegebenen gewichteten Graphen G = (V, E) lässt sich der Dijkstra-Algorithmus folgendermaßen allgemein beschreiben:
S:={s};
Distanz(s):=0;
for all v
V\{s} do {
Distanz(v)=Kante(s,v);
Vorgaenger(v)=s;
}
while z
S do {
Finde v'V\S mit Distanz(v')=min{Distanz(v) | vV\S};
S:=S
{v'};
for all vV\S do {
if Distanz(v')+Kante(v',v) < Distanz(v)
then {
Distanz(v):=Distanz(v')+Kante(v' ,v);
Vorgaenger(v):=v'
}
}
}
Im Programm bedeutet Kante (x, y) die Länge der Kante von Knoten x zu Knoten y. Falls es keine solche Kante gibt, gilt ihre Länge als unendlich.
Bei geschickter Implementation des Algorithmus mit einem binären oder binomialen Heap wird nur eine Rechenzeit in benötigt, wobei
bzw.
die Zahl der Knoten bzw. Kanten bezeichnen. Dies ist noch besser als der eingangs in Aussicht gestellte quadratische Aufwand.
Kruskal-Algorithmus
Minimaler Spannbaum
Unter Verwendung der in Abschnitt 4.1 eingeführten Grundbegriffe aus der Graphentheorie können wir einen zusammenhängenden, zyklenfreien, gewichteten Teilgraphen bilden, dessen Gesamtgewicht minimal ist. Die Knotenmenge dieses Teilgraphen stimmt mit der des vollständigen Graphen aus diesem Modell überein. Im Allgemeinen sind aber nicht alle Kanten vorhanden.
In der Graphentheorie nennt man einen ungerichteten, zusammenhängenden und zyklenfreien Graph mit mindestens einem Knoten einen Baum.
Ist ein Teilgraph eines zusammenhängenden Graphen G ein Baum, so nennt man diesen ein Gerüst von G.
Da er alle Knoten als Baum aufspannt, spricht man auch von einem aufspannenden Baum, also ein Spannbaum.
Für die Suche des minimalen Spannbaums gibt es einen Greedy-Algorithmus von Joseph Kruskal. Der US-amerikanische Mathematiker beschrieb den Algorithmus 1956 wie folgt:
Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von G (dem Graphen) die kürzeste Kante, die mit den schon gewählten Kanten keinen Kreis bildet.
Die kürzeste Kante bezeichnet dabei jeweils die Kante mit dem kleinsten Kantengewicht. Nach Abschluss des Algorithmus bilden die ausgewählten Kanten einen minimalen Spannbaum des Graphen.
Die Grundidee des Kruskal-Algorithmus beschreibt man folgendermaßen:
- Ordne die Kanten des Graphen nach ihren Gewichten in aufsteigender Folge
- Beginne mit der ersten Kante
- Nimm die nächste Kante hinzu, egal ob sie an die erste anschließt oder nicht. Falls es zwei Kanten mit gleichem Gewicht gibt, nimm beide.
- Wiederhole dieses Verfahren für alle Kanten, solange kein Kreis mit der nächsten Kante entsteht. Ist das der Fall, lass die Kante weg und mach mit der folgenden weiter.
Da der Kruskal-Algorithmus eine Prioritätswarteschlange, die aus allen Kanten in aufsteigender Folge besteht, besitzt, weiß er jederzeit, ob sich durch Hinzunehmen einer Kante ein Kreis bildet oder nicht. Dadurch wird die Kreisbildung verhindert.
Der Algorithmus arbeitet im Average case mit , wobei
für die Anzahl der Kanten und
für die Knoten des betrachteten Graphen stehen. Hat der vorgegebene Graph nur wenige Kanten, etwa bei
, so gilt im Best case
. Bei höherer Dichte, d.h.
, ergibt sich im Worst case
.
Prim-Algorithmus
Der Prim-Algorithmus, welcher von dem tschechischen Mathematiker Vojtěch Jarník (*1897 †1970) 1930 entwickelt wurde und später von Robert C. Prim im Jahr 1957 und von Edsger W. Dijkstra im Jahr 1959 wieder entdeckt wurde, stellt eine Alternative für die Suche eines minimalen Spannbaums dar.
Durch eine kleine Modifikation an drei Stellen des Dijkstra-Algorithmus erhällt man ihn:
S:={s};
Distanz(s):=0;
for all vV\{s} do {
Distanz(v)=Kante(s,v);
Vorgaenger(v)=s;
}
while S!=V do {
Finde v'V\S mit Distanz(v')=min{Distanz(v) | vV\S};
S:=S{v'};
for all vV\S do {
if Kante(v',v) < Distanz(v)
then {
Distanz(v):=Kante(v' ,v);
Vorgaenger(v):=v'
}
}
}
Der Prim-Algorithmus arbeitet nach folgendem Prinzip:
- Ein beliebiger Knoten wird gewählt und als Startgraph
festgelegt.
- Unter den abgehenden Kanten wird die mit dem kleinsten Gewicht gewählt und mit dem anhängenden Knoten zum Startgraphen hinzugefügt
- Solange
- Wenn die entsprechende Kante gefunden wurde und der entsprechende Knoten noch nicht in
- Wiederhole dieses Verfahren für alle Kanten, solange kein Kreis im Graph entsteht.
Der Algorithmus arbeitet mit einem Aufwand von .
Übungen
Literatur und andere Quellen
- Th. H. Cormen, Ch. E. Leiserson, R. Rivest, C. Stein: Algorithmen - Eine Einführung, 2.Auflage, Oldenbourg Wissenschaftsverlag GmbH 2007, ISBN 978-3-486-58262-8
- Volker Heun: Grundlegende Algorithmen - Einführung in den Entwurf und die Analyse effizienter Algorithmen, 2. Auflage, Vieweg+Teubner Verlag 2003, ISBN 978-3528131401
- Ch. Wagenknecht: Algorithmen und Komplexität, 1.Auflage, Carl Hanser Verlag 2003, ISBN 3-446-22314-2
