Greedyalgorithmen und -heuristiken
Inhaltsverzeichnis |
09.01.16 - hab mal versucht nen roten faden für die aufteilung zu finden - es muss alles noch bearbeitet werden - müssen die nächsten tage mal wegen der Vortragsaufteilung/Gliederung sprechen - evtl habt ihr ja noch ideen was noch rein kann/muss - ich würde gern den abschnitt matroide/unabhängigkeitssysteme machen
Greedy-Heuristiken
Globales und lokales Optimum
ca 20-25min ---Warum funktioniert der allgorithmus nur manchmal? ---Lokales Globales Optimum ---Matroide erklären
Ein Greedy-Algorithmus findet EIN(es kann immernoch eine gleichwertige lösung geben) Optimum, genau dann wenn die Lösungen unabhängige Mengen eines Matroids sind. Sonst führt der Algorithmus lediglich zu einem lokalen Optimum.
Vektoraufgabe/lineare Algebra: Wähle ein Menge unabhängiger Vecktoren. Graphentheorie-Aufgavbe: Bilde eine größtmögliche Menge an Kanten ohne dabei Kreise zu bilden. Bilde die kleinstmögliche Menge an Straßen um alle Städte zu verbinden. Es dürfen dabei keine Kreise entstehen! Matching-Aufgabe:Bilde so viele Paarungen wie möglich. Equation-Aufgabe: a=z^3,b=x+y,c=x-y,d=xy,e=x^2y^2,f=1
folgerungen lineare unabhängigkeit- Graphen: eine Menge an Kanten ist unabhängig wenn sie keine Kreise bilden Matching: eine Menge ist unabhängig wenn sie gleichzeitig gematcht werden kann equations: eine Menge an Ausdrücken ist unabhängig wenn
Matroide
Unabhängigkeit
- erklärung an graph, bipartitem matching, vektoren
- heranführung an definition...
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 kruskal, lokales optimum rucksack0/1, fall in dem der greedy algorithmus versagt gerichteter graph
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. Die Basis eines Greedy-Algorithmus ist eine bereits (absteigend) vorsortierte Liste. Wird diese erweitert, werden die entsprechenden Elemente direkt an die richtige Stelle einsortiert.
- Vorteil: sehr schnell, gute (Näherungs-)Lösung.
- Nachteil:
- keine Berücksichtigung früherer Lösungen; keine Revision einmal getroffener Entscheidungen.
- Endlösung möglicherweise nicht optimale Lösung. 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 Resultatliste
- Funktionen
- loesung?, die kontrolliert, ob die aktuelle Resultatliste eine Lösung des Problems darstellt
- okay?, die kontrolliert, ob die Erweiterung einer Resultatliste durch den nächsten Kandidaten zulässig ist
- ziel, die den Wert einer Lösung angibt
- Auswahlfunktion
- nächster, die aus der Kandidatenliste den jeweils besten "Happen" auswählt
- Modifikationsfunktionen
- modify+, die die Kandidatenliste im positiven Fall, also wenn die Erweiterung zu einer zulässigen Liste führt, modifiziert
- modify-, die die Kandidatenliste im negativen Fall, also wenn die Erweiterung nicht zu einer zulässigen Liste führen würde, modifiziert
Greedy Template
Bestandteile des Algorithmus:
- eine (sich verbrauchende) Kandidatenliste,
- eine (sich aufbauende) Resultatliste,
- Funktionen:
- loesung?, die überprüft, ob die aktuelle Resultatliste eine Lösung des Problems darstellt,
- okay?, die überprüft, ob die Erweiterung einer Resultatliste durch den nächsten Kandidaten zulässig ist,
- naechster, die den besten Kandidaten aus der Liste auswählt,
- modify+, die die Kandidatenliste im positiven Fall modifiziert,
- modify-, die die Kandidatenliste im negativen Fall modifiziert,
- ziel, die die Lösung angibt.
Anwendungsbeispiel 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.
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
Kruskal-Algorithmus
Der Mathematiker Joseph Kruskal entwickelte einen Algorithmus zur Suche nach einem minimalen Spannbaum. Durch seine Effizienz arbeitet der Algorithmus in \mathcal{O}\left( m \log n\right), wobei m die Anzahl der Kanten und n die Anzahl der Knoten darstellen. Sollte m \leq n gelten, so arbeitet der Algorithmus in \mathcal{O}\left( n \log n\right), für sehr wenige m, d. h. m \leq \frac{n}{2}\left( n-1\right), in \mathcal{O}\left( n^2 \log n\right).
Der Algorithmus lässt sich wie folgt beschreiben:
- Alle Kanten werden in aufsteigender Länge in einer Liste sortiert.
- Die erste Kante bildet mit ihren anschließenden Knoten den Startgraphen. Existeren mehrere Kanten gleicher Länge, werden alle verwendet.
- Solange noch nicht alle Knoten verbunden sind, wird dieses Verfahren wiederholt.
- Würde durch die Hinzunahme einer Kante ein Kreis entstehen, wird diese Kante aus der Liste gestrichen und mit der nächsten fortgefahren.
Am Beispiel wird der Algorithmus deutlich. Als Basis dient wieder der bereits weiter oben verwendete Graph.
Prim-Algorithmus
Ein weiterer Algorithmus zur Ermittlung des minimalen Spannbaums wurde 1930 vom Mathematiker Vojtěch Jarník entwickelt, 1957 von Robert Prim und 1959 von Edsger Dijkstra wiederentdeckt. Auf Basis des Dijkstra-Algorithmus arbeitet dieser Algorithmus in \mathcal{O}\left( n^2\right).
Die Funktionsweise des Algorithmus lässt sich wie folgt beschreiben:
- Ein beliebiger Knoten eines Graphen wird gewählt.
- Nun wird die angrenzende Kante mit dem geringsten Wert gewählt und der angrenzende Knoten verbunden.
- Dieses Verfahren wird so lange wiederholt, bis alle Knoten verbunden sind. Es werden nun aber alle Kanten an allen verbundenen Knoten betrachtet.
- Würde durch die Hinzunahme einer Kante ein Kreis entstehen, wird diese Kante aus der Liste gestrichen und mit der nächsten fortgefahren.
Die Erweiterung der Dijkstra-Algorithmus ergibt sich dann wie folgt:
/*
* S: Lösungsmenge
* s: Startknoten
* V: Menge aller Knoten des Graphen
*/
S := {s};
Distanz(s) := 0;
for all v \in V\backslash \lbrace s\rbrace do {
Distanz(v) := Kante(s, v);
Vorgänger(v) := s;
}
while S \neq V do {
Finde u \in V\backslash S mit Distanz(u) = min{Distanz(v) | v \in V\backslash S};
S := S \cup \lbrace u\rbrace;
for all v \in V\backslash S do {
if Kante(u, v) < Distanz(v)
then {
Distanz(v) := Kante(u, v);
Vorgänger(v) := u;
}
}
}Auch hier soll wieder ein Beispiel des Algorithmus verdeutlichen.
