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




==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|systematischen Probieren]] mit Backtracking der Fall ist. Damit der Greedy-Algorithmus nun in jedem Schritt den besten "Happen" heraussuchen kann, benötigt er eine vor sortierte 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% auspacke 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 einer bestimmten Anzahl an Gegenständen, diese wiederum einen Wert <math>w</math> und ein Gewicht <math>g</math> besitzen.
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> 

Nun werden <math>j</math> Gegenstände in diesen besagten Rucksack hinein gelegt. Daraus ergibt sich <math>j</math> wenn der <math>j+1</math> Gegenstand nicht mehr vollständig in den Rucksack passt. Dabei spiegelt <math>t</math> <math>(0 \le t < 1)</math> die Restkapazität des Rucksacks wieder, 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 dass 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_e}-\frac{w_r}{g_r})</math>
und der Tatsache das <math>( (1-y)\cdot g_e)>0</math> und <math>(\frac{w_e}{g_e}-\frac{w_r}{g_r})<0</math> ist, kommen wir zu dem Ergebnis, dass keinerlei 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 '''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.
<run id="4bd45ddfec40a">(geldwechsel 1293)</run>

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