Zu Beginn der Veranstaltung:
Teile-und-Herrsche Paradigma
- Teile das Problem in kleinere Unterprobleme
- Beherrsche die Teilprobleme rekursiv.
- Kombiniere die Ergebnisse zu einer Gesamtlösung
Beispiele Merge-Sort, Quick-Sort, Kabasutra-Multiplikation etc.
Konstruiere eine Lösung nach und nach (iterativly) mittels "kurzsichtiger" Entscheidungen und "hoffe" dabei, dass die Gesamtlösung (optimal) funktioniert.
Es muss allerdings noch mittels eines (mathematischen) Beweises gezeigt werden, dass die Lösungen immer optimal sind. Sonst kann man nicht darauf vertrauen, dass der Algorithmus immer die optimale Lösung liefert.
Warnung: Die meisten Greedy-Algorithmen sind meist nicht korrekt!
Beispiel für einen korrekten Greedy-Algorithms:
Planen (der Priorität) (Schedule) von Aufgaben, um spezielle Zielsetzungen (objectives) zu optimieren.
Beispiel:
Die Reihenfolge, nach der gewichtete Aufgaben ausgeführt werden, soll geplant werden. Dabei soll die "Summe der gewichteten Abschlusszeiten" minimiert werden.
Wieviele mögliche Reihenfolgen gibt es für $n$-Aufgaben?
Bei $n$-Aufgaben gibt es $n! = n\cdot (n-1) \dots 2 \cdot 1$ mögliche Reihenfolgen.
Die Abschlusszeit (completion time) $C_j(\sigma)$ einer Aufgabe $j$ für eine Planung $\sigma$ ist die Zeitspanne der vorher laufenden Aufgaben plus der Zeitspanne der Aufgabe selbst.
Gegeben sind drei Aufgaben $1,2$ und $3$ mit den Zeitspannen $l_1=1$, $l_2=2$ und $l_3=3$. Die Aufgaben sollen in folgender Reihenfolge ausgeführt werden: zuerst Aufgabe $1$, dann $2$ und zum Schluss $3$ . Wie lauten die Abschlusszeiten für die drei Aufgaben?
Mit den drei Aufgaben von oben und den Gewichten $w_1=3$, $w_2=2$ und $w_3=1$, wie lautet die Summe der gewichteten Abschlusszeiten?
Input: Eine Menge von Aufgaben mit positiven Zeitspannen $l_1, l_2 \dots l_n$ und positiven Gewichten $w_1, w_2 \dots w_n$
Output: Eine Sequenz (Reihenfolge) von Aufgaben, die die der Summe der gewichteten Abschlusszeiten $\left(\sum_{j=1}^n w_j C_j(\sigma)\right)$ minimiert.
Gesucht ist also die Planung $\sigma$, die die Summe der gewichteten Abschlusszeiten minimiert:
$$ \text{arg}\min_\sigma J_{\mathcal A}(\sigma) = \text{arg}\min_\sigma \sum_{j=1}^n w_j C_j(\sigma) $$Wenn alle Aufgaben gleiche Zeitspannen haben, sollen wir Aufgaben mit kleineren oder größeren Gewichten zuerst einplanen?
Wenn alle Aufgaben gleiche Gewichte haben, sollen wir Aufgaben mit kürzeren oder längeren Zeitspannen zuerst einplanen?
Welchen Wert für die Summe der gewichteten Abschlusszeiten gibt es für
die Planungen von GreedyDiff
($w_j - l_j$) und GreedyRation
($w_j / l_j$) in folgendem Beispiel?
Aufgabe 1 | Aufgabe 2 | |
---|---|---|
Zeitspanne | $l_1=5$ | $l_2=2$ |
Gewicht | $w_1=3$ | $w_2=1$ |
GreedyDiff
($w_j - l_j$):
Daher wird Aufgabe 2 zuerst geplant. $$ \sum_{j=1}^n w_j C_j(\sigma) = 1*2+7*3=23 $$
GreedyRation
($w_j/l_j$):
Daher wird Aufgabe 1 zuerst geplant. $$ \sum_{j=1}^n w_j C_j(\sigma) = 3*5 + 7*1 = 22 $$
Schlussfolgerung: GreedyDiff
liefert für diesen Fall keine optimale Lösung.
Aber offen, ob GreedyRatio
für alle Fälle korrekte Lösungen liefert. Damit wir sicher sein können, benötigen wir einen Beweis.
GreedyRatio
¶Für jede Menge von Aufgaben mit positiven Zeitspannen $l_1, l_2 \dots l_n$ und positiven Gewichten $w_1, w_2 \dots w_n$ liefert GreedyRatio
immer eine Planung mit einer minimaler
Summe der gewichteten Abschlusszeiten.
Beweis basierenden auf Exchange Arguments. Dies ist neben Induktion eine gängige Beweistechnik für Greedy Algorithmen.
Die Aufgaben seien indexiert in nicht-aufsteigender Ordnung nach dem Gewicht-Zeitspannen Verhältnis (weigth-length ratio), d.h.: $$ \frac{w_1}{l_1} \geq \frac{w_2}{l_2} \geq \dots \geq \frac{w_n}{l_n} $$
Es gibt (erstmal) keine gleichen Verhältnisse, d.h. für alle $i$ und $j$ gilt $\frac{w_i}{l_i} \neq \frac{w_j}{l_j} $
GreedyRatio
produziert Schedule $\sigma$Vergleiche Schedule $\sigma^*$ mit Schedule $\sigma'$, der sich durch Vertauschen (Exchange) der Aufgaben $i$ und $j$ ergibt. Können wir dadurch einen Widerspruch zur Annahme finden.
Welchen Effekt hat der Austausch von $i$ und $j$ auf die Abschlusszeiten der Aufgaben von
Wie stark wirken sich die Änderungen auf die Summe der gewichteten Abschlusszeiten aus?
Somit gilt für die Differenz der Zielfunktionen:
$$ J(\sigma') = J(\sigma^*) + w_i l_j - w_j l_i $$$$ \sum_{k=1}^n w_k C_k(\sigma') = \sum_{k=1}^n w_k C_k(\sigma^*) + w_i l_j - w_j l_i $$Mit der Ordnung $$ \frac{w_i}{l_i} < \frac{w_j}{l_j} $$
ergibt sich $$ w_i l_j < w_j l_i $$
Da die Gewichte und Zeitspannen positiv sind, folgt:
$$J(\sigma') < J(\sigma^*)$$Somit kann $\sigma^*$ nicht optimal sein und der Widerspruch ist gezeigt. QED
Falls es gleiche Verhältnisse geben kann, können solche Paare einer optimalen Lösung ausgetauscht werden, ohne die Gesamtsumme zu verändern. Analog dem Beweis oben.