AuK/Greedy-Algorithmen SS10

Wiki-Quelltext dieser Seite.

Für diese Seite ist es zu empfehlen sich vorher mit der dynamischen Programmierung auseinanderzusetzten.


'''Autoren:'''

<p> Claudia Scheffler  ([mailto:siclsche@stud.hs-zigr.de siclsche@stud.hs-zigr.de])</p>
<p> Dirk Klahre        ([mailto:sidiklah@stud.hs-zigr.de sidiklah@stud.hs-zigr.de])</p>


==Einführung==

In dem Themenkomplex Algorithmen und Komplexität wollen wir uns jetzt mit dem Thema Greedy-Algorithmen beschäftigen. Greedy steht hier für gierig bzw. gefräßig. Der Greedy-Algorithmus arbeitet nach der Methode:

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

Die Entscheidung welches nun der beste Happen ist, wird vom Algorithmus rechnerisch getroffen und nicht etwa erraten. Diese Berrechnung geschieht auf der Basis lokaler Information, das heißt es erfolgt kein Rückgriff auf Werte, die für frühere Berechnungen benötigt wurden. Dementsprechend wird auch keine Tabelle, die alle Teilproblemlösungen bereithält, mitgeführt wie es in der [http://www.michael-hielscher.de/wiki/index.php?title=AuK/Dynamisches_Programmieren_SS10&action=edit dynamischen Programmierung] der Fall ist. Ein weiteres Merkmal der gierigen Strategie ist, das eine einmal getroffene Entscheidung nicht wieder zurückgenommen wird. Aus diesem Grund gibt es kein Zurücknehmen und Erproben von Alternativen der einzelnen Fälle, wie es beim [http://www.michael-hielscher.de/wiki/index.php/AuK/Systematische_Suche_SS10 systematische Probieren] mit Backtracking der Fall ist. Damit der Greedy-Algoritmus nun in jedem Schritt den besten "Happen" herraussuchen kann, benötigt er eine vorsortierte Angebots- oder Kanidatenliste. Um die Sortierung beizubehalten, wird jedes neue Element gleich an die richtige Stelle einsortiert. 
 
Wenn die gierige Strategie anwendbar ist führt sie in der Regel zu recht guten, wenn auch nicht immer zu optimalen Lösungen. Einer der Hauptvorteile des Greedy-Algorithmus liegt in der Tatsache, dass der zusätzliche organisatorische Aufwand zur Durchführung des Verfahrens meist relativ gering ist. Die Kombination von geringem zusätzlichem Aufwand und im allgemeinen guten bis sehr guten Erfolg ist ein wesentliches Merkmal dieser Strategie. Die gierige Strategie ist kein graziles aber dennoch oft ein höchst wirkungsvolles und sehr "preiswertes" Instrument des Problemlösens.

==Bruchteilrucksack==

Bei diesem Problem geht es ähnlich wie bei dem [http://www.michael-hielscher.de/wiki/index.php/AuK/Systematische_Suche_SS10#Rucksackproblem 0/1 Rucksackproblem] darum, eine bestimmte Kapazität mit einer Anzahl an Teilmengen zu erreichen.
Der Vorteil bei dieser Herangehensweise ist die Möglichkeit nur einen gewissen Teil einzupacken. Somit wird sichergestellt das wir die zur Verfügung stehende Kapazität voll ausschöpfen.
In der Nachfolgenden Erläuterung gehen wir stets von einer homogenen Verteilung aus.Im Klartext heißt das, wenn ich ein Gegenstand zu 20% auspackte hat dieser auch einen Wertverlust von 20%.
Das dies in der realen Welt eher selten anzutreffen ist, versteht sich von selbst. Es hilft uns aber das Problem besser zu verstehen.
Nehmen wir also an, wir haben einen Rucksack mit einer gewissen Kapazität '''K''' und eine bestimmte Anzahl an Gegenständen, diese wiederum einen Wert '''w''' und ein Gewicht '''g'''.
Nun sortieren wir diese Gegenstände absteigend nach ihrem Wert. So bekommen wir diese Form heraus:
<math>\frac{w_1}{g_1}\leq\frac{w_2}{g_2}\leq.......\leq\frac{w_n}{g_n}</math>  

<popup name="Beispiel">
  Text der aufgeklappt und zugeklappt werden kann. 
 </popup>

==Aufbau==
==Kürzeste Wege in den Graphen==