AuK/Greedy-Algorithmen SS10

Wiki-Quelltext dieser Seite.

'''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"'''

Das Prinzip der gierigen Algorithmen besteht darin in jedem Teilschritt so viel wie möglich zu erreichen. 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==
==Aufbau==
==Kürzeste Wege in den Graphen==