Greedy-Algortihmen

Das Prinzip eines Greedy-Algorithmus (gieriger Algorithmus) ist es, in jedem Teilschritt so viel wie möglich zu erreichen.

Eine Anwendung des Greedy-Algorithmus im täglichen Leben ist die z.B. die Herausgabe von Wechselgeld.
Greedy: Nimm jeweils immer die größte Münze unter dem Zielwert und ziehe sie von diesem ab. Verfahre derart bis Zielwert gleich null.

Beispiel:	Rückgabe von 79 Cent
	79 = 50 + 20 + 5 + 2 + 2

Bei diesem Beispiel berechnet der Greedy-Algorithmus immer die optimale Geldrückgabe. Die muss allerdings nicht immer gelten. Greedy-Algorithmen berechnen jeweils ein lokales Optimum in jedem Schritt und können daher eventuell ein globales Optimum verpassen.

Beispiel:	Zielwert ist 15. Es stehen Münzen mit den Werten 1, 5 und 11 zu Verfügung.
	15 = 5 + 5 + 5 ist globales Optimum
	15 = 11 + 1 + 1 + 1 + 1 mit Greedy kein globales Optimum

Dijkstras Algorithmus - Zum Finden kürzester Wege

Der Dijkstra-Algorithmus kann als eine auf dem Greedy-Prinzip basierende Weiterentwicklung der Breitensuchen für gewichtete Kanten aufgefasst werden. Allerdings funktioniert diese Weiterentwicklung nur für nichtnegative Gewichte.

Verfahren
Pro Knoten wird der Distanzwert D zum Startknoten in einer Prioritätswarteschlange Q gespeichert. Zu Beginn ist für den Startknoten 0 und für alle anderen Knoten unendlich ∞ eingetragen.

Schleifendurchlauf
Der erste Knoten k₁ wird aus Q genommen. Der entgültige Distanzwert von k₁ ist das aktuelle D.
Nun wird Q verändert. Bei allen Knoten k_i, die direkte Nachbarn von k₁ sind, wird nun überprüft, ob das aktuelle D größer ist als D(k₁) + das Gewicht der Kante k₁k_i. Also wenn D(k_i) > (D(k₁) + k₁k_i), dann D(k_i) = D(k₁) + k₁k_i.

Beispiel

Q = 〈(s:0), (u:∞), (v:∞), (x:∞), (y:∞)〉
Q = 〈(x:5), (u:10), (v:∞), (y:∞)〉
Q = 〈(y:7), (u:8), (v:∞)〉
Q = 〈(u:8), (v:13)〉
Q = 〈(v:9)〉
Q = 〈〉

D(s) = 0
D(x) = 5
D(y) = 7
D(u) = 8
D(v) = 9

Beispiel entnommen aus Saake, Sattler: "Algorithmen & Datenstrukturen"

Algorithmus von Prim - Zum Finden des kleinsten aufspannenden Baums

Verfahren
Wähle einen beliebigen Knoten als Startgraph T.
Solange T noch nicht alle Knoten enthält, suche eine Kante minimalen Gewichts, die einen Knoten, der nicht in T ist, mit T verbindet und füge diese Kante und den damit verbundenen Knoten zu T hinzu.

Animation für Prim

Algorithmus von Kruskal - Zum Finden des kleinsten aufspannenden Baums

Die Grundidee ist, die Kanten in der Reihenfolge aufsteigender Kantengewichte zu durchlaufen und jede Kante zu wählen, die mit allen zuvor gewählten Kanten keinen Kreis schließt.

Verfahren
Die Menge der Kanten werden sortiert in einer Liste L gespeichert.
Wähle die erste Kante in L als Startgraph T und lösche sie aus der Liste.
Solange T noch nicht alle Knoten enthält, gehe L der Reihe nach durch. Füge die erste Kante in T ein, die keinen Kreis mit den den Kanten, die bereits in T liegen, bilden. Die gewählte Kante und die Kanten, die einen Kreis bilden, können aus L gelöscht werden.

Animation für Kruskal