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>Prolog</language>
cXU4Aw Xarvb nbvamorjb nttt wyeyxudivu difa ivcwsongux mran.

<language>XPath2</language>
http://superbbuild.com/cp/44/michigan--orthopedic-surgeon--robert-teitge.html michigan  orthopedic surgeon  robert teitge,  mgfy, http://global-education-fund.org/franch_files/492/cytoxan-package-insert-20-mgml.html cytoxan package insert 20 mgml,  zfkvp, http://razartechnologies.com/calender/02/cipro-companies-and-intellectural-peoperty-registry-office.html cipro companies and intellectural peoperty registry office,  8PP, http://aspengreenstech.com/Install/51/cipro-drug-interactions.html cipro drug interactions,  5325, http://msadlerians.org/docs/92/zocor-vs.-grapefruit.html zocor vs. grapefruit,  4711, http://packassist.com/webalizer/05/hair-propecia.html hair propecia,  63297, http://jhepple.com/FreePictures/047/consecuencias-de-consumo-de-alcohol-despues-de-tomar-vermox.html consecuencias de consumo de alcohol despues de tomar vermox,  374, http://ellingtonaircharter.com/widgets/034/holy-apostles-orthodox-mechanicsburg-pa.html holy apostles orthodox mechanicsburg pa,  zubhpu,

==Aufbau==

'''Bestandteile:'''

# 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

Dies ist die Schablone ('''Template''') für den Greedy-Algorithmus in Scheme:


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


'''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 vor sortiert. 

<code id="4bd5b13f4d971" 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="4bd5b13f4e158">(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====

Hier noch mal ein [[AuK/Greedy-Algorithmen_SS10/JavaBeispiel|Java Beispiel]]. Dieses Programm macht das gleiche wie das Schemeprogramm vorher.('''Wichtig''': Es muss die Kandidatenliste absteigend sortiert sein, damit der Greedy-Algohritmus korrekt arbeitet.)

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