AuK/Greedy-Algorithmen WS13-14

Wiki-Quelltext dieser Seite.

== 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 [http://programmingwiki.de/AuK/Systematische_Suche_WS13-14#Varianten 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} \]