AuK/Greedy-Algorithmen SS09
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
'''Dev Status'''
==Einführung==
Greedy (engl. ''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. Es wird also keine Tabelle, die alle Teilproblemlösungen bereithält, mitgeführt, wie dam beim [[dynamisches Programmieren]] der Fall ist.
Beim Greedy-Algorithmen gibt es kein Zurücknehmen und Erproben von Alternativen, wie bei [[Systematische Suche|systematischen Probieren mit Backtracking]]. Eine einmal getroffene Entscheidung wird nicht revidiert.
Der Aufwand eines Greedy-Verfahrens ist sicher '''nicht exponentiell'''. Allerdings ist die Anwendbarkeit dieses ''Superverfahrens'' sehr in Frage gestellt.
Greedy-Algorithmen brauchen um die beste Auswahl zu treffen eine vorsortierte Kandidatenliste. Die neu aufnehmende Elemente werden immer gleich an der richtigen Stelle eingefügt, so dass die Sortierung erhalten bleibt.
Der zugehörige Datentyp ist eine Prioritätswarteschlange (''priority queue''). Sie kann mit einem heap sehr effizient implementiert werden.
==Bruchteilrucksack-Problem==
Bruchteilrucksack-Problem unterscheidet sich von dem [[Systematische_Suche#Rucksackprobleme|0/1 Rucksackproblem]]. Man hat die Möglichkeit, Gegenstände auch teilweise einzupacken. Hinsichtlich der Gegenstandeswerte gehen wir von einer homogenen Verteilung aus. Das heißt, dass ein zu 80% eingepackter Gegenstand, einen Wertzuwachs von 80% seines vollen Wertes erbringt.
Die Kandidatenliste wird nach dem Quotient aus:
*<math>w_i</math> - Wert des <math>i</math>-ten Gegenstandes
*<math>g_i</math> - Gewicht des <math>i</math>-ten Gegenstandes
absteigend sortiert.
<math>\frac{w_1}{g_1}\geq\frac{w_2}{g_2}\geq\hdots\geq\frac{w_n}{g_n}</math>
Der Gegenstand mit dem größten spezifischen Wert erhält die Nummer <math>1</math>, danach folgen <math>2</math>, <math>3</math>, <math>\hdots</math>, <math>n</math> in dieser Reihenfolge.
<math>K</math> sei die Kapazität des Rucksacks.
Nach der Greedy-Strategie stecken wir nun die ersten <math>j</math> Gegenstände in den Rucksack. <math>j</math> ergibt sich, wenn Gegenstand <math>j + 1</math> der erste ist, der nicht vollständig in den Rucksack passt. Die eventuell vorhandene Restkapazität kann aber durch einen Teil <math>t</math> mit <math>0 \leq t < 1</math> des Gegenstandsgewichtes <math>g_{j+1}</math> ausgefüllt werden.
<math>K - \left(g_1 + g_2 + \hdots + g_j\right) = t \cdot g_{j+1}</math>
Der Gesamtwert <math>W</math> des so gefüllten Rucksacks beträgt
<math>W = w_1 + w_2 + \hdots + w_j + t \cdot w_{j+1}</math>
Kann man wirklich sicher sein, dass auf diese weise der größtmögliche Gesamtwert erreicht wird? Könnte es nicht besser sein, von einem der ursprünglich vollständig eingepackten Gegenstände, sagen wir <math>e</math> (mit <math>1 \leq e \leq j</math>) nur einen Teil, sagen wir <math>y</math> (mit <math>0 < y < 1</math>) zu nehmen. Dann hat man so viel Platz, dass ein Teil <math>z</math> eines Gegenstandes <math>r</math> (<math>e < r \leq n</math>) mit kleinerem spezifischem Wert als der von <math>e</math> eingepackt werden kann. Dies ergibt den folgenden Gesamtwert.
<math>W' = \left(w_1 + w_2 + \hdots + w_e + \hdots + w_j + t \cdot w_{j+1}\right) - \left(1 - y\right) \cdot w_e + z \cdot w_r</math>
Da das Gewicht des <math>z</math>-ten Teiles von <math>r</math> gerade mit dem Restgewicht <math>\left(1 - y\right) \cdot g_e</math> übereinstimmt, d.h. <math>z \cdot g_r = \left(1 - y\right) \cdot g_e</math>, gilt
<math>z = \frac{\left(1 - y\right) \cdot g_e}{g_r}</math>.
Dann kann man für den Gesamtwert
<math>W' = \left(w_1 + w_2 + \hdots + w_e + \hdots + w_j + t \cdot w_{j+1}\right) - \left(1 - y\right) \cdot w_e + \frac{\left(1 - y\right) \cdot g_e \cdot w_r}{g_r}</math>
schreiben. Eine einfache Umformung ergibt
<math>W' = W - \frac{\left(1 - y\right) \cdot g_e \cdot w_e}{g_e} + \frac{\left(1 - y\right) \cdot g_e \cdot w_r}{g_r}</math>
Da <math>\left(1 - y\right) \cdot g_e > 0</math> ergibt sich wegen
<math>W' = W + \underbrace{\left(1 - y\right) \cdot g_e}_{>0} \cdot \underbrace{\left(\frac{w_r}{g_r} - \frac{w_e}{g_e}\right)}_{<0}</math>
kein Wertzuwachs. Ganz im gegenteil, es gilt sogar <math>W' < W</math>.
Wir können also sicher sein, dass die Greedy-Methode das Bruchteil-Rucksackproblem effizient löst.
Hier unten ist die Prozedur ''teil_rucksack'' zu sehen, die nimmt als Eingabe die Rucksack-Kapazität und liefert die beste Einpackungsmöglichkeit aus der vorgegebenen Kandidatenliste ''(Wert . Gewicht)''. Gesamtwert, Gesamtgewicht und Bruchteil des letztes Elements werden auch ausgegeben.
<code hidden>(define delete
(lambda (item ls)
(cond
((null? ls) '())
((equal? (car ls) item) (cdr ls))
(else
(cons (car ls)(delete item (cdr ls)))))))
(define k-sum
(lambda (ls)
(letrec
((helfer
(lambda (ls wert)
(cond
((null? ls) wert)
(else
(helfer (cdr ls) (+ wert (cdr(car ls)))))))))
(helfer ls 0))))
(define w-sum
(lambda (ls)
(letrec
((helfer
(lambda (ls wert)
(cond
((null? ls) wert)
(else
(helfer (cdr ls) (+ wert (car(car ls)))))))))
(helfer ls 0))))</code>
<code>(define teil_rucksack
(lambda (kapazitaet)
(let*
((faktor 1)
(kandidatenliste '((400 . 2) (500 . 4) (200 . 2) (150 . 3) (30 . 1) (75 . 5)))
(loesung? (lambda (ls kls) (= kapazitaet (k-sum ls))))
(okay? (lambda (ls) (>= kapazitaet (k-sum ls))))
(naechster car)
(modify+ (lambda (x ls) (delete x ls)))
(modify- (lambda (rls kls) (set! faktor(/(- kapazitaet (k-sum rls))(cdr(car kls))))
(list(cons(*(car(car kls))faktor)(*(cdr(car kls))faktor)))))
(ziel (lambda (ls)(cons(cons(cons(reverse ls)(list faktor)) (list(k-sum ls)))(list(w-sum ls))))))
(letrec
((helfer
(lambda (kandidaten resultat)
(cond
((loesung? resultat kandidaten)(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- resultat kandidaten) resultat))))))))
(helfer kandidatenliste '())))))</code>
<eval>(teil_rucksack 13)</eval>
==Aufbau-Template==
Bestandteile des Algorithmus:
* eine (sich verbrauchende) Kandidatenliste,
* eine (sich aufbauende) Resultatliste,
* Funktionen:
** ''loesung?'', die überprüft, ob die aktuelle Resultatliste eine Lösung des Problems darstellt,
** ''okay?'', die überprüft, ob die Erweiterung einer Resultatliste durch den nächsten Kandidaten zulässig ist,
** ''naechster'', die den besten Kandidaten aus der Liste auswählt,
** ''modify+'', die die Kandidatenliste im positiven Fall modifiziert,
** ''modify-'', die die Kandidatenliste im negativen Fall modifiziert,
** ''ziel'', die die Lösung angibt.
(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 '())))))
==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|'''Bild 6.1:''' 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]]).
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.
[[Bild:Kropki.png|thumb|295px|left|'''Bild 6.2:''' 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 [http://de.wikipedia.org/wiki/Algorithmus_von_Floyd_und_Warshall Floyd und Warshall] 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.
Das Problem ist, mathematisch gesehen, eine Sache der [http://de.wikipedia.org/wiki/Graphentheorie 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.
Zur Speicherung von Graphen verwendet man Matrizen. Eine gängige Form sind sog. ''Adjazenmatrizen'', die für jedes Knotenpaar vermerken, ob die durch die aktuelle Zeile bzw. Spalte bestimmten Knoten durch eine Kante verbunden sind.
Handelt es sich um einen '''gewichteten Graph''', dessen Kanten z.B. mit je einer Zahl für eine bestimmte Länge, Masse oder einen Euro-Betrag markiert sind, werden diese ''Gewichte'' in der Adjazenmatrix angegeben. Nicht vorhandene Kanten werden durch einen vereinbarten Wert, meist 0, ''x'' oder eine sehr große Zahl, beschrieben.
Wir sprechen von einem '''gerichteten Graph''' (engl. ''directed graph'', ''Digraph''), wenn die Kanten einseitig gerichtete Pfeile sind.
'''Dijkstras Algorithmus'''
Gegeben sei der Bild in Bild 6.2 modellierter Stadplan mit 7 markanten Punkten ''A'', ''B'', ''C'', ''D'', ''E'', ''F'' und ''G''.
Gesucht ist die kürzeste Strecke von ''A'' (Airport) zum Stadthotel ''D''.
Die Grundidee des Algorithmus ist, ab einem Startknoten die kürzest möglichen Wege weiter zu verfolgen und längere Wege beim Updaten auszuschließen. Er besteht aus diesen Schritten:
# Initialisiere eine Menge von Startknoten mit einem Element (''A'').
# Weise allen Knoten die beiden Eigenschaften "Distanz" und "Vorgänger" zu. Initialisiere die Distanz im Startknoten mit 0 und in allen anderen Knoten mit ∞.
# Solange es noch unbesuchte Knoten gibt wähle darunter denjenigen mit minimaler Distanz aus und
## Speichere, dass dieser Knoten schon besucht wurde
## Berechne für alle noch unbesuchten Nachbarknoten die Summe des jeweiligen Kantengewichtes und der Distanz im aktuellen Knoten
## Ist dieser Wert für einen Knoten kleiner als die dort gespeicherte Distanz, aktualisiere sie und setze den aktuellen Knoten als Vorgänger.<br/>Dieser Schritt wird auch als ''Update'' bezeichnet und ist die zentrale Idee von ''Dijkstra''.
Naive Implementation: <math>\mathcal{O}\left(n^2\right)</math>.
Heaps Implementation: <math>\mathcal{O}\left(\left(m + n\right) log\ n\right)</math>, wo <math>n</math> Knoten und <math>m</math> Kanten sind.
[[Bild:Kropki_solved.png|thumb|295px|right|'''Bild 6.3:''' Bild 6.2 bearbeitet von Dijkstra-Algorithmus (von ''A'' nach ''D'')]]
S:={s};
Distanz(s):=0;
for all v<math>\in</math>V\{s} do {
Distanz(v)=Kante(s,v);
Vorgaenger(v)=s;
}
while <span style="background:#FA8072">z<math>\notin</math>S</span> do {
Finde v'<math>\in</math>V\S mit Distanz(v')=min{Distanz(v) | v<math>\in</math>V\S};
S:=S<math>\cup</math>{v'};
for all v<math>\in</math>V\S do {
if <span style="background:#FA8072">Distanz(v')+Kante(v',v) < Distanz(v)</span>
then {
Distanz(v):=<span style="background:#FA8072">Distanz(v')+Kante(v' ,v)</span>;
Vorgaenger(v):=v'
}
}
}
===Kruskal===
[[Bild:Kruskal.png|thumb|295px|'''Bild 6.4:''' Kruskal Algorithmus (minimaler Spannbaum)]]
[http://en.wikipedia.org/wiki/Joseph_Kruskal Joseph Kruskal auf Wikipedia]
Der Algorithmus von Kruskal ist ein Algorithmus der Graphentheorie zur Berechnung minimaler Spannbäume von ungerichteten Graphen. Der Graph muss dazu zusätzlich zusammenhängend, kantengewichtet und endlich sein.
Der Algorithmus stammt von Joseph Kruskal, der ihn 1956 in der Zeitschrift „Proceedings of the American Mathematical Society“ veröffentlichte. Er beschrieb ihn dort wie folgt:
''Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von G (dem Graphen) die kürzeste Kante,''
''die mit den schon gewählten Kanten keinen Kreis bildet.''
Die kürzeste Kante bezeichnet dabei jeweils die Kante mit dem kleinsten Kantengewicht. Nach Abschluss des Algorithmus bilden die ausgewählten Kanten einen minimalen Spannbaum des Graphen.
Wendet man den Algorithmus auf unzusammenhängende Graphen an, so berechnet er einen minimalen Wald, also minimal spannende Bäume für jede Zusammenhangskomponente des Graphen.
Best case: <math>\mathcal{O}\left(n\ log\ n\right)</math>, bei <math>a \leq n</math>
Average case: <math>\mathcal{O}\left(m\ log\ n\right)</math>
Worse case: <math>\mathcal{O}\left(n^2\ log\ n\right)</math>, bei <math>a \leq \frac{n}{2}\left(n - 1\right)</math>
<math>n</math>: Anzahl der Knoten.
<math>m</math>: Anzahl der Kanten.
===Prim===
Minimaler Spannbaum Algorithmus, der eine Alternative zu Kruskal-Algorithmus ist. Prim stellt eine kleine Modifikation von Dijksrta-Algorithmus vor, die sich im vergleich zu Dijkstra, nur an 3 Stellen unterscheidet.
Der Prim-Algorithmus ist effizienter bei Graphen mit vielen Kanten als Kruskal-Algorithmus.
Aufwand: <math>\mathcal{O}\left(n^2\right)</math>
S:={s};
Distanz(s):=0;
for all v<math>\in</math>V\{s} do {
Distanz(v)=Kante(s,v);
Vorgaenger(v)=s;
}
while <span style="background:#FA8072">'''S!=V'''</span> do {
Finde v'<math>\in</math>V\S mit Distanz(v')=min{Distanz(v) | v<math>\in</math>V\S};
S:=S<math>\cup</math>{v'};
for all v<math>\in</math>V\S do {
if <span style="background:#FA8072">'''Kante(v',v) < Distanz(v)'''</span>
then {
Distanz(v):=<span style="background:#FA8072">'''Kante(v' ,v)'''</span>;
Vorgaenger(v):=v'
}
}
}
Die folgende Scheme-Prozedur versucht die Zahlen in Primfaktoren zu zerlegen, die sich in der Kandidatenliste befinden. In der Lösung wird auch die Anzahl der Primfaktoren ausgegeben.
<code>(define prim
(lambda (wert)
(let
((kandidatenliste '(19 17 13 11 7 5 3 2))
(loesung? (lambda (ls) (= wert (apply * ls))))
(okay? (lambda (ls) (and
(>= wert (apply * ls))
(= (round (/ wert (apply * ls)))(/ wert (apply * ls))))))
(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 '())))))
(define delete
(lambda (item ls)
(cond
((null? ls) '())
((equal? (car ls) item) (cdr ls))
(else
(cons (car ls)(delete item (cdr ls)))))))</code>
<eval>(prim 234)</eval>
==Übung==
===Teilrucksack-Problem===
Gegeben sei:
* Rucksackkapazität: 60kg
* Material 1:
**Wert: 200 000
**Gewicht: 35
* Material 2:
**Wert: 103 000
**Gewicht: 25
* Material 3:
**Wert: 92 543
**Gewicht: 14
Berechnen Sie die absteigende Kandidatenliste (schriftlich). Benutzen Sie die Scheme-Prozedur um die beste Rucksackseinpackung zu finden.
===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'''''.
===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 Dollars 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.
===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.
===Dijkstra-Algorithmus===
[[Bild:Aufgabe_Dijkstra.gif|thumb|400px|right|Dijkstra-Algorithmus Aufgabe]]
Ein Beispiel für die Anwendung des Algorithmus von Dijkstra ist die Suche nach einem kürzesten Pfad auf einer Landkarte.
Im diese Aufgabe sollen Sie aus der Adjazenzmatrix einen Graphen erstellen (schriftlich) und den kürzesten Pfad von Frankfurt nach München finden. Die Zahlen auf den Verbindungen zwischen zwei Städten geben jeweils die Entfernung zwischen den beiden durch die Kante verbundenen Städten an.
===Prim-Algorithmus===
[[Bild:prim aufgabe.gif|thumb|295px|right|Prim-Algorithmus Aufgabe]]
Verwenden Sie den Bsp. aus der Vorlesung, wählen Sie jetzt als den Startknoten: ''D''.
Ermitteln Sie eine Reihenfolgenliste für alle Knoten.
===Prim-Algorithmus (Scheme)===
Experimentieren Sie mit dem Scheme-Code für Prim-Algorithmus.
Versuchen Sie die folgenden Zahlen in Primfaktoren zu zerlegen:
* 24
* 76
* 98
* 437
* 667
'''Hinweis:''' Denken Sie auch an Erweiterung der Kandidatenliste, wenn die Prozedur einen Fehler ausgibt.
==Kommentare==
<pinwand></pinwand>