Inhalt
Greedy Verfahren sind dadurch gekennzeichnet, dass sie in jedem Verfahrensschritt diejenige Entscheidung treffen, die in diesem Moment am Besten ist. Anhand zweier Beispiele, dem Münzwechselproblem und dem Handlungsreisenden-Problem wird gezeigt, dass dieser Ansatz nicht zwingend zu einer global optimalen Lösung führen muss und sogar zu einem beliebig schlechten Ergebnis führen kann. Die Eigenschaften, die ein Greedy Verfahren haben muss, um eine globale Lösung zu erhalten, werden diskutiert.
Als Beispiele für Probleme, bei denen ein Greedy Verfahren immer eine optimale Lösung liefert, werden das Aktivitäten Auswahl Problem und der Huffman Code behandelt. Bei dem Aktivitäten Auswahl Problem wird gezeigt, dass man mit einem Greedy Verfahren immer eine global optimale Lösung erzielen kann. Auch für das Huffman Verfahren, das bei der Komprimierung von Daten eine große Rolle spielt, wird die Korrektheit des Verfahrens bewiesen.
|