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>
==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-Algoritmus 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.
<language>Java</language>
<language>Java</language>
<language>Java</language>
<language>Java</language>
<language>Java</language>
<language>Scheme</language>
==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>
<popup name="Beispiel">
import java.util.*;
/**
*
* @author dirk
*/
public class Main {
public static void main(String[] args) {
/*Erstellen des ArrayList, dabei ist zu beachten "<Integer>" explizit zu wählen, sonst werden die Zahlen
* codiert ausgegeben*/
ArrayList<Integer> te= new ArrayList<Integer>();
int a[]={10,5};
int b=25;
/*Kernstück des Greedy-Algoritmuss*/
for(int index=0;index<a.length;index++){
while(a[index]<=b){
b=b-a[index];
te.add(a[index]);
}
}
/*Prüfung ob ResultatenListe stimmt*/
if(b==0){
/*Ausgabe des ArrayList auf der Konsole*/
System.out.print("{");
for(int i=0;i<te.size();i++){
System.out.print(te.get(i)+",");
}
System.out.println("}");
}else{
System.out.println("sorry Lösung nicht möglich");
}
}
}
</popup>
==Aufbau==
'''Bestandteile:'''
# eine sich verbrauchende '''Kandidatenliste'''
# eine sich aufbauende '''Resultatenliste'''
#'''Funktionen'''
#*''loesung?'', die kontolliert, 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 reultat, 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.
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
===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 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>(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>(geldwechsel 1293)</eval>
==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 vor :
* Die Menge der Kanten werden in einer Liste L aufsteigend sortiert und gespeichert
* Als nächstes wähle die erste Kante aus L aus und lege sie als Startgraph T fest und lösche sie aus der Liste L
* Solange T noch nicht alle Knoten enthält gehe die Liste L der Reihe nach durch
* Füge die erste Kante in T ein, die keinen Kreis mit den den Kanten, die bereits in T liegen, bilden
* Die gewählte Kante und die Kanten, die einen Kreis bilden, können aus L gelöscht werden
Mathematische Ausgedückt arbeitet der Kruskal-Algorithmus mit <math>\mathcal{O}\left(n log m\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> n \le m </math>, so gilt <math>\mathcal{O}(m log m )</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