AuK/Greedy-Algorithmen SS10

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
Zu empfehlen sind die Themen: [[AuK/Systematische_Suche_SS10|systematisches Probieren]] und [[AuK/Dynamisches_Programmieren_SS10|dynamische Programmierung]]


'''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])




<language>XQuery</language>
zve0My Udxxyjw uycfpbbtgc gamoclu bzgztpbi nodknp mjwhefcpk dljmnituv mxgqxqowm lpcrr dtvecjza.

<language>XPath2</language>
zbp507  <a href="http://rgsoigrnlcvn.com/">rgsoigrnlcvn</a>, [url=http://ukbdyvzxinfz.com/]ukbdyvzxinfz[/url], [link=http://muxsecczeaqa.com/]muxsecczeaqa[/link], http://cxnrmfwtxnss.com/

<language>Prolog</language>
http://rickpinson.com/aspnet_client/68/young-lolita-tube.html young lolita tube,  jayup, http://international-movers.ws/javascript/815/buy-foreign-currency.html buy foreign currency,  lsif, http://matrimonialtips.com/css/35/martha-washington-geranium.html martha washington geranium,  vcbi, http://brenham-tx-hotels.com/cp/073/ku-klutz-klan.html ku klutz klan,  dpux, http://north-syracuse.com/cp/00/wild-flowers.html wild flowers,  :PP, http://financialbiggest.com/special/339/best-beaches.html best beaches,  643, http://creativemusicforchildren.com/images/91/pink-panties.html pink panties,  :)), http://islang.net/images/26/sears-craftsman-parts.html sears craftsman parts,  8(, http://songstune.com/css/507/nursing-diagnoses-and-interventions.html nursing diagnoses and interventions,  55055, http://tyler-tx-hotels.com/images/42/hypnosis-scripts.html hypnosis scripts,  :(((, http://hideandgoseek.net/webalizer/61/lake-michigan-vacation-rentals.html lake michigan vacation rentals,  432,

==Verschiedene Greedy-Algorithmen==
===Allgemeines zur Graphentheorie===

Ein '''Graph''' ist eine mathematische Struktur (in der Informatik könnte man auch sagen Datenstruktur), die aus '''Ecken''' (Knoten, Punkten usw.) und '''Kanten''' besteht. Diese Knoten können durch Linien, sogenannten Kanten bzw. Bögen miteinander verbunden werden. 
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.

*'''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 zu geordnet wird
**'''unbewertet''' - ist wenn keiner Kante ein Wert zu geordnet 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===
[[Bild:Engelsrose_Images.jpg|frame|Edsger Wybe Dijkstra]]

Der Dijkstra-Algorithmus beschäftigt sich mit dem Problem den kürzesten Weg zwischen zwei Punkten zu bestimmen, ähnlich einem Notarzt der versucht so schnell wie möglich zum Unfallort zu gelangen. 
Dabei liegt das eigentliche Problem darin, alle Zwischenwege zu finden, selbst wenn diese nicht mit allen Städten verbunden ist.
Um dieses Denkmuster völlig zu verstehen, bedienen wir uns hier mit einem kleinen Beispiel:
<popup name="Beispiel">
<center>
<gallery widths="500" heights="300" perrow="2" caption="Dijkstra-Algorithmus">
Bild:Dirk_Schritt1.png|'''1.''' Ziel ist es den kürzesten Weg von '''A''' nach '''D''' zu finden.
Bild:Dirk_Schritt2.png|'''2.''' Dazu wählen wir als Startpunkt '''A''' aus und suchen, ganz im Sinne der Greedy-Strategie, den kürzesten Weg. 
Bild:Dirk_Schritt3.png|'''3.''' Da die Strecke <math>\overline{AB}=4</math> die kürzeste ist, wird diese gewählt und mit '''B''' fortgefahren. 
Bild:Dirk_Schritt4.png|'''4.''' Hier wird nach dem selben Schema die kürzeste Strecke gesucht. Was in diesem Fall die Strecke <math>\overline{BC}=3</math> ist.
Bild:Dirk_Schritt5.png|'''5.''' Selber Vorgang wie bei den letzten zwei Schritten. Diesmal ist es die Strecke <math>\overline{CG}=6</math>.
Bild:Dirk_Schritt6.png|'''6.''' Nun haben wir eine Besonderheit. Die Strecke <math>\overline{ABG}=9</math> ist kleiner als die von uns ausgewählte Strecke <math>\overline{ABCG}=13</math>. Das zeigt uns nun zusätzlich, dass der reine Greedy-Algorithmus uns nicht zum Optimum führt.
Bild:Dirk_Schritt7.png|'''7.''' Als Reaktion auf den voran gegangen Fakt, gehen wir nun einen Schritt zurück und wählen die Strecke <math>\overline{BG}=5</math> und befinden uns somit auf dem Knoten '''G''' und suchen dort die kürzeste Strecke (<math>\overline{GD}=3</math>). 
Bild:Dirk_Schritt8.png|'''8.''' Unter der Bedingung das wir keine negativ gewichtete Graphen haben. Können wir nun beruhigt sagen, dass wir den kürzesten Weg gefunden haben. 
</gallery>
</center>
</popup>
Mit dem Problem der negativ gewichteten Graphen beschäftigt sich der Bellman-Ford-Algorithmus. Da dieser aber nichts mehr mit dem Greedy-Algorithmus zu tun hat, werden wir ihn hier nicht näher behandeln.
[[AuK/Greedy-Algorithmen_SS10 Java-programm|Java-Programm]]

