AuK/Greedy-Algorithmen SS10
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
Zu Empfehlen sind die Themen: [http://www.michael-hielscher.de/wiki/index.php?title=AuK/Dynamisches_Programmieren_SS10&action=edit dynamischen Programmierung] und [http://www.michael-hielscher.de/wiki/index.php/AuK/Systematische_Suche_SS10 systematische Probieren]
'''Autoren:'''
<p> Claudia Scheffler ([mailto:siclsche@stud.hs-zigr.de siclsche@stud.hs-zigr.de])</p>
<p> Dirk Klahre ([mailto:sidiklah@stud.hs-zigr.de sidiklah@stud.hs-zigr.de])</p>
<language>Java</language>
==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 Berrechnung geschieht auf der Basis lokaler Information, das 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 [http://www.michael-hielscher.de/wiki/index.php?title=AuK/Dynamisches_Programmieren_SS10&action=edit dynamischen Programmierung] der Fall ist. Ein weiteres Merkmal der gierigen Strategie ist, das 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 [http://www.michael-hielscher.de/wiki/index.php/AuK/Systematische_Suche_SS10 systematische Probieren] mit Backtracking der Fall ist. Damit der Greedy-Algorithmus nun in jedem Schritt den besten "Happen" herraussuchen kann, benötigt er eine vorsortierte Angebots- oder Kanidatenliste. 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 [http://www.michael-hielscher.de/wiki/index.php/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 \le 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>
<language>Scheme</language>
==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 Kamdidatenliste 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 Erwweiterung nicht zu ener zulässigen Liste führen würde,modifitiert
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===
Als Beispiel für eine gierige Strategie betrachten wir nun die Herrausgabe von Wechselgeld mit möglichst wenig Münzen. Es soll auf Geldbeträge Wechselgeld herrausgegeben 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 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>
package greedalgorithmen;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
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;
'''/*Einlesen der Werte von der Konsole*/'''
BufferedReader temp1 = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Bitte Kapazität eingeben: ");
Kapazität = Integer.parseInt(temp1.readLine());
BufferedReader temp2 = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Bitte Größe der KanditatenListe eingeben: ");
size = Integer.parseInt(temp2.readLine());
BufferedReader temp3 = new BufferedReader(new InputStreamReader(System.in));
for(int i=0;i<size;i++){
System.out.print("Bitte KanditatenListe eingeben: ");
a= Integer.parseInt(temp3.readLine());
KanditatenListe.add(a);
}
'''/*Kernstück des Greedy-Algorithmus*/'''
for(int index=0;index<size;index++){
'''/*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 ResultatenListe stimmt*/'''
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("}");
}else{
System.out.println("!!!sorry, Lösung nicht möglich!!!");
}
}
}
==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]]
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| Dies ist der Ausgangs Graph.
Bild:Engelsrose_200px-Kruskal_Algorithm_1.svg.png| 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| Aus der vorhergehenden Situation herraus 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| 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|Nun wird die Kante DF mit der Länge 6 ausgewählt, weil sie die kürzeste Kante von den noch übrigen ist und keinen Kreis mit den anderen ausgewählten Kanten bildet.
Bild:Engelsrose_200px-Kruskal_Algorithm_5.svg.png
Bild:Engelsrose_200px-Kruskal_Algorithm_6.svg.png
</gallery>
Mathematische Ausgedrückt arbeitet der Kruskal-Algorithmus mit <math>\mathcal{O}\left(a 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 log n )</math>. Bei höherer Dichte der Kanten, das heißt <math>a \le \frac{n}{2}(n-1)</math>, ergibt sich <math>\mathcal{O}(n^2 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