Greedy-Algorithmen SS09

Dev Status

Einführung

Greedy (engl. gefräßig) - eine gefräßige Strategie für Algorithmen. Sie funktioniert nach der Methode:

"Nimm immer den besten Happen, den du kriegen kannst."

Das geschieht durch eine rechnerische Entscheidung. Die Berechnung erfolgt auf der Basis lokaler Information, also ohne Rückgriff auf vorher ermittelte Werte. Es wird also keine Tabelle, die alle Teilproblemlösungen bereithält, mitgeführt, wie dam beim dynamisches Programmieren der Fall ist.

Beim Greedy-Algorithmen gibt es kein Zurücknehmen und Erproben von Alternativen, wie bei systematischen Probieren mit Backtracking. Eine einmal getroffene Entscheidung wird nicht revidiert.

Der Aufwand eines Greedy-Verfahrens ist sicher nicht exponentiell. Allerdings ist die Anwendbarkeit dieses Superverfahrens sehr in Frage gestellt.

Greedy-Algorithmen brauchen um die beste Auswahl zu treffen eine vorsortierte Kandidatenliste. Die neu aufnehmende Elemente werden immer gleich an der richtigen Stelle eingefügt, so dass die Sortierung erhalten bleibt.

Der zugehörige Datentyp ist eine Prioritätswarteschlange (priority queue). Sie kann mit einem heap sehr effizient implementiert werden.

Bruchteilrucksack-Problem