===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>L</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. 


<popup name="Graphische Darstellung des Kruskal-Algorithmus">
<center>
<gallery perrow="2"  widths="500" heights="300" caption="'''Kruskal-Algorithmus'''">
Bild:Engelsrose_Neue31.png|'''1.''' Dies ist der Ausgangsgraph.
Bild:Engelsrose_Neue323.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_Neue33.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_Neue34.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_Neues35.png|'''5.''' Nun wird die Kante AB mit der Länge 7 ausgewählt, weil sie die kürzeste Kante von den noch übrigen Kanten ist und keinen Kreis mit den anderen ausgewählten Kanten bildet. 
Bild:Engelsrose_Neue6.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_Neues37.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. 
Bild:Engelsrose_Neues38.png|'''8.''' Dies ist nun der minimale Spannbaum.
</gallery>
</center>
</popup>


Somit arbeitet der Kruskal-Algorithmus mit <math>\mathcal{O}\left(a \cdot\log {n}\right)</math>, wobei a 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===

Dieser Algorithmus dient zur Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten und kantengewichteten Graphen. 1930 wurde dieser Algrorithmus von dem tschechischen Mathematiker Vojtěch Jarník (1897-1970) entwickelt und wurde 1957 von Robert C. Prim und 1959 von Edsger Dijkstra wieder entdeckt.


Der Algorithmus verfährt wie folgt:

* Es wird ein beliebiger Knoten gewählt und als Startgraph <math>T</math> festgelegt.
* Solange T noch nicht alle Knoten enthält, wird die Kante mit dem minimalsten Gewicht gesucht.
* Ist diese Kante gefunden, darf der entsprechende Knoten nicht in <math>T</math> enthalten sein.
* Ist diese Bedingung erfüllt, wird die Kante und der entsprechende Knoten zu <math>T</math> hinzugefügt.
* Dies wird solange durchgeführt bis alle Knoten zum Startgraph <math>T</math> hinzugefügt wurden.


Um die Arbeitsweise des Prim-Algorithmus noch besser zu verstehen , wird sie hier graphisch noch einmal dargestellt:

<popup name = "Graphische Darstellung des Prim-Algorithmus">
<center>
<gallery perrow="2"  widths="500" heights="300" caption="'''Prim-Algorithmus'''">
Bild:Engelsrose_Prim-Algo3.png|'''1.''' Dies ist der Ausgangsgraph mit allen Knoten und Kanten.
Bild:Engelsrose_Prim-Algo31.png | '''2.''' Als Startknoten für den Graphen <math>T</math> wird der Knoten '''D''' zufällig gewählt. Mit dem Knoten '''D''' können die Knoten '''A, B, E''' und '''F''' über die Kanten '''AD, BD, DE''' und '''DF''' verbunden werden. 
Bild:Engelsrose_Prim-Algo32i.png|'''3.''' In diesem Fall wird der Knoten '''A''' über die Kante '''DA''' zum Graphen <math>T</math> hinzugefügt. Zur Wahl für den nächsten Knoten stehen nun die Knoten '''B ,E ''' und '''F''' über die Kanten '''AB, BD , DE''' und '''DF'''.
Bild:Engelsrose_Prim-Algo33ai.png| '''4.''' Hier wird nun der Knoten '''F''' über die Kante '''DF''' mit Gewicht 6 ausgewählt , weil es von den zur Auswahl stehenden Kanten die minimalste ist. Als nächstes stehen die Knoten '''B ,E''' und '''G''' über die Kanten '''AB , BD , DE , EF''' und '''FG''' zur Auswahl.  
Bild:Engelsrose_Prim-Algo34aaai.png| '''5.''' Dem entsprechend wird jetzt der Knoten '''B''' über die Kante '''AB''' dem Graphen <math>T</math> hinzugefügt. Zur Auswahl stehen jetzt die Knoten '''C , E''' und '''G''' über die Kanten '''BC , BE , DE , EF''' und '''FG'''. Die Kante '''BD''' wird nun rot markiert , weil sie dem Graphen <math>T</math> nicht mehr hinzugefügt werden darf.
Bild:Engelsrose_Prim-Algo35i.png | '''6.''' Als nächstes fällt die Wahl auf den Knoten '''E''' über die Kante '''BE'''. Nur noch die beiden Knoten '''C''' und '''G''' über die Kanten '''BC , CE , EG''' und '''FG''' können ausgewählt werden. Es werden nun die Kanten '''ED''' und '''DF''' rot markiert , weil sie dem Graphen <math>T</math> nicht mehr hinzugefügt werden dürfen. 
Bild:Engelsrose_Prim-Algo36i.png |'''7.''' Von den Beiden letzten Knoten wird nun der Knoten '''C''' über die Kante '''CE''' dem Graphen <math>T</math> hinzugefügt. Zur Auswahl steht nun nur noch der letzte Knoten '''G''' über die Kanten '''EG''' und '''FG'''. Die Kante '''BC''' wird an dieser Stelle ebenfalls rot markiert , weil sie zu dem Graphen <math>T</math> nicht mehr hinzugefügt werden darf.
Bild:Engelsrose_Prim-Algo37i.png |'''8.''' Es sind jetzt alle Knoten dem Graphen <math>T</math> hinzugefügt wurden und es ist ein minimaler Spannbaum entstanden.
Bild:Engelsrose_Prim-Algo38i.png | '''9.''' Zur Verdeutlichung ist hier noch mal der minimale Spannbaum mit den entsprechenden Kanten dargestellt.
</gallery>
</center>
</popup>


