Greedy-Algorithmen SS09
Inhaltsverzeichnis |
Dev Status
Einführung
Greedy [eng. gefräßig] - eine gefräßige Strategie für Algorithmen. Sie funktioniert nach der Methode:
"Nimm immer den besten Happen, den du kriegen kannst."
Das geschieht durch eine rechnerische Entscheidung. Die Berechnung erfolgt auf der Basis lokaler Information, also ohne Rückgriff auf vorher ermittelte Werte.
Bruchteilrucksack-Problem
Greedy
Aufbau
(define greedy
(lambda (vorgabewert) ; z.B.: Kapazitaet der Rucksacks
(let
((kandidatenliste '(......))
(loesung? (lambda (ls) ... ))
(okay? (lambda (ls) ... ))
(naechster (lambda (ls) ... ))
(modify+ (lambda (x ls) ... ))
(modify- (lambda (x ls) ... ))
(ziel (lambda (ls) ... ))
(letrec
((helfer
(lambda (kandidaten resultat)
(cond
((loesung? resultat)(ziel resultat))
((and (null? kandidaten)(not (loesung? resultat)))
(error 'greedy "Es gibt keine Loesung."))
(else
(let* ((neuer-kandidat (naechster kandidaten))
(neues-resultat (cons neuer-kandidat resultat)))
(if (okay? neues-resultat)
(helfer (modify+ neuer-kandidat kandidaten) neues-resultat)
(helfer (modify- neuer-kandidat kandidaten) resultat))))))))
(helfer kandidatenliste '())))))Anwendbarkeit
Greedy
Beispiel (Geldwechsel)
Einem Kunden wird Wechselgeld herausgegeben, wobei möglichst wenige Münzen verwendet werden sollen.
- Zur Verfügung haben wir alle Euro-Münzen: 1, 2, 5, 10, 20, 50, 100 (1 Euro), 200 (2 Euro).
- Die Münzen werden mit absteigendem Cent-Wert vorsortiert.
- Die Prozedur geldwechsel ergibt Resultatliste und Anzahl der Münzen.
Die Prozedur wird benutzt um 12,93 Euro (1293 Euro-Cent) herauszugeben. <eval> (geldwechsel 1293) </eval>
Verschiedene Greedy-Algorithmen
Dijkstra
[[Bild:Dijksta_Anim.gif|thumb|284px|Dijkstras Algorithmus(Quelle: Wikipedia)]]
Edsger W. Dijkstra auf Wikipedia
Kürzeste Wege in Graphen
Die Suche nach der kürzesten Rundreise, die n gegebene Städte genau einmal besucht, gehört zu den schwierigsten Problemen, für die bisher nur Lösungsverfahren mit exponentieller Rechenzeit bekannt sind (siehe: Verzweigen und beschränken: Rundreiseproblem).
Das folgende Problem klingt noch schwieriger. Gesucht ist der kürzeste Weg von Stadt A zu Stadt B, wobei für die n betrachteten Städte eine Entfernungsmatrix gegeben ist. Man muss alle Zwischenstädtefolgen (Wege) betrachten, auch solche, die nicht alle Städte enthalten.
Dijkstra fand 1959 einen Algorithmus zur Lösung des Kürzeste-Wege-Problems dessen Rechenzeit in \mathcal{O}(n^2) liegt. Ein nach Floyd und Warschall benanntes Verfahren löst eine etwas weiter gehende fragestellung in \mathcal{O}(n^3). Dabei werden die kürzesten Wege für alle Städtpaare bestimmt.
Das Problem ist, mathematisch gesehen, eine Sache der Graphentheorie.
Unter einem endlichen Graph G versteht man ein Paar (V, E), wobei V eine endliche Knotenmenge (Knoten = vertex) und E eine endliche Menge von Kanten (edges) bezeichnet. Eine Kante verbindet genau zwei Knoten. Es ist nicht verlangt, dass alle Knotenpaare durch je eine Kante verbunden sind. Es kann Mehrfachkanten geben.
Dijkstras Algorithmus
Dieses Algorithmus wurde in 1959 von Dijkstra gefunden.
Kruskal
Übung
1. Geldwechsel (Euro)
Berechnen Sie schriftlich, wieviele Münzen heraugegeben werden müssen, um den Betrag 15,61 Euro auszuzahlen.
Überprüfen Sie das Ergebnis mit hilfe von der Prozedur geldwechsel.
2. Geldwechsel (US Dollar)
Berechnen Sie schriftlich, wieviele Münzen heraugegeben werden müssen, um den Betrag 15,61 US Dollar auszuzahlen.
Beachten Sie darauf, dass US Cents folgende Münzen haben:
Überprüfen Sie das Ergebnis mit hilfe von der Prozedur geldwechsel.
Hinweis: die Kandidatenliste soll im Quellcode angepasst werden.
3. Geldwechsel (Polski Złoty)
Berechnen Sie schriftlich, wieviele Münzen heraugegeben werden müssen, um den Betrag 15,61 PLN auszuzahlen.
Beachten Sie darauf, dass Polski Złoty folgende Münzen hat:
Überprüfen Sie das Ergebnis mit hilfe von der Prozedur geldwechsel.
Hinweis: die Kandidatenliste soll im Quellcode angepasst werden.