Gierige Methoden | MathePrisma

Gierige Methoden

Sudokus und Gier

Sudokus

Wechselgeld

Allgemein

Codes

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

$w(1) = b^{n-1}, w(2) = b^{n-2}, ..., w(n-1) = b^{1}, w(n) = b^{0}$

vorliegen. Dabei ist $b$ eine ganze Zahl $\geq 2$ .

Aufgabe 2

Man kann jeden Bruch $\displaystyle \frac{p}{q}$ mit $1\leq p \leq q$ als sog. ägyptischen Bruch darstellen, d.h.

$\frac{p}{q} = \frac{1}{q_1} + \frac{1}{q_2} + ... + \frac{1}{q_n}.$

Dabei sind die Nenner $q_i$ paarweise verschiedene natürliche Zahlen. Die Anzahl $n$ der Glieder hängt von $p$ und $q$ ab.
a) Beschreibe einen auf einer gierigen Strategie beruhenden Algorithmus, welcher für gegebenes $p$ und $q$ die Nenner $q_i$ 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

Manche Aufgabenstellungen, wie z.B. unsere Sudokus, kann man mit der folgenden Strategie lösen:

Voraussetzung:

die Lösung ergibt sich als Folge von Entscheidungen

Strategie:

die Entscheidungsfolge wird schrittweise aufgebaut
in jedem Schritt weiß man, welches die richtige Entscheidung ist und trifft dann diese

Der Fragebogen der vorangegangenen Seite wurde dann wohl so beantwortet.

verschiebe die grünen Felder in die Mitte

Für Sudokus wird hier noch genauer ausgeführt, wie man erkennen kann, dass die Entscheidung für eine Zahl z für Feld F richtig ist.

Definition

Eine Strategie, bei der man eine Lösung dadurch erhält, dass man

schrittweise vorgeht und
in jedem Schritt eine Entscheidung trifft (die richtige), die später nie mehr verworfen wird,

nennt man gierig (engl. greedy).

gierig geht nicht immer

Nicht jedes Problem, das man mit einer Folge von Entscheidungen lösen kann, kann mit einer gierigen Strategie gelöst werden. Es kann nämlich sein, dass man erst viele Schritte später erkennt, dass eine früher getroffene Entscheidung falsch war.

Unsere Sudokus (so wie fast alle aus den Rätselseiten der Zeitschriften) lassen sich stets mit einer gierigen Strategie mit den beschriebenen Kriterien lösen. Man muss dazu natürlich in jedem Schritt das richtige Feld finden.

Es gibt aber auch diabolische Sudokus, deren eindeutige Lösung man prinizipiell nicht mit einer gierigen Strategie finden kann.