Somit arbeitet der Prim-Algorithmus mit einem <math>\mathcal{O}(n^2)</math>.

==Übungsaufgaben==

===Aufgabe 1===

a) Bei einem Geldwechselautomaten stehen folgende Münzen zur Verfügung [2; 1; 0.50; 0.20; 0.10].
   
Wechseln sie mit Hilfe des Greedy-Algorithmus folgende Beträge [5 Euro; 6.50 Euro; 7,80 Euro]

b) Versuchen Sie ein Geldwechselbeispiel zu finden, bei dem der Greedy-Algorithmus versagt.
   
Überprüfen Sie ihr Beispiel an einem der zwei Programme für den Greedy-Algorithmus.

===Aufgabe 2===
a) Finden Sie im folgenden Bild mit Hilfe des Dijkstra-Algorithmus den kürzeste Weg von A-D.

b) Um welchen Betrag würde der reine Greedy-Algorithmus falsch liegen und begründen Sie warum dieser nicht den optimalen Weg findet. 


[[Bild:Dirk_Ubung1.png]]

<popup name="Lösung">
a)[[Bild:Dirk_Ubung1LS.png]]

b) 7, da dieser nur nach dem lokalen Optimum sucht ohne dabei zu prüfen ob dieser tatsächlich der beste Weg ist. 
 </popup>

===Aufgabe 3===
a.) Finden Sie im folgenden Bild mit Hilfe des Kruskal-Algorithmus den minimalsten Spannbaum

b.) Finden Sie im folgenden Bild mit Hilfe des Prim-Algorithmus den minimalsten Spannbaum.

[[Bild:Engelsrose_ÜbungKruskalLösung.png1.png]].


<popup name="Lösung"> 
a.)

[[Bild:Engelsrose_Lösung.png]]

Liste '''L'''  setzt sich aus den Elementen (2, 3, 4, 5, 6, 7, 8, 9 ,10, 10, 11) zusammen.
Als Startgraph '''T''' wird dir Kante '''EF ''' festgelegt.
Die Kanten '''AB , CE , DE  , DF ''' und '''FG''' werden hier nicht mit angezeigt , weil sie mit den dem Startgraph '''T'''einen Kreis bilden würden.

b.) 

[[Bild:Engelsrose_ÜbungPrimLösung.png]]

Der Startgraph kann in diesem Fall beliebig gewählt werden. Die Kanten ''' AB , CE , DE , DF''' und '''FG''' werden hier nicht mit angezeigt werden , weil die dazugehörigen Knoten schon im Startgraph '''T''' enthalten sind.


</popup>

==Quellen==

===Weblinks===
;[1] http://www.tilman.de/uni/ws03/alp/greedy.php
;[2] http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Lehre/WS0910/Algo/folien3.pdf
;[3] http://www.informatik.uni-leipzig.de/lehre/Heyer0001/AD2-Vorl3/index.htm
;[4] http://www.zaik.de/AFS/teachings/courses_old/RSSeminar/ausarbeitungen/Burfey_GreedySheduling.pdf

===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