AuK/Greedy-Algorithmen SS11
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
Autoren:
* Stefan Brandt ([mailto:s3stbran@stud.hs-zigr.de s3stbran@stud.hs-zigr.de])
* Sascha Demuth ([mailto:s3sademu@stud.hs-zigr.de s3sademu@stud.hs-zigr.de])
== Idee ==
Bei vielen Optimierungsproblemen ist eine Verwendung der [[AuK/Dynamisches_Programmieren_SS11|dynamischen Programmierung]] zur Bestimmung der besten Wahl übertrieben. Dann genügen einfachere, effizientere Greedy-Algorithmen.
Greedy bedeutet ''gefräßig'' - eine gefräßige Strategie, die nach der Methode "Nimm immer den besten Happen, den du kriegen kannst." arbeitet.
Diese Methode ist recht leistungsfähig und deshalb arbeiten Greedy-Algorithmen für einen großen Bereich von Problemen gut.
Aber was ist nun der beste "Happen"? Greedy-Algorithmen treffen die Entscheidung rechnerisch auf der Basis ''lokaler'' Information, d.h. ''ohne'' Rückgriff auf Werte, die für frühere Situationen ermittelt wurden. Daraus resultiert, dass keine Tabelle, die alle Teilproblemlösungen bereithält, mitgeführt wird, wie das beim [[AuK/Dynamisches_Programmieren_SS11|dynamischen Programmieren]] der Fall ist.
Außerdem wird eine einmal getroffene Entscheidung nicht korrigiert. Es gibt kein Zurücknehmen und Erproben von Alternativen, wie beim [[AuK/Systematische_Suche_SS11|systematischen Probieren mit Backtracking]].
Der Aufwand eines solchen Verfahrens ist sicher nicht exponentiell. Allerdings stellen wir die universelle Anwendbarkeit dieses "Superverfahrens" stark in Frage, da wir uns um effiziente Algorithmen bemühen.
Greedy-Algorithmen brauchen für die Auswahl des besten "Happens" eine vorsortierte Kandidatenliste. Neu aufzunehmende 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), die wir bereits bei [[AuK/Verzweigen_und_beschränken_SS11|Verzweigen und Beschränken]] kennengelernt haben.
== Bruchteil-Rucksackproblem ==
Im Gegensatz zu dem [[AuK/Systematische_Suche_SS11#Rucksackproblem|0/1 Rucksackproblem]] gibt das ''Bruchteil-Rucksackproblem'' uns die Möglichkeit, Gegenstände auch teilweise, also Bruchstücke einpacken zu dürfen.
Bezüglich der Gegenstandswerte gehen wir von einer homogenen Verteilung aus. Dies bedeutet, dass ein Gegenstand, der beispielsweise zu 80 % eingepackt wird, einen Wertzuwachs von 80 % seines vollen Wertes erbringt.
Nehmen wir also an, wir haben einen Rucksack mit einer gewissen Kapazität <math>K</math> und einer bestimmten Anzahl an Gegenständen, diese wiederum einen Wert <math>w</math> und ein Gewicht <math>g</math> besitzen.
Nun sortieren wir diese Gegenstände absteigend nach ihrem Wert. Somit heißt die mathematische Vorschrift:
<math>\frac{w_1}{g_1}\ge\frac{w_2}{g_2}\ge...\ge\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.
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.
Die folgende Prozedur ''bruchteilrucksack'' nimmt als Eingabe die Kapazität des verwendeten Rucksacks und liefert aus der vorgegebenen Kandidatenliste die beste Einpackungsmöglichkeit. Ausgegeben werden der Bruchteil des letzten eingepackten Elements, das Gesamtgewicht und der Gesamtwert aller eingepackten Elemente.
<code id="4dc99e81d9e1e" 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 id="4dc99d9a1c13f">(define bruchteilrucksack
(lambda (kapazitaet)
(let*
((faktor 1)
(kandidatenliste '((500 . 4) (400 . 2) (200 . 2) (150 . 3) (75 . 5) (25 . 1)))
(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>
<run id="4dc99d9a1c1c6">(bruchteilrucksack 17)</run>
== Aufbau von Greedy-Algorithmen ==
Im Allgemeinen bestehen Greedy-Algorithmen aus den folgenden Bestandteilen:
* eine (sich verbrauchende) Kandidatenliste
* eine (sich aufbauende) Resultatliste
* eine Funktion ''loesung?'', die überprüft, ob die aktuelle Resultatliste eine (nicht unbedingt optimale) Lösung des Problems darstellt
* eine Funktion ''okay?'', die überprüft, ob die Erweiterung einer Resultatliste durch den nächsten Kandidaten zulässig ist
* eine Auswahlfunktion ''naechster'', die aus der Kandidatenliste den jeweils besten "Happen" auswählt
* eine Modifikationsfunktion ''modify+'', die die Kandidatenliste im positiven Fall verändert, demzufolge wenn die Erweiterung zu einer zulässigen Liste führt
* eine Modifikationsfunktion ''modify-'', die die Kandidatenliste im negativen Fall verändert, also wenn die Erweiterung zu einer unzulässigen Liste führt
* eine Funktion ''ziel'', die den Wert einer Lösung angibt
In SCHEME können wir eine Prozedur angeben, die eine Struktur aufweist, die für alle Greedy-Algorithmen unverändert übernommen werden kann. An den durch Punkte gekennzeichneten Stellen werden die Werte eingefügt, die dann den jeweils entsprechenden Algorithmus spezifizieren. Eine solche Prozedur wird demnach wie eine Schablone, ein sog. Template, benutzt.
(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 ===
Die Verwendung dieser Greedy-Schablone illustrieren wir am folgenden Beispiel der Prozedur ''geldwechsel''.
Einem Kunden wird Wechselgeld herausgegeben, wobei möglichst wenige Münzen verwendet werden sollen.
* Die ''Kandidatenliste'' besteht aus allen verfügbaren Euro-Münzen (1-, 2-, 5-, 10-, 20-, 50-Cent und 1- und 2-Euro-Münzen), die wir seit 01.01.2002 zusammen mit den Euro-Scheinen in Europa als Zahlungsmittel benutzen. Die Münzen werden mit absteigendem Cent-Wert vorsortiert.
* ''loesung?'' gibt #t zurück, wenn die Summe der verwendeten Münzen genau den auszuzahlenden Betrag ergibt.
* ''okay?'' gibt an, wenn eine Menge ausgewählter Münzen okay ist, wenn deren Summe höchstens dem zu zahlenden Betrag entspricht.
* Ist dies nicht der Fall, wird dieser Wert aus der Liste der (aussichtsreichen) Kandidaten entfernt. Dies erledigt die Prozedur ''modify-''.
* ''modify+'' lässt die Kandidatenliste unverändert. Dadurch wird erreicht, dass sich potenziell unendlich viele Münzen jeden Wertes in der ''Kandidatenliste'' befinden, so dass jeder beliebige Restbetrag immer ausgezahlt werden kann.
* Die Prozedur ''naechster'' wählt unter den verbleibenden Münzen die jenige mit dem jeweils höchsten Wert aus, ganz gleich, ob damit der zu zahlende Betrag überschritten wird oder nicht. (Dafür gibt es ja ''okay?'') Es wird immer das erste Element zurückgegeben, da zu jedem Zeitpunkt die Kandidatenliste absteigend sortiert ist.
* Die Funktion ''ziel'' gibt die Liste der verwendeten Münzen zurück.
<code id="4db593cd31be4" 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 id="4db593cd31c61">(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.
<run id="4db593cd31d1e">
(geldwechsel 1293)
</run>
== Verschiedene Greedy-Algorithmen ==
===Allgemeines zur Graphentheorie===
Ein '''Graph''' ist eine mathematische Struktur, die aus '''Knoten''' und '''Kanten''' besteht. Diese Knoten können durch Kanten verbunden werden. Jede '''Kante''' verbindet in der Regel zwei '''Knoten''' miteinander. Die '''Kanten''' können, je nach Problemstellung, ''gerichtet'' oder ''ungerichtet'', ''bewertet'' (gewichtet) oder ''unbewertet'' (ungewichtet) sein.
[[Bild:S3sademu_Bewerteter_ungerichteter_Graph.png|thumb|295px|left|'''Bild 4.1:''' Bewerteter ungerichteter Graph mit 7 Knoten]]
'''Eigenschaften des Graphen''':
*'''gerichtet''' - wenn die Kanten einseitig gerichtete Pfeile sind
*'''ungerichtet''' - wenn die Kanten in beide Richtungen gelten
*'''bewertet''' - ist wenn jeder Kante ein Wert zugeordnet wird
*'''unbewertet''' - ist wenn keiner Kante ein Wert zugeordnet wird
* '''zusammenhängend''' - ist, wenn von jedem Knoten zu jedem anderen Knoten ein Weg vorhanden ist
* Ein Graph ohne Zyklen entspricht einem Baum.
* Ein aufspannender Baum ist ein Teil des Graphen, der alle Knoten enthält, aber nur so viele Kanten besitzt, dass er einen Baum bildet.
=== Dijkstra-Algorithmus ===
[[Bild:Dijksta_Anim.gif|thumb|284px|'''Bild 4.2:''' 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#Das_Rundreiseproblem|Verzweigen und beschränken: Das 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.
Edsger W. 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 Robert Floyd und Stephen 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ädtepaare 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 ''Knoten''menge (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 auch 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. Die folgende Matrix zu dem Graphen aus '''Bild 4.1''' ist ein solches Beispiel.
[[Bild:S3sademu_Entfernungsmatrix_-_Graph.png|'''Bild 4.3:''' Entfernungsmatrix]]
Ähnlich der Feuerwehr, die schnellstmöglich von der Wache zu einem Großbrand fahren will, versucht der Dijkstra-Algorithmus den kürzesten Weg zwischen zwei Knoten zu bestimmen. Im folgenden Beispiel wird dieser Vorgang illustriert:
Gegeben ist der Graph in '''Bild 4.1''' mit den 7 Knoten ''A, B, C, D, E, F'' und ''G''. Gesucht ist die kürzeste Strecke von ''A'' nach ''D''.
<popup name="Graphische Darstellung des Dijkstra-Algorithmus">
<center>
<gallery widths="500" heights="300" perrow="2" caption="Dijkstra-Algorithmus">
Bild:S3sademu_Bild1.png|'''1.''' Ziel ist der kürzeste Weg von Knoten '''A''' nach Knoten '''D'''.
Bild:S3sademu_Bild2.png|'''2.''' Knoten '''A''' ist der Startpunkt und mit der Greedy-Strategie wird der kürzeste Weg gesucht.
Bild:S3sademu_Bild3.png|'''3.''' Da die Kante von '''A''' nach '''B''' die am niedrigsten bewertete ist, wird diese gewählt und mit '''B''' fortgefahren.
Bild:S3sademu_Bild4.png|'''4.''' Hier wird nach dem selben Schema fortgefahren. In diesem Fall die Kante von '''B''' nach '''C'''.
Bild:S3sademu_Bild5.png|'''5.''' Selber Vorgang wie bei den letzten zwei Schritten. Diesmal ist es die Kante von '''C''' nach '''G'''.
Bild:S3sademu_Bild6.png|'''6.''' Jetzt ergibt sich der Fall, dass die Kanten von '''A''' über '''B''' nach '''G''' mit dem Wert 9 kleiner sind als die von uns ausgewählten Kanten '''A, B, C und G''' mit dem Wert 13. Hier ist zu sehen, dass der reine Greedy-Algorithmus nicht zum Optimum führt.
Bild:S3sademu_Bild7.png|'''7.''' Als Reaktion auf den vorigen Fakt, gehen wir nun einen Schritt zurück und wählen die Kante von '''B''' nach '''G''' und suchen von Knoten '''G''' aus die am niedrigsten bewertete Kante.
Bild:S3sademu_Bild8.png|'''8.''' Dies ist der kürzeste Weg von '''A''' nach '''D'''.
</gallery>
</center>
</popup>
Zur Bestimmung eines kürzesten Weges von ''s'' nach ''z'', mit ''s, z Element V'', für einen gegebenen gewichteten Graphen ''G = (V, E)'' lässt sich der Dijkstra-Algorithmus folgendermaßen allgemein beschreiben:
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'
}
}
}
Im Programm bedeutet ''Kante (x, y)'' die Länge der Kante von Knoten ''x'' zu Knoten ''y''. Falls es keine solche Kante gibt, gilt ihre Länge als unendlich.
Bei geschickter Implementation des Algorithmus mit heaps für priority queues wird nur eine Rechenzeit in <math>\mathcal{O}\left(\left(m + n\right) log\ n\right)</math> benötigt, wobei <math>n</math> bzw. <math>m</math> die Zahl der Knoten bzw. Kanten bezeichnen. Dies ist noch besser als der eingangs in Aussicht gestellte quadratische Aufwand.
=== Kruskal-Algorithmus ===
[http://de.wikipedia.org/wiki/Joseph_Kruskal Joseph Kruskal auf Wikipedia]
'''Minimaler Spannbaum'''
Unter Verwendung der in [[AuK/Greedy-Algorithmen_SS11#Allgemeines zur Graphentheorie|Abschnitt 4.1]] eingeführten Grundbegriffe aus der Graphentheorie können wir einen ''zusammenhängenden'', zyklenfreien, gewichteten Teilgraphen bilden, dessen Gesamtgewicht minimal ist.
Die Knotenmenge dieses Teilgraphen stimmt mit der des vollständigen Graphen aus diesem Modell überein.
Im Allgemeinen sind aber nicht alle Kanten vorhanden.
[[Bild:S3sademu_Bild9.png|thumb|295px|left|'''Bild 4.3:''' Minimaler Spannbaum für den Graph in Bild 4.1]]
In der Graphentheorie nennt man einen ungerichteten, zusammenhängenden und zyklenfreien Graph mit mindestens einem Knoten einen Baum.
Ist ein Teilgraph eines zusammenhängenden Graphen ''G'' ein Baum, so nennt man diesen ein ''Gerüst'' von ''G''.
Da er alle Knoten als Baum aufspannt, spricht man auch von einem aufspannenden Baum, also ein ''Spannbaum''.
Für die Suche des minimalen Spannbaums gibt es einen Greedy-Algorithmus von Joseph Kruskal. Der US-amerikanische Mathematiker beschrieb den Algorithmus 1956 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.
Die Grundidee des Kruskal-Algorithmus beschreibt man folgendermaßen:
* Ordne die Kanten des Graphen nach ihren Gewichten in aufsteigender Folge
* Beginne mit der ersten Kante
* Nimm die nächste Kante hinzu, egal ob sie an die erste anschließt oder nicht. Falls es zwei Kanten mit gleichem Gewicht gibt, nimm beide.
* Wiederhole dieses Verfahren für alle Kanten, solange kein Kreis mit der nächsten Kante entsteht. Ist das der Fall, lass die Kante weg und mach mit der folgenden weiter.
<popup name="Graphische Darstellung des Kruskal-Algorithmus">
<center>
<gallery perrow="2" widths="500" heights="300" caption="Kruskal-Algorithmus">
Bild:S3sademu_Bild1.png|'''1.''' Dies ist der Ausgangsgraph.
Bild:S3sademu_Tabelle.png|'''2.''' Geordnete Kanten nach ihrem Gewicht in aufsteigender Folge.
Bild:S3sademu_Bild11.png|'''3.''' Zur Auswahl stehen die drei leichtesten Kanten BC, DG und ED mit dem Wert 3. Die Kante BC wird ausgewählt und als Startgraph <math>T</math> festgelegt.
Bild:S3sademu_Bild12.png|'''4.''' Nun wird die Kante DG gewählt und dem Startgraphen <math>T</math> hinzugefügt.
Bild:S3sademu_Bild13.png|'''5.''' Als nächstes wird die Kante ED ebenfalls hinzugefügt.
Bild:S3sademu_Bild14.png|'''6.''' Nun wird die Kante AB mit dem Gewicht 4 aus den Verbleibenden genommen und hinzugefügt.
Bild:S3sademu_Bild15.png|'''7.''' Als nächstes ist die Kante BG mit dem Gewicht 5 die Leichteste und wird hinzugefügt.
Bild:S3sademu_Bild16.png|'''8.''' Anschließend wird die Kante AF mit ihrem Gewicht 6 hinzugefügt.
Bild:S3sademu_Bild17.png|'''9.''' Alle übrigen Kanten können nicht dem Startgraphen <math>T</math> hinzugefügt werden, da alle einen Kreis bilden würden.
Bild:S3sademu_Bild18.png|'''10.''' Dies ist nun der minimale Spannbaum.
</gallery>
</center>
</popup>
Der Algorithmus arbeitet im Average case mit <math>\mathcal{O}\left(a\ log\ n\right)</math>, wobei <math>a</math> für die Anzahl der Kanten und <math>n</math> für die Knoten des betrachteten Graphen stehen. Hat der vorgegebene Graph nur wenige Kanten, etwa bei <math>a \leq n</math>, so gilt im Best case <math>\mathcal{O}\left(n\ log\ n\right)</math>. Bei höherer Dichte, d.h. <math>a \leq \frac{n}{2}\left(n - 1\right)</math>, ergibt sich im Worst case <math>\mathcal{O}\left(n^2\ log\ n\right)</math>.
=== Prim-Algorithmus ===
Der Prim-Algorithmus, welcher von dem tschechischen Mathematiker Vojtěch Jarník (*1897 †1970) 1930 entwickelt wurde und später von Robert C. Prim im Jahr 1957 und von Edsger W. Dijkstra im Jahr 1959 wieder entdeckt wurde, stellt eine Alternative für die Suche eines minimalen Spannbaums dar.
Durch eine kleine Modifikation an drei Stellen des Dijkstra-Algorithmus erhällt man ihn:
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'
}
}
}
Der Prim-Algorithmus arbeitet nach folgendem Prinzip:
* Ein beliebiger Knoten wird gewählt und als Startgraph <math>T</math> festgelegt.
* Unter den abgehenden Kanten wird die mit dem kleinsten Gewicht gewählt und mit dem anhängenden Knoten zum Startgraphen hinzugefügt
* Solange <math>T</math> noch nicht alle Knoten enthällt, wird jeweils die Kante mit dem kleinsten Gewicht gesucht
* Wenn die entsprechende Kante gefunden wurde und der entsprechende Knoten noch nicht in <math>T</math> enthalten ist, wird dieser hinzugefügt
* Wiederhole dieses Verfahren für alle Kanten, solange kein Kreis im Graph entsteht.
<popup name = "Graphische Darstellung des Prim-Algorithmus">
<center>
<gallery perrow="2" widths="500" heights="300" caption="Prim-Algorithmus">
Bild:S3sademu_Bild1.png|'''1.''' Dies ist der Ausgangsgraph.
Bild:S3sademu_Bild19.png|'''2.''' Der Knoten A wird zufällig gewählt und zum Startgraphen <math>T</math> hinzugefügt. Unter den vier abgehenden Kanten wird die Leichteste gewählt (AB).
Bild:S3sademu_Bild20.png|'''3.''' Dadurch wird der Knoten B zum Graphen hinzugefügt. Die Kante BC ist ist jetzt die leichtere Kante.
Bild:S3sademu_Bild21.png|'''4.''' Knoten C wird in <math>T</math> eingefügt und CG sticht hervor.
Bild:S3sademu_Bild22.png|'''5.''' Knoten D wird eingefügt. Bei den Kanten ergibt sich nun der Fall, dass BG niedriger gewichtet ist wie CG. Dadurch ändert sich der Graph in seinem Aussehen.
Bild:S3sademu_Bild23.png|'''6.''' Anschließend geht es weiter mit Hinzufügen von D. Hier ist die Kante DE die richtige für den nächsten Schritt.
Bild:S3sademu_Bild24.png|'''7.''' Dieser ist, dass Knoten E zum Graph hinzu kommt. Kante AE können wir nicht gebrauchen.
Bild:S3sademu_Bild25.png|'''8.''' Um den Knoten F noch in <math>T</math> einfügen zu können, sehen wir uns die drei verbindenden Kanten an und wählen Kante AF.
Bild:S3sademu_Bild18.png|'''9.''' Dies ist nun der minimale Spannbaum.
</gallery>
</center>
</popup>
Der Algorithmus arbeitet mit einem Aufwand von <math>\mathcal{O}(n^2)</math>.
== Übungen ==
== Literatur und andere Quellen ==
* Th. H. Cormen, Ch. E. Leiserson, R. Rivest, C. Stein: ''Algorithmen - Eine Einführung'', 2.Auflage, Oldenbourg Wissenschaftsverlag GmbH 2007, ISBN 978-3-486-58262-8
* Volker Heun: ''Grundlegende Algorithmen - Einführung in den Entwurf und die Analyse effizienter Algorithmen'', 2. Auflage, Vieweg+Teubner Verlag 2003, ISBN 978-3528131401
* Ch. Wagenknecht: ''Algorithmen und Komplexität'', 1.Auflage, Carl Hanser Verlag 2003, ISBN 3-446-22314-2