Greedy-Algorithmen WS13-14

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2013-10-30T15:26:45+00:00. Aktuelle Version

Einführung

Entgegen anderen Programmiermethoden, wie bspw. dem Dynamischen Programmieren oder dem systematischen Probieren mit Backtracking, arbeiten Greedy-Algorithmen nach dem Motto "Nimm immer den besten Happen, den du kriegen kannst". Hierzu werden immer Entscheidungen auf Basis von lokalen (zu dieser Zeit vorliegenden) Informationen getroffen. Greedy-Algorithmen sind gefräßig und suchen sich immer die besten Stücken aus.

Auf den ersten Blick erscheint das Verfahren gut, denn der Aufwand, den man benötigt, wird wohl nicht exponentiell sein.

Die Basis eines Greedy-Algorithmus ist eine bereits vorsortierte Liste. Wird diese erweitert, werden die entsprechenden Elemente direkt an die richtige Stelle einsortiert.


Bruchteilrucksack

In Erweiterung des 0/1-Rucksackproblem können beim Bruchteilrucksack auch nur Teile eines Gegenstands eingepackt werden. Dabei gehen wir davon aus, dass ein Gegenstand, der zu 70 % eingepackt wurde, auch tatsächlich einen Wert von 70 % seines Gesamtwertes besitzt. Weiterhin legen wir fest, dass das Gewicht des i-ten Gegenstandes mit g_i und dessen Wert mit w_i bezeichnet wird. Damit der Greedy-Algorithmus arbeiten kann, werden die n Gegenstände nach ihrem spezifischen Wert, dem Quotienten aus w_i und g_i, absteigend sortiert.

\frac{w_1}{g_1} \geq \frac{w_2}{g_2} \geq \frac{w_3}{g_3} \geq \dots \geq \frac{w_n}{g_n}

Die Kapazität (das Maximalgewicht) des Bruchteilrucksacks sei als K definiert. Es leuchtet ein, dass K immer genau erreicht wird, wenn K die Summe der einzelnen Gewichte g_i ist. Wählt man K kleiner als die Summe der einzelnen g_i, so kommt der Greedy-Algorithmus zum Einsatz:

Es werden die ersten j Gegenstände in den Rucksack gesteckt. Dabei erhält man j, indem j+1 das erste Element ist, das nicht mehr vollständig in den Rucksack passt. Die (eventuell noch) vorhandene Restkapazität kann nun mit einem Teil t (mit 0 \leq t < 1) des Gewichtes des j+1-ten Gegenstands gefüllt werden.

K - \left(g_1 + g_2 + g_3 + \dots + g_j\right) = t \cdot g_{j+1}

Der Gesamtwert des auf diese Weise gefüllten Rucksacks beträgt nun:

W = w_1 + w_2 + w_3 + \dots + w_j + t \cdot w_{j+1}

Aber kann man sich wirklich sicher sein, dass der Rucksack nun tatsächlich maximal gefüllt ist? Man könnte ja auch auf die Idee kommen, dass man ein Element e (mit 1 \leq e \leq j) auswählt, das nun (statt komplett) nur zum Teil y (mit 0 < y < 1) eingepackt wird. Zum Auffüllen kommt dann ein weiteres (bisher vernachlässigtes) Element r (mit j < r \leq n) mit einem geringeren spezifischen Wert zum Einsatz, das nun zu einem Teil z (0 < z \leq 1) eingepackt wird. Dies ergibt dann den folgenden Gesamtwert

W' = w_1 + w_2 + \dots + w_e + \dots + w_j + t \cdot w_{j+1} - \left( 1 - y\right) \cdot w_e + z \cdot w_r

Das Gewicht des z-ten Teil des r-ten Elements stimmt mit dem Restgewicht \left( 1 - y\right) \cdot g_e des e-ten Elements überein.

z \cdot g_r = \left( 1 - y\right) \cdot g_e z = \frac{\left( 1 - y\right) \cdot g_e}{g_r}

Setzt man nun dieses z in die Gleichung für den Gesamtwert W' ein, erhält man:

W' = w_1 + w_2 + \dots + w_e + \dots + w_j + t \cdot w_{j+1} - \left( 1 - y\right) \cdot w_e + \frac{\left( 1 - y\right) \cdot g_e \cdot w_r}{g_r}
Umformung
W' = W - \frac{\left( 1 - y\right) \cdot g_e \cdot w_e}{g_e} + \frac{\left( 1 - y\right) \cdot g_e \cdot w_r}{g_r}

Wie oben festgelegt wurde, gilt \left( 1 - y\right) \cdot g_e > 0 und damit ergibt sich:

W' = W + \underbrace{\left( 1 - y\right) \cdot g_e}_{> 0} \cdot \underbrace{\left( \frac{w_r}{g_r} - \frac{w_e}{g_e}\right)}_{< 0}

Hier wird deutlich, dass kein Wertzuwachs erfolgt, sondern stattdessen sogar W' < W gilt. Dies zeigt als, dass der Greedy-Algorithmus das Bruchteilrucksack-Problem effizient löst.


Aufbau eines Greedy-Algorithmus

Ein Greedy-Algorithmus hat im Allgemeinen folgende Bestandteile:

  • Listen
    • Kandidatenliste
    • Resultatsliste
  • Funktionen
    • loesung? prüft, ob die ermittelte Resultatliste eine mögliche Lösung des Problems darstellt
    • okay? prüft, ob aktueller Kandidat in Resultatliste aufgenommen werden kann
    • naechster wählt nächsten Kandidaten aus
    • modify+ erweitert die Kandidatenliste
    • modify- streicht einen nicht verwendbaren Kandidaten aus der Kandidatenliste
    • ziel gibt die Resultatliste aus

Diese Bestandteile können wir mit Scheme bzw. Racket in Form einer Prozedur angeben, die allgemein gültig ist:

Diese hier geschriebene Funktion (Quelle: xxx) kann man als Template für alle Greedy-Algorithmen übernehmen. Nur im oberen Bereich müssen die Punkte (...) durch entsprechende Funktionen angepasst werden.

Eine genaue Funktionsweise der Prozedur wird anhand eines Geldwechsel-Beispiels verdeutlicht.



Beispiel: Geldwechsel

Problemstellung: Ein beliebiger Euro-Betrag soll mit so wenig wie möglichen Münzen dargestellt werden. Damit können wir unsere Kandidatenliste in Form von Cent-Beträgen absteigend sortieren: 

(200, 100, 50, 20, 10, 5, 2, 1)

Die Funktion loesung? liefert #t, wenn die Summe der ausgewählten Münzen genau den gesuchten Betrag ergibt.

In der Funktion okay? wird geprüft, ob die Summe der gewählten Münzen höchstens dem geuschen Betrag entspricht. Sobald das nicht mehr der Fall ist, wird mithilfe der Funktion modify- der gegenwärtige Kandidat aus der Liste der potentiellen Kandidaten gestrichen. Da wir hier von einer idealen Kasse ausgehen, die unendlich viele Münzen beinhaltet, lässt die Funktion modify+ die Liste der Kandidaten in diesem Fall unverändert.

Die Funktion naechster gibt immer den ersten Wert aus der Kandidatenliste zurück - ganz gleich, ob damit der Gesamtwert überschritten wird, oder nicht. Die Summe wird dann ja von okay? geprüft. Aufgrund der absteigend vorsortierten Liste können wir immer davon ausgehen, dass der höchstmögliche Kandidat geprüft wird.

Die verbleibende Funktion ziel gibt bei einem erfolgreichen Wechselvorgang die Liste der Einzelmünzen und die Anzahl der gefundenen Münzen aus.