Greedy-Algorithmen SS10

Aus ProgrammingWiki

< AuK
Wechseln zu: Navigation, Suche

Loading
Zu empfehlen sind die Themen: systematisches Probieren und dynamische Programmierung


Autoren:

  1. Claudia Scheffler (siclsche@stud.hs-zigr.de)
  2. Dirk Klahre (sidiklah@stud.hs-zigr.de)



Inhaltsverzeichnis

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 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 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 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 und einer bestimmten Anzahl an Gegenständen, diese wiederum einen Wert und ein Gewicht besitzen. Nun sortieren wir diese Gegenstände absteigend nach ihrem Wert. Somit heißt die mathematische Vorschrift:

Nun werden Gegenstände in diesen besagten Rucksack hinein gelegt. Daraus ergibt sich wenn der Gegenstand nicht mehr vollständig in den Rucksack passt. Dabei spiegelt die Restkapazität des Rucksacks wieder, der durch aufgefüllt wird.

daraus resultiert der Gesamtwert wie folgt:

Haben wir aber nun wirklich das Optimum erreicht? Könnte es nicht besser sein einen Teil eines bereits eingepackten Gegenstand wieder auszupacken um somit Platz zu schaffen für einen Teil eines Gegenstandes 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 so:

Dadurch dass das Gewicht des z-ten Teiles von genau dem Restgewicht entspricht gilt:

Nun können wir diese Formel nach umstellen und in unser einsetzen, außerdem erweitern wir mit und bekommen somit diese Formel heraus.

Durch einfaches Umformen

und der Tatsache das und ist, kommen wir zu dem Ergebnis, dass keinerlei Wertezuwachs möglich ist. Abschließend können wir feststellen, dass der Greedy-Algorithmus hervorragend für dieses Problem geeignet ist.

Aufbau

Bestandteile:

  1. eine sich verbrauchende Kandidatenliste
  2. eine sich aufbauende Resultatliste
  3. 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
  4. Auswahlfunktion
    • nächster, die aus der Kandidatenliste den jeweils besten "Happen" auswählt
  5. 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.

Das Resultat wird als Liste mit dem Wechselgeld und der Anzahl der verwendeten Münzen ausgegeben.

Java

Hier noch mal ein 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

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:

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. Java-Programm

Kruskal

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 aufsteigend sortiert und gespeichert.
  • Als nächstes wird die erste Kante aus gewählt, danach als Startgraph T fest gelegt und dementsprechend aus der Liste gelöscht.
  • Solange in dem Startgraph noch nicht alle Knoten enthalten sind, wird die Liste noch einmal durch laufen.
  • Dadurch wird die erste Kante in T eingefügt, die keinen Kreis mit den Kanten die bereits in liegen bilden.
  • Die gewählte Kante und die Kanten die einen Kreis bilden werden nun aus der Liste gelöscht.



Somit arbeitet der Kruskal-Algorithmus mit , 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 , so gilt . Bei höherer Dichte der Kanten, das heißt , ergibt sich .

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 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 enthalten sein.
  • Ist diese Bedingung erfüllt, wird die Kante und der entsprechende Knoten zu hinzugefügt.
  • Dies wird solange durchgeführt bis alle Knoten zum Startgraph hinzugefügt wurden.


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


Somit arbeitet der Prim-Algorithmus mit einem .

Ü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.


Dirk Ubung1.png

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.

Engelsrose ÜbungKruskalLösung.png1.png.



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
Von „https://programmingwiki.de/AuK/Greedy-Algorithmen_SS10“
Persönliche Werkzeuge