AuK/Greedy-Algorithmen SS09
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
'''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.
<code hidden>(define delete
(lambda (item ls)
(cond
((null? ls) '())
((eqv? (car ls) item) (cdr ls))
(else
(cons (car ls) (delete item (cdr ls)))))))</code>
<code>(define geldwechsel
(lambda (restbetrag)
(let ((kandidatenliste '(200 100 50 20 10 5 2 1))
(loesung? (lambda (ls)(= restbetrag (apply + ls))))
(okay? (lambda (ls) (<= (apply + ls) restbetrag)))
(naechster car)
(modify+ (lambda (x ls) ls))
(modify- (lambda (x ls) (delete x ls)))
(ziel (lambda (ls) (cons (reverse ls) (list (length 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 '())))))</code>
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<br />(Quelle: [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Wikipedia])]]
[http://de.wikipedia.org/wiki/Edsger_Wybe_Dijkstra 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|Verzweigen und beschränken: Rundreiseproblem]]).
Die 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.
[[Bild:Kropki.png|thumb|250px|left|Bewerteter ungerichteter Graph mit 7 Knoten]]
Dijkstra fand 1959 einen Algorithmus zur Lösung des Kürzeste-Wege-Problems dessen Rechenzeit in <math>\mathcal{O}(n^2)</math> liegt. Ein nach Floyd und Warschall benanntes Verfahren löst eine etwas weiter gehende fragestellung in <math>\mathcal{O}(n^3)</math>. Dabei werden die kürzesten Wege für ''alle'' Städtpaare bestimmt.
====Dijkstras Algorithmus====
Dieses Algorithmus wurde in 1959 von Dijkstra gefunden.
===Kruskal===
[http://en.wikipedia.org/wiki/Joseph_Kruskal Joseph Kruskal auf Wikipedia]
==Übung==
===1. Geldwechsel (Euro)===
Berechnen Sie schriftlich, wieviele Münzen heraugegeben werden müssen, um den Betrag '''15,61 Euro''' auszuzahlen.
[[Bild:001eur.png|100px]] [[Bild:002eur.png|100px]] [[Bild:005eur.png|100px]] [[Bild:010eur.gif|100px]] [[Bild:020eur.gif|100px]] [[Bild:050eur.gif|100px]] [[Bild:1eur.gif|100px]] [[Bild:2eur.png|100px]]
Ü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:
[[Bild:150px-Formative_Years_in_Indiana_Reverse.jpg|100px]] [[Bild:150px-2006_Nickel_Proof_Rev.png|100px]] [[Bild:150px-2005_Dime_Rev_Unc_P.png|100px]] [[Bild:150px-2006_Quarter_Proof.png|100px]] [[Bild:150px-2005_Half_Dollar_Rev_Unc_P.png|100px]] [[Bild:150px-LineartPresRev.png|100px]]
Ü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:
[[Bild:1grosz_2.png|100px]] [[Bild:2grosze_2.png|100px]] [[Bild:5groszy_2.png|100px]] [[Bild:10groszy_2.png|100px]] [[Bild:20groszy_2.png|100px]] [[Bild:50groszy_2.png|100px]] [[Bild:1zloty_2.png|100px]] [[Bild:2zloty_2.png|100px]] [[Bild:5zlotych_2.png|100px]]
Überprüfen Sie das Ergebnis mit hilfe von der Prozedur '''''geldwechsel'''''.
'''Hinweis:''' die Kandidatenliste soll im Quellcode angepasst werden.
==Kommentare==
<pinwand></pinwand>