Bei der Optimierung geht es darum aus mehreren Lösungen die (in einem gewissen Sinn) "optimale" zu finden, z.B. minimale Spannbäume, das Handlungsreisendenproblem, das Rucksackproblem, etc.
Greedy-Algorithmen sind "gierige" Verfahren zur Lösung von Optimierungsaufgaben, wobei in jedem Schritt die lokal beste Lösung gewählt wird, und diese einmal getroffene Wahl nie wieder geändert wird. Diese Algorithmen führen jedoch nur in seltenen Fällen zur optimalen Lösung, wie zum Beispiel der Algorithmus von Kruskal zur Bestimmung eines minimalen Spannbaumes eines Graphen: Hat man einen (zusammenhängenden) Graphen 
gegeben, wobei jeder Kante 
ein Kantengewicht 
zugeordnet ist, so ist der minimale Spannbaum ein zusammenhängender, kreisfreier Graph, der alle Knoten miteinander verbindet, und dessen Gesamtgewicht minimal ist. Nach Kruskal sortiert man die Kanten gemäß ihrem Gewicht aufsteigend, und nimmt iterativ die nächsthöhere Kante in den Spannbaum auf, sofern dadurch kein Kreis erzeugt wird. So erhält man den minimalen Spannbaum.
Bei den Enumerationsverfahren werden alle Lösungen aufgezählt und aus diesen dann die optimale ausgewählt. Allerdings kann das Bestimmen aller Lösungen sehr lange dauern.
Man kann dieses Verfahren zum Beispiel auf das Rucksackproblem anwenden: Man hat eine Menge von 
Gegenständen 
mit Gewicht und Wert 
sowie einen Rucksack mit Fassungsvermögen 
gegeben. Nun geht es darum, die Gegenstände mit möglichst hohem Gesamtwert einzupacken, ohne die Kapazität des Rucksacks zu überschreiten.
Auch das Acht-Damen-Problem kann mittels Enumeration gelöst werden. Es geht dabei darum, acht Damen - oder allgemeiner: 
Damen - so auf einem 
-Schachbrett zu platzieren, dass sie einander nicht bedrohen. Bei der Enumeration sollte man allerdings beachten, dass in jeder Zeile und jeder Spalte genau eine Dame stehen muss, damit die Aufgabe überhaupt erfüllt werden kann. Beachtet man das nicht, so erreicht der Aufwand 
.
Bei der dynamischen Programmierung zerlegt man das Problem in Teilprobleme, die jedoch voneinander abhängig sind.
Mit ihrer Hilfe kann die Lösung des Rucksackproblems deutlich vereinfacht werden: Man betrachtet zuerst nur die ersten 
Gegenstände und merkt sich für alle möglichen Werte 
diejenigen Lösungen, die das kleinste Gewicht ergeben. In der Praxis macht man das durch einen Entscheidungsbaum: Die Verzweigungen vor der -ten Ebene entscheiden darüber, ob das -te Element aufgenommen wird oder nicht. In den Knoten wird das jeweilige 
-Paar gespeichert. Treten in einer Ebene Paare mit gleichem -Wert auf, so wird nur jene Lösung mit kleinerem Gewicht weiterverfolgt, die andere wird verworfen. Gleiches geschieht mit Paaren mit 
. In der letzten Ebene sucht man dann unter jenen Paaren mit 
dasjenige heraus, das den größten Wert besitzt, und hat somit die Lösung gefunden.
|
||
|
|
|
|
||