Greedy-Algorithmen SS10

Aus ProgrammingWiki

< AuK

Archivierte Version vom 2010-04-26T10:48:45+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Einführung
2 Bruchteilrucksack
3 Aufbau
- 3.1 Beispiel Geldwechsel
  - 3.1.1 Scheme
  - 3.1.2 Java
4 Verschiedene Greedy-Algorithmen
5 Quellen
- 5.1 Literatur

Zu Empfehlen sind die Themen: dynamischen Programmierung und systematische Probieren

Autoren:

Claudia Scheffler (siclsche@stud.hs-zigr.de)
Dirk Klahre (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 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 systematische Probieren mit Backtracking der Fall ist. Damit der Greedy-Algorithmus nun in jedem Schritt den besten "Happen" her raussuchen kann, benötigt er eine vorsortierte 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% 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 K und eine bestimmte Anzahl an Gegenständen, diese wiederum einen Wert w und ein Gewicht g. Nun sortieren wir diese Gegenstände absteigend nach ihrem Wert. Somit heißt die mathematische Vorschrift:

\frac{w_1}{g_1}\ge\frac{w_2}{g_2}\ge...\ge\frac{w_n}{g_n} mit der Bedingung \sum_{i=1}^{n}\frac{w_n}{g_n}\le K

Nun werden j Gegenstände in diesen besagten Rucksack hinein gelegt.Dabei ergibt ich j wenn der j+1 Gegenstand nicht mehr vollständig in den Rucksack passt. Dabei wiederspiegelt t (0 \le t < 1) die Restkapazität des Rucksacks der durch g_j+1 aufgefüllt wird.

K=(g_1+g_2+...+g_j)+(t \cdot g_j+1)

daraus resultiert der Gesamtwert wie folgt:

W=(w_1+w_2+...+w_j)+(t \cdot w_j+1)

Haben wir aber nun wirklich das Optimum erreicht? Könnte es nicht besser sein einen Teil y (0 < y < 1) eines bereits eingepackten Gegenstand e (0 \le e \le j) wieder auszupacken und somit Platz zu schaffen für einen Teil z eines Gegenstandes r (e < r \le n)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 W so:

W'=(w_1+w_2+...+w_e+...+w_j+t\cdot w_j+1)-(1-y)\cdot w_e+z\cdot w_r

Dadurch das das Gewicht des z-ten Teiles von r genau dem Restgewicht e entspricht gilt

z\cdot g_r=(1-y)\cdot g_e.

Nun können wir diese Formel nach z umstellen und in unser W' einsetzen, außerdem erweitern wir (1-y)\cdot w_e mit g_e und bekommen somit diese Formel heraus.

W'=W+\frac{(1-y)\cdot g_e\cdot w_e}{g_e}+\frac{(1-y)\cdot g_\cdot w_r}{g_r}

Aufbau

Bestandteile:

eine sich verbrauchende Kandidatenliste
eine sich aufbauende Resultatenliste
Funktionen
- loesung?, die kontrolliert, 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 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 vorsortiert.

(define delete
  (lambda (item ls)
    (cond
      ((null? ls) '())
      ((eqv? (car ls) item) (cdr ls))
      (else
       (cons (car ls) (delete item (cdr ls)))))))

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

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

<eval id="4bd45ddfec40a">(geldwechsel 1293)</eval>

Java

import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.util.*;

 public class Main {
    public static int intRead(){
     int temp =0;
     BufferedReader eingabe = new BufferedReader( new InputStreamReader(System.in));
     try{
      temp = Integer.parseInt(eingabe.readLine());
     }
     catch(IOException e){
      System.out.println("Fehler");
     }
  return temp;
 }

    public static void main(String[] args) throws IOException {

    /*Erstellen des ArrayList, dabei ist zu beachten "<Integer>" explizit zu wählen, sonst werden die Zahlen 
     * codiert ausgegeben.*/
    ArrayList<Integer>KanditatenListe=new ArrayList<Integer>();
    ArrayList<Integer>ResultatenListe= new ArrayList<Integer>();
    int Kapazität=0;
    int a=0;
    int size=0;

    System.out.print("Bitte Kapazität eingeben: ");
    Kapazität=intRead();
    System.out.print("Bitte Größe der KanditatenListe eingeben: ");
    size=intRead();
    for(int i=0;i<size;i++){
    System.out.print("Bitte KanditatenListe eingeben: ");
    a=intRead();
    KanditatenListe.add(a);    
    }


    /*Kernstück des Greedy-Algorithmus*/
//===============================================================================================================
    for(int index=0;index<size;index++){
    /*Diese Zuweisung ist notwendig, da kein direkter Vergleich zwischen ArrayList und Integer möglich ist.
     *(zumindest fiel mir keiner ein;))*/
         a=KanditatenListe.get(index);
         while(a<=Kapazität){
          Kapazität=Kapazität-KanditatenListe.get(index);
          ResultatenListe.add(KanditatenListe.get(index));       
         }
    }

        /*Prüfung ob mögliche Lösung richtig ist.*/
        if(Kapazität==0){
        /*Ausgabe des ArrayList auf der Konsole*/
        System.out.print("{");
         for(int i=0;i<ResultatenListe.size();i++){
          System.out.print(ResultatenListe.get(i)+",");
         }
        System.out.println("}");
        System.out.println("Anzahl: "+ResultatenListe.size());
        }else{
          System.out.println("!!!Kein Lösung gefunden!!!");
          System.out.println("Rest: "+Kapazität);
         }
//===============================================================================================================
     }
 }

Verschiedene Greedy-Algorithmen

Allgemeines zur Graphentheorie

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

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

Engelsrose_200px-Prim_Algorithm_0.svg.png

1. Dies ist der Ausgangsgraph.

Engelsrose_200px-Kruskal_Algorithm_1.svg.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 T festgelegt.

Engelsrose_200px-Kruskal_Algorithm_2.svg.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 T keinen Kreis bildet.

Engelsrose_200px-Kruskal_Algorithm_3.svg.png

4. Als nächstes wird die Kante DF mit der Länge 6 zum Startgraphen T hinzugefügt. Auch diese Kante bildet keinen Kreis mit T.

Engelsrose_200px-Kruskal_Algorithm_4.svg.png

5. Nun werden die Kanten AB und CE mit jeweils der Länge 7 ausgewählt, weil sie die kürzesten Kanten von den noch übrigen besitzen und keinen Kreis mit den anderen ausgewählten Kanten bilden.

Engelsrose_200px-Kruskal_Algorithm_5.svg.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 T hinzugefügt werden können.

Engelsrose_200px-Kruskal_Algorithm_6.svg.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. Die grün markierten Kanten bilden nun den minimalen Spannbaum.

Mathematische Ausgedrückt arbeitet der Kruskal-Algorithmus mit \mathcal{O}\left(a \cdot\log {n}\right), 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 a \le n , so gilt \mathcal{O}(n \cdot \log {n} ). Bei höherer Dichte der Kanten, das heißt a \le \frac{n}{2} \cdot(n-1), ergibt sich \mathcal{O}(n^2 \cdot \log {n}) .

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 \mathcal{O}\left(n^2\right).

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