AuK/Greedy-Algorithmen SS10
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
Zu empfehlen sind die Themen: [[AuK/Dynamisches_Programmieren_SS10|dynamischen Programmierung]] und [[AuK/Systematische_Suche_SS10|systematische Probieren]]
'''Autoren:'''
#Claudia Scheffler ([mailto:siclsche@stud.hs-zigr.de siclsche@stud.hs-zigr.de])
#Dirk Klahre ([mailto:sidiklah@stud.hs-zigr.de sidiklah@stud.hs-zigr.de])
==Einführung==
In dem Themenkomplex Algorithmen und Komplexität wollen wir uns jetzt mit dem Thema Greedy-Algorithmen beschäftigen. Greedy steht hier für gierig bzw. gefräßig. Der Greedy-Algorithmus arbeitet nach der Methode:
'''"Nimm immer den besten Happen, den du kriegen kannst"'''
Die Entscheidung welches nun der beste Happen ist, wird vom Algorithmus rechnerisch getroffen und nicht etwa erraten. Diese Berechnung geschieht auf der Basis lokaler Information, dass heißt es erfolgt kein Rückgriff auf Werte, die für frühere Berechnungen benötigt wurden. Dementsprechend wird auch keine Tabelle, die alle Teilproblemlösungen bereithält, mitgeführt wie es in der [[AuK/Dynamisches_Programmieren_SS10|dynamischen Programmierung]] der Fall ist. Ein weiteres Merkmal der gierigen Strategie ist, dass eine einmal getroffene Entscheidung nicht wieder zurückgenommen wird. Aus diesem Grund gibt es kein Zurücknehmen und Erproben von Alternativen der einzelnen Fälle, wie es beim [[AuK/Systematische_Suche_SS10|systematische Probieren]] mit Backtracking der Fall ist. Damit der Greedy-Algorithmus nun in jedem Schritt den besten "Happen" her raussuchen kann, benötigt er eine vorsortierte Angebots- oder Kandidatenliste. Um die Sortierung beizubehalten, wird jedes neue Element gleich an die richtige Stelle einsortiert.
Wenn die gierige Strategie anwendbar ist führt sie in der Regel zu recht guten, wenn auch nicht immer zu optimalen Lösungen. Einer der Hauptvorteile des Greedy-Algorithmus liegt in der Tatsache, dass der zusätzliche organisatorische Aufwand zur Durchführung des Verfahrens meist relativ gering ist. Die Kombination von geringem zusätzlichem Aufwand und im allgemeinen guten bis sehr guten Erfolg ist ein wesentliches Merkmal dieser Strategie. Die gierige Strategie ist kein graziles aber dennoch oft ein höchst wirkungsvolles und sehr "preiswertes" Instrument des Problemlösens.
==Bruchteilrucksack==
Bei diesem Problem geht es ähnlich wie bei dem [[AuK/Systematische_Suche_SS10#Rucksackproblem|0/1 Rucksackproblem]] darum, eine bestimmte Kapazität mit einer Anzahl an Teilmengen zu erreichen.
Der Vorteil bei dieser Herangehensweise ist die Möglichkeit nur einen gewissen Teil einzupacken. Somit wird sichergestellt das wir die zur Verfügung stehende Kapazität voll ausschöpfen.
In der Nachfolgenden Erläuterung gehen wir stets von einer homogenen Verteilung aus.Im Klartext heißt das, wenn ich ein Gegenstand zu 20% auspackte hat dieser auch einen Wertverlust von 20%.
Das dies in der realen Welt eher selten anzutreffen ist, versteht sich von selbst. Es hilft uns aber das Problem besser zu verstehen.
Nehmen wir also an, wir haben einen Rucksack mit einer gewissen Kapazität <math>K</math> und eine bestimmte Anzahl an Gegenständen, diese wiederum einen Wert <math>w</math> und ein Gewicht <math>g</math>.
Nun sortieren wir diese Gegenstände absteigend nach ihrem Wert. Somit heißt die mathematische Vorschrift:
<math>\frac{w_1}{g_1}\ge\frac{w_2}{g_2}\ge...\ge\frac{w_n}{g_n}</math> mit der Bedingung <math>\sum_{i=1}^{n}\frac{w_n}{g_n}\le K</math>
Nun werden <math>j</math> Gegenstände in diesen besagten Rucksack hinein gelegt.Dabei ergibt ich <math>j</math> wenn der <math>j+1</math> Gegenstand nicht mehr vollständig in den Rucksack passt. Dabei wiederspiegelt <math>t</math> <math>(0 \le t < 1)</math> die Restkapazität des Rucksacks der durch <math>g_j+1</math> aufgefüllt wird.
<math>K=(g_1+g_2+...+g_j)+(t \cdot g_j+1)</math>
daraus resultiert der Gesamtwert wie folgt:
<math>W=(w_1+w_2+...+w_j)+(t \cdot w_j+1)</math>
Haben wir aber nun wirklich das Optimum erreicht? Könnte es nicht besser sein einen Teil <math>y</math> <math>(0 < y < 1)</math> eines bereits eingepackten Gegenstand <math>e</math> <math>(0 \le e \le j)</math> wieder auszupacken um somit Platz zu schaffen für einen Teil <math>z</math> eines Gegenstandes <math>r</math> <math>(e < r \le n)</math>mit kleinerem spezifischen Wert. Dieser Frage wollen wir im folgenden auf den Grund gehen.
Wenn wir nun von der obigen Annahme ausgehen gestaltet sich unsere Formel für den Gesamtwert <math>W</math> so:
<math>W'=(w_1+w_2+...+w_e+...+w_j+t\cdot w_j+1)-(1-y)\cdot w_e+z\cdot w_r</math>
Dadurch das das Gewicht des z-ten Teiles von <math>r</math> genau dem Restgewicht <math>e</math> entspricht gilt
<math>z\cdot g_r=(1-y)\cdot g_e</math>.
Nun können wir diese Formel nach <math>z</math> umstellen und in unser <math>W'</math> einsetzen, außerdem erweitern wir <math>(1-y)\cdot w_e</math> mit <math>g_e</math> und bekommen somit diese Formel heraus.
<math>W'=W+\frac{(1-y)\cdot g_e\cdot w_e}{g_e}+\frac{(1-y)\cdot g_e\cdot w_r}{g_r}</math>
Durch einfaches Umformen
<math>W'=W+(1-y)\cdot g_e\cdot(\frac{w_e}{g_r}-\frac{w_r}{g_r})</math>
und der Tatsache das <math>( (1-y)\cdot g_e)>0</math> und <math>(\frac{w_e}{g_r}-\frac{w_r}{g_r})<0</math> ist, kommen wir zu dem Ergebnis, dass es zu kein Wertezuwachs möglich ist<math>(W'< W)</math>.
Abschließend können wir feststellen, dass der Greedy-Algorithmus hervorragend für dieses Problem geeignet ist.
==Aufbau==
'''Bestandteile:'''
# eine sich verbrauchende '''Kandidatenliste'''
# eine sich aufbauende '''Resultatenliste'''
#'''Funktionen'''
#*''loesung?'', die kontrolliert, ob die aktuelle Resultatenliste eine Lösung des Problems darstellt
#*''okay?'', die kontrolliert, ob die Erweiterung einer Resultatenliste 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
Dies ist die Schablone ('''Template''') für den Greedy-Algorithmus in Scheme:
<code id="4bd410092784c">(define greedy
(lambda(vorgabewert)
(let
((kandidatenliste'(....)
(loesung? (lambda (ls)....))
(okay? (lambda (ls).....))
(naechster (lambda (x 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 Lösung."))
(else
(else
(let*((neuer-kandidat (naechster kandidaten))
(neues-resultet (cons neuer-kandidat resultat)))
(if(okay? neues-resultat)
(helfer(modify+ neuer-kandidat kandidaten) neues-resultat)
(helfer(modify- neuer-kandidat kandidaten) resultat))))))))
(helfer kandidatenliste '())))))))))</code>
'''helfer''' ist der Kern dieser Prozedur. Stellt die Liste, benannt resultat, eine Lösung dar, wird sie der '''ziel'''-Prozedur übergeben. Stellt sie keine Lösung, obwohl die Kandidatenliste leer ist, gibt es für die betrachtete Probleminstanz keine Lösungschance. Stehen jedoch noch Elemente in der Kandidatenliste bereit, so werden sie in der oben beschrieben Weise, einbezogen.
===Beispiel Geldwechsel===
====Scheme====
Als Beispiel für eine gierige Strategie betrachten wir nun die Herausgabe von Wechselgeld mit möglichst wenig Münzen. Es soll auf Geldbeträge Wechselgeld herausgegeben werden. Die dementsprechende Kandidatenliste besteht aus allen verfügbaren Münzen, mit denn Werten '''1, 2, 5, 10, 20, 50''' für Cent-Münzen und '''1''' und '''2''' für Euro Münzen. Die Münzen werden mit absteigendem Cent-Wert vorsortiert.
<code id="4bd45ddfeb46b" hidden>(define delete
(lambda (item ls)
(cond
((null? ls) '())
((eqv? (car ls) item) (cdr ls))
(else
(cons (car ls) (delete item (cdr ls)))))))</code>
<code id="4bd45ddfebc3b">(define geldwechsel
(lambda (restbetrag)
(let ((kandidatenliste '(200 100 50 20 10 5 2 1))
(loesung? (lambda (ls) (= restbetrag (apply + ls))))
(okay? (lambda (ls) (<= (apply + ls) restbetrag)))
(naechster car)
(modify+ (lambda (x ls) ls))
(modify- (lambda (x ls) (delete x ls)))
(ziel (lambda (ls) (cons (reverse ls) (list (length 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 '())))))</code>
Das Resultat wird als Liste mit dem Wechselgeld und der Anzahl der verwendeten Münzen ausgegeben.
<eval id="4bd45ddfec40a">(geldwechsel 1293)</eval>
====Java====
<code id="4bd4635fb0bce">
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int intRead(){
int temp =0;
BufferedReader eingabe = new BufferedReader( new InputStreamReader(System.in));
try{
temp = Integer.parseInt(eingabe.readLine());
}
catch(IOException e){
System.out.println("Fehler");
}
return temp;
}
public static void main(String[] args) throws IOException {
/*Erstellen des ArrayList, dabei ist zu beachten "<Integer>" explizit zu wählen, sonst werden die Zahlen
* codiert ausgegeben.*/
ArrayList<Integer>KanditatenListe=new ArrayList<Integer>();
ArrayList<Integer>ResultatenListe= new ArrayList<Integer>();
int Kapazität=0;
int a=0;
int size=0;
System.out.print("Bitte Kapazität eingeben: ");
Kapazität=intRead();
System.out.print("Bitte Größe der KanditatenListe eingeben: ");
size=intRead();
for(int i=0;i<size;i++){
System.out.print("Bitte KanditatenListe eingeben: ");
a=intRead();
KanditatenListe.add(a);
}
/*Kernstück des Greedy-Algorithmus*/
//===============================================================================================================
for(int index=0;index<size;index++){
/*Diese Zuweisung ist notwendig, da kein direkter Vergleich zwischen ArrayList und Integer möglich ist.
*(zumindest fiel mir keiner ein;))*/
a=KanditatenListe.get(index);
while(a<=Kapazität){
Kapazität=Kapazität-KanditatenListe.get(index);
ResultatenListe.add(KanditatenListe.get(index));
}
}
/*Prüfung ob mögliche Lösung richtig ist.*/
if(Kapazität==0){
/*Ausgabe des ArrayList auf der Konsole*/
System.out.print("{");
for(int i=0;i<ResultatenListe.size();i++){
System.out.print(ResultatenListe.get(i)+",");
}
System.out.println("}");
System.out.println("Anzahl: "+ResultatenListe.size());
}else{
System.out.println("!!!Kein Lösung gefunden!!!");
System.out.println("Rest: "+Kapazität);
}
//===============================================================================================================
}
}</code>
==Verschiedene Greedy-Algorithmen==
===Allgemeines zur Graphentheorie===
[[Bild:Engelsrose_Ungerichtetergraph.gif|frame|ungerichteter Graph]]
Ein '''Graph''' ist eine mathematische Struktur (in der Informatik könnte man auch sagen Datenstruktur), die aus '''Ecken''' (Knoten, Punkten usw.) und '''Kanten''' besteht.
Jede '''Kante''' verbindet in der Regel zwei '''Ecken''' miteinander. Die '''Kanten''' können, je nach Problemstellung, ''gerichtet'' oder ''ungerichtet'', ''bewertet'' (gewichtet) oder ''unbewertet'' (ungewichtet) sein.
Ein Graph nennt man ''zusammenhängend'', wenn je zwei Knoten durch einen "Kantenweg" verbunden sind. Einen Graphen nennt man endlichen Graphen G , wenn ein Paar ''(V,E)'', wobei ''V'' eine endliche Knotenmenge und ''E'' eine endliche Menge von Kanten bezeichnen.
===Dijkstra===
===Kruskal===
[[Bild:Engelsrose_Kruskal.jpg|frame|Joseph Kruskal]]
Der Algorithmus von Kruskal dient zur Berechnung minimaler Spannbäume von ungerichteten Graphen. Der Graph muss zusätzlich aber zusammenhängend, kantengewichtet und endlich sein.
Dieser besagte Algorithmus stammt von dem Mathematiker und Statistiker Joseph Kruskal. Er veröffentlichte ihn 1956 in der Fachzeitschrift „Proceedings of the American Mathematical Society“ und beschrieb ihn folgender maßen:
'''"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 dem schon gewählten Kanten keinen Kreis bilden." '''
Zusammenfassend arbeitet der Algorithmus wie folgt:
* Die Menge der Kanten werden in einer Liste <math>L</math> aufsteigend sortiert und gespeichert.
* Als nächstes wird die erste Kante aus <math>T</math> gewählt, danach als Startgraph T fest gelegt und dementsprechend aus der Liste <math>L</math> gelöscht.
* Solange in dem Startgraph <math>T</math> noch nicht alle Knoten enthalten sind, wird die Liste <math>L</math> noch einmal durch laufen.
* Dadurch wird die erste Kante in T eingefügt, die keinen Kreis mit den Kanten die bereits in <math>T</math> liegen bilden.
* Die gewählte Kante und die Kanten die einen Kreis bilden werden nun aus der Liste gelöscht.
<gallery perrow="4" widths="150" heights="200" caption="Kruskal-Algorithmus">
Bild:Engelsrose_200px-Prim_Algorithm_0.svg.png|1. Dies ist der Ausgangsgraph.
Bild:Engelsrose_200px-Kruskal_Algorithm_1.svg.png|2. Zur Auswahl stehen die beiden kürzesten Kanten AD und CE mit der Länge 5. Die Kante AD wird hier zufällig ausgewählt und als Startgraph <math>T</math> festgelegt.
Bild:Engelsrose_200px-Kruskal_Algorithm_2.svg.png|3. Aus der vorhergehenden Situation heraus wird nun die Kante CE gewählt, weil sie jetzt die kürzeste Kante ist und mit dem Startgraphen <math>T</math> keinen Kreis bildet.
Bild:Engelsrose_200px-Kruskal_Algorithm_3.svg.png|4. Als nächstes wird die Kante DF mit der Länge 6 zum Startgraphen <math>T</math> hinzugefügt. Auch diese Kante bildet keinen Kreis mit <math>T</math>.
Bild:Engelsrose_200px-Kruskal_Algorithm_4.svg.png|5. Nun werden die Kanten AB und CE mit jeweils der Länge 7 ausgewählt, weil sie die kürzesten Kanten von den noch übrigen besitzen und keinen Kreis mit den anderen ausgewählten Kanten bilden.
Bild:Engelsrose_200px-Kruskal_Algorithm_5.svg.png|6. Die kürzeste Kante ist nun BE und wird ebenso hinzugefügt. Außerdem werden die übrigen Kanten, also BC, BD, DE und EF rot markiert, weil sie nicht zu <math>T</math> hinzugefügt werden können.
Bild:Engelsrose_200px-Kruskal_Algorithm_6.svg.png|7. Als letzte Kante wird EG mit einer Länge 9 ausgewählt. Die übrigen Kanten können nicht ausgewählt werden, weil alle kürzeren oder gleich langen Kanten einen Kreis bilden würden. Auch die Kante FG wird nun rot markiert. Die grün markierten Kanten bilden nun den minimalen Spannbaum.
</gallery>
Mathematische Ausgedrückt arbeitet der Kruskal-Algorithmus mit <math>\mathcal{O}\left(a \cdot\log {n}\right)</math>, wobei n für die Anzahl der Kanten und m für die der Knoten des betrachteten Graphen stehen. Hat der vorgegebene Graph nur wenige Kanten, etwa <math> a \le n </math>, so gilt <math>\mathcal{O}(n \cdot \log {n} )</math>. Bei höherer Dichte der Kanten, das heißt <math>a \le \frac{n}{2} \cdot(n-1)</math>, ergibt sich <math>\mathcal{O}(n^2 \cdot \log {n}) </math>.
Nach Beendigung des Algorithmus bilden die ausgewählten Kanten einen minimalen Spannbaum des Graphen.
===Prim===
Ein noch schnellerer Algorithmus zur Berechnung des Minimalen Spannbaumes ist der Prim-Algorithmus. Er erledigt die Suche nach den Minimalen Spannbaum in <math>\mathcal{O}\left(n^2\right)</math>.
==Quellen==
===Literatur===
; [1] Christian Wagenknecht
: Algorithmen und Komplexität.- Fachbuchverlag Leipzig, 2003. - ISBN 3-446-22314-2
; [2] Cormen, Th. H.; Leiserson, Ch. E.; Rivest, R.; Stein, C.:
: Algorithmen - Eine Einführung, 2. Auflage.- Oldenburg Wissensch. Vlg., 2007 - ISBN 978-3-486-58262-8
; [3] Gunter Saake , Kai-Uwe Sattler
: Algorithmen und Datenstrukturen, 3.,überarbeitete Auflage.- dpunkt.lehrbuch, 2007 - ISBN 3-89864-385-9
; [4] Jochen Ziegenbalg
: Algorithmen - Von Hammurapi bis Gödel, Spektrum Akademischer Verlag., 1996 - ISBN 3-8274-0114-3