&^^@&*(#%&&#*@Q

Aufbau-Template

(define greedy
 (lambda (vorgabewert) ; z.B.: Kapazitaet der Rucksacks
  (let
      ((kandidatenliste '(......))
       (loesung? (lambda (ls) ... ))
       (okay? (lambda (ls) ... ))
       (naechster (lambda (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 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 '())))))

Anwendbarkeit

Oft steht eine begrenzte Kapazität zur Verfügung, welche nicht die gesamte Nachfrage befriedigen kann. Man denke z. B. an einen Lkw, der viele verschiedene Güter – mit einem bestimmten Gewinn – transportieren soll, aber wegen der begrenzten Lademenge nicht alle Güter aufnehmen kann. Der Besitzer des Lkws wird die Ladung so wählen wollen, dass der Gewinn maximal ausfällt.

Beispiel (Geldwechsel)

Einem Kunden wird Wechselgeld herausgegeben, wobei möglichst wenige Münzen verwendet werden sollen.

• Zur Verfügung haben wir alle Euro-Münzen: 1, 2, 5, 10, 20, 50, 100 (1 Euro), 200 (2 Euro).
• Die Münzen werden mit absteigendem Cent-Wert vorsortiert.
• Die Prozedur geldwechsel ergibt Resultatliste und Anzahl der Münzen.

Die Prozedur wird benutzt um 12,93 Euro (1293 Euro-Cent) herauszugeben. <eval> (geldwechsel 1293) </eval>

Verschiedene Greedy-Algorithmen

Dijkstra

Edsger W. Dijkstra auf Wikipedia

Kürzeste Wege in Graphen

Die Suche nach der kürzesten Rundreise, die n gegebene Städte genau einmal besucht, gehört zu den schwierigsten Problemen, für die bisher nur Lösungsverfahren mit exponentieller Rechenzeit bekannt sind (siehe: Verzweigen und beschränken: Rundreiseproblem).

Das folgende Problem klingt noch schwieriger. Gesucht ist der kürzeste Weg von Stadt A zu Stadt B, wobei für die n betrachteten Städte eine Entfernungsmatrix gegeben ist. Man muss alle Zwischenstädtefolgen (Wege) betrachten, auch solche, die nicht alle Städte enthalten.

'''Bild 6.2:''' Bewerteter ungerichteter Graph mit 7 Knoten

Dijkstra fand 1959 einen Algorithmus zur Lösung des Kürzeste-Wege-Problems dessen Rechenzeit in \mathcal{O}(n^2) liegt. Ein nach Floyd und Warshall benanntes Verfahren löst eine etwas weiter gehende fragestellung in \mathcal{O}(n^3). Dabei werden die kürzesten Wege für alle Städtpaare bestimmt.

Das Problem ist, mathematisch gesehen, eine Sache der Graphentheorie.

Unter einem endlichen Graph G versteht man ein Paar (V, E), wobei V eine endliche Knotenmenge (Knoten = vertex) und E eine endliche Menge von Kanten (edges) bezeichnet. Eine Kante verbindet genau zwei Knoten. Es ist nicht verlangt, dass alle Knotenpaare durch je eine Kante verbunden sind. Es kann Mehrfachkanten geben.

Zur Speicherung von Graphen verwendet man Matrizen. Eine gängige Form sind sog. Adjazenmatrizen, die für jedes Knotenpaar vermerken, ob die durch die aktuelle Zeile bzw. Spalte bestimmten Knoten durch eine Kante verbunden sind.

Handelt es sich um einen gewichteten Graph, dessen Kanten z.B. mit je einer Zahl für eine bestimmte Länge, Masse oder einen Euro-Betrag markiert sind, werden diese Gewichte in der Adjazenmatrix angegeben. Nicht vorhandene Kanten werden durch einen vereinbarten Wert, meist 0, x oder eine sehr große Zahl, beschrieben.

Wir sprechen von einem gerichteten Graph (engl. directed graph, Digraph), wenn die Kanten einseitig gerichtete Pfeile sind.

Dijkstras Algorithmus

Gegeben sei der Bild in Bild 6.2 modellierter Stadplan mit 7 markanten Punkten A, B, C, D, E, F und G.
Gesucht ist die kürzeste Strecke von A (Airport) zum Stadthotel D.

Die Grundidee des Algorithmus ist, ab einem Startknoten die kürzest möglichen Wege weiter zu verfolgen und längere Wege beim Updaten auszuschließen. Er besteht aus diesen Schritten:

1. Initialisiere eine Menge von Startknoten mit einem Element (A).
2. Weise allen Knoten die beiden Eigenschaften "Distanz" und "Vorgänger" zu. Initialisiere die Distanz im Startknoten mit 0 und in allen anderen Knoten mit ∞.
3. Solange es noch unbesuchte Knoten gibt wähle darunter denjenigen mit minimaler Distanz aus und
   1. Speichere, dass dieser Knoten schon besucht wurde
   2. Berechne für alle noch unbesuchten Nachbarknoten die Summe des jeweiligen Kantengewichtes und der Distanz im aktuellen Knoten
   3. Ist dieser Wert für einen Knoten kleiner als die dort gespeicherte Distanz, aktualisiere sie und setze den aktuellen Knoten als Vorgänger.
      Dieser Schritt wird auch als Update bezeichnet und ist die zentrale Idee von Dijkstra.

'''Bild 6.3:''' Bild 6.2 bearbeitet von Dijkstra-Algorithmus (von ''A'' nach ''D'')

S:={s};
Distanz(s):=0;
for all v\inV\{s} do {
    Distanz(v)=Kante(s,v);
    Vorgaenger(v)=s;
}
while z\notinS do {
    Finde v'\inV\S mit Distanz(v')=min{Distanz(v) | v\inV\S};
    S:=S\cup{v'};
    for all v\inV\S do {
        if Distanz(v')+Kante(v',v) < Distanz(v)
        then {
            Distanz(v):=Distanz(v')+Kante(v' ,v);
            Vorgaenger(v):=v'
        }
    }
}

Kruskal

Joseph Kruskal auf Wikipedia

Prim

Die folgende Scheme-Prozedur versucht die Zahlen in Primfaktoren zu zerlegen, die sich in der Kandidatenliste befinden. In der Lösung wird auch die Anzahl der Primfaktoren ausgegeben.

<eval>(prim 234)</eval>

Übung

Geldwechsel (Euro)

Berechnen Sie schriftlich, wieviele Münzen heraugegeben werden müssen, um den Betrag 15,61 Euro auszuzahlen.

Überprüfen Sie das Ergebnis mit hilfe von der Prozedur geldwechsel.

Geldwechsel (US Dollar)

Berechnen Sie schriftlich, wieviele Münzen heraugegeben werden müssen, um den Betrag 15,61 US Dollar auszuzahlen.

Beachten Sie darauf, dass US Dollars folgende Münzen haben:

Überprüfen Sie das Ergebnis mit hilfe von der Prozedur geldwechsel.

Hinweis: die Kandidatenliste soll im Quellcode angepasst werden.

Geldwechsel (Polski Złoty)

Berechnen Sie schriftlich, wieviele Münzen heraugegeben werden müssen, um den Betrag 15,61 PLN auszuzahlen.

Beachten Sie darauf, dass Polski Złoty folgende Münzen hat:

Überprüfen Sie das Ergebnis mit hilfe von der Prozedur geldwechsel.

Hinweis: die Kandidatenliste soll im Quellcode angepasst werden.

Prim-Algorithmus

Prim-Algorithmus Aufgabe

Verwenden Sie den Bsp. aus der Vorlesung, wählen Sie jetzt als den Startknoten: D.

Ermitteln Sie eine Reihenfolgenliste für alle Knoten.

Prim-Algorithmus (Scheme)

Experimentieren Sie mit dem Scheme-Code für Prim-Algorithmus.

Versuchen Sie die folgenden Zahlen in Primfaktoren zu zerlegen:

• 24
• 76
• 98
• 437
• 667

Hinweis: Denken Sie auch an Erweiterung der Kandidatenliste, wenn die Prozedur einen Fehler ausgibt.

Kommentare