Gierige Methoden
"kurzsichtig handeln, langfristig gewinnen"
Autor(en): Andreas Frommer - Februar 2008
Kapitelübersicht
Anhand der bekannten Sudoku-Rätsel werden die wichtigsten Elemente einer gierigen Strategie erfahren.
Auch für die Wechselgeldaufgabe entwickelt der Nutzer selbständig eine gierige Strategie. Dabei wird auch klar, dass gierige Strategien nicht immer zum globalen Optimum führen.
Aufgrund der bisherigen Kapitel wird jetzt das Prinzip der gierigen Strategien allgemein formuliert. Dabei werden die Eigenschaften der gierigen Wahl und der optimalen Teilstruktur besonders herausgestellt.
Als letzte Anwendung für eine gierige Strategie wird die Erstellung von Huffman-Codes behandelt. Der Nutzer kann eigene und vorgegebene Texte selbst codieren. Ein Korrektheitsbeweis für den Huffman-Algorithmus, basierend auf den zuvor untersuchten Eigenschaften der gierigen Wahl und der optimalen Teilstruktur, wird entwickelt.
Arbeitsblatt
Aufgabe 1
a) Wir betrachten einen Münzsatz mit 5 Münzen mit den Werten
w(1) = 16, w(2) = 8, w(3) = 4, w(4) = 2, w(5) = 1.
Zeige, dass die gierige Strategie für das Wechselgeldproblem hier stets eine minimale Zahl von Münzen ergibt.
b) Verallgemeinere die Untersuchung von a) für den Fall, dass n Münzen mit den Werten
vorliegen. Dabei ist 
eine ganze Zahl
.
Aufgabe 2
Man kann jeden Bruch 
mit 
als sog. ägyptischen Bruch darstellen, d.h.
Dabei sind die Nenner 
paarweise verschiedene
natürliche Zahlen. Die Anzahl 
der Glieder hängt von 
und 
ab.
a) Beschreibe einen auf einer gierigen Strategie beruhenden Algorithmus, welcher für gegebenes und die Nenner in der Darstellung als ägyptischer Bruch bestimmt.
b) Wie lauten hier die Eigenschaften der gierigen Wahl und der optimalen Teilstruktur?
Aufgabe 3
Auf einer sehr langen Autofahrt (z.B. von Wuppertal nach Wladiwostok) soll möglichst selten zum Tanken angehalten werden. Die Tankstellen entlang der Strecke sind mit T(i) durchnummeriert. Folgendes ist bekannt:
- Das Auto besitzt den konstanten Benzinverbrauch v.
- Tankstelle T(i) befindet sich an Streckenkilometer d(i)..
- Der Tank besitzt einen Inhalt I.
a) Beschreibe eine gierige Strategie zur Lösung dieser Aufgabe.
b) Wie lauten hier die Eigenschaften der gierigen Wahl und der optimalen Teilstruktur?
Aufgabe 4
a) Führe alle Schritte des Huffman-Algorithmus für den nachstehenden Zeichensatz mit den angegebenen Häufigkeiten aus:
|
|
Zeichen z
|
a
|
i
|
o
|
l
|
k
|
n
|
t
|
|
|
|
h(z)
|
11
|
6
|
5
|
9
|
3
|
4
|
4
|
|
b) Gib mit dem in a) berechneten Codierungsbaum die Codierungen für die Wörter
"koala", "aioli" und "koalition" an.
c) Wie groß ist die gewichtete externe Pfadlänge des Codierungsbaums aus a)?
Aufgabe 5
Beim Nachweis der Eigenschaft der gierigen Wahl auf der Seite Huffman-Codes 4 hatten wir einen optimalen Codierungsbaum so umgebaut, dass die Zeichen z1 und z2 Geschwister in maximaler Tiefe wurden. Wenn sie das nicht schon vor dem Umbau waren, müssen einige Zeichen mit genau den gleichen Häufigkeiten wie z1 und z2 vorkommen.
Welche (Blätter in dem angegebenen Codierungsbaum) sind das?
Drucken
Inhalt
Das Prinzip der gierigen Strategien wird zunächst spielerisch am Beispiel von Sudokus erfahrbar gemacht.
Über weitere Beispiele wird erarbeitet, unter welchen Voraussetzungen gierige Strategien korrekt sind.
Die Eigenschaften der gierigen Wahl und der optimalen Teilstruktur werden herausgestellt.
Das umfangreichere Beispiel der Huffman-Codes zeigt zum Abschluss eine praktisch relevante Anwendung des Prinzips der gierigen Strategien.
Glossar
statt 
