Inhaltsverzeichnis
Greedy-Algorithmus
Annahme: Es gibt eine Gewichtsfunktion w,
Huffman-Codes
Dieser Code hat eine mittlere Codewortlänge - bezogen auf die
Code läßt sich als Codebaum darstellen: (nach links 0, nach rechts 1)
Wenn beispielsweise die Folge
Greedy-Algorithmus generiert diesen Baum auf folgende Weise:
Der Huffman-Algorithmus konstruiert einen optimalen Codebaum .
Teilmengensystem
Der einem Teilmengensystem (E, U) und Gewichtsfunktion
Beispiel:
Austauscheigenschaft
Satz: Sei (E,U) ein Teilmengensystem. Der kanonische
Der Greedy-Algorithmus wählt dann eine Menge T
PPT-Folie
Beispiel: Auftragsplanung
Greedy Algorithmus:
PPT-Folie
|