Greedyalgorithmen und -heuristiken
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
09.01.16 - hab mal versucht nen roten faden für die aufteilung zu finden - es muss alles noch bearbeitet werden - müssen die nächsten tage mal wegen der Vortragsaufteilung/Gliederung sprechen - evtl habt ihr ja noch ideen was noch rein kann/muss - ich würde gern den abschnitt matroide/unabhängigkeitssysteme machen
== Greedy-Heuristiken ==
<!-- hier kommt alles zu Heuristiken, sollte zu Algorithmen überleiten
Quelle: http://programmingwiki.de/AuK/N%C3%A4herungsverfahren_1_SS10 -->
Der Unterschied zwischen einer Greedy-Heuristik und einem Greedy-Verfahren ist hauptsächlich die Qualität der Lösungen, da ein Greedy-Verfahren eine exakte Lösung und eine Greedy-Heuristik nur eine Näherungslösung, welche jedoch in den meisten Fällen recht nah an der exakten Lösung liegt, liefert. Ein Greedy-Verfahren benötigt, anders als eine Greedy-Heuristik, zur Angabe einer exakten Lösung ein [http://de.wikipedia.org/wiki/Matroid Matroid] als zugrunde liegende algebraische Struktur. Es ist beispielsweise beim Bruchteil-Rucksackproblem der Fall, dass die zugrunde liegende algebraische Struktur ein Matroid ist, jedoch nicht beim 0/1-Rucksackproblem. Wendet man trotz dem nicht vorhandenem Matroid beim 0/1-Rucksackproblem ein Greedy-Verfahren an, so erhält man eine Näherungslösung und man spricht dann von einer Greedy-Heuristik.
Greedy-Heuristiken zeichnen sich dadruch aus, dass sie immer nach einem lokalem Optimum suchen und weder bereit sind eine Entscheidung zu revidieren noch eine lokale Verschlechterung zu ermöglichen.
Wenn man zum Beispiel eine Greedy-Heuristik zur Lösung des Traveling-Salesman-Problem verwenden möchte so wird man versuchen gerade den Knoten einzubinden, der den größten Gewinn, also hier die kürzeste Rundreise beschert. Beispielsweise könnte man auf die Idee kommen immer den Knoten einzubinden, welcher dem gerade betrachteten am nächsten liegt. Diese Strategie nennt man ''nearest neighbor heuristic''. Sie ist jedoch in den meisten Fällen nicht wirklich hilfreich, da die Ergebnisse meist unbrauchbar sind oder zumindest ziemlich weit vom Optimum abweichen. Bessere Resultate erhält man zum Beispiel mit der ''farthest insertion''. Bei der ''farthest insertion'' beginnt man die Knoten mit dem geringstem Abstand zu verbinden oder man erstellt einen Konvexe Hülle (eine Erläuterung findet man [http://www.hyfisch.de/Lehre/UebersichtInfoSST/KonvexeHuelle.pdf hier]) und erweitert die Tour dann um den Knoten, dessen Minimalabstand zu einem bereits auf der Rundreise liegendem Knoten maximal ist. Diese Technik führt zu ebenso guten Ergebnissen wie die ''random insertion'', bei der ein unbenutzter Knoten zufällig ausgewählt wird und so integriert wird, dass die daraus resultierende Länge der Rundreise minimal wird. Ein weiteres Greedy-Verfahren ist die ''nearest insertion''oder auch ''cheapest insertion'' genannt. Bei diesem Verfahren wird der Knoten eingebunden, der die geringste Verlängerung der daraus resultierenden Teilroute zur Folge hat.
Es wurde mitlerweile bewiesen, dass größere Schritte besser sind als kleine, desshalb werden also anstelle kleine Veränderungen beim TSP zu betrachten möglichst große gewählt. Dies führt zu einem weiteren Greedy-Verfahren, der ''best insertion''. Bei diesem Verfahren geht man vor wie bei einem Bombenabwurf, es werden in einem kreisförmigen Gebiet alle Städte zerstört und dann nacheinander wieder aufgebaut, wobei man sie mittels der Farthest-Insertion-Methode in den Rundweg integriert, was ''best insertion'' genannt wird. Nach diesem Verfahren aus dem ''Ruin-and-recreate''-Bereich ist die entstandene Länge des Rundweges im allgemeinen kürzer als vorher.
Zwei schöne Applets für Greedy Heuristiken finden sie auf [http://www-e.uni-magdeburg.de/mertens/TSP/node2.html dieser Seite] von Stephan Mertens.
= Matroide, die Theorie der Unabhängigkeitsysteme - Reihenfolge und Struktur wird noch angepasst... Inhalt noch in arbeit=
ca 20-25min
---Warum funktioniert der allgorithmus nur manchmal?
---Lokales Globales Optimum
---Matroide erklären
Motivation: Ein Greedy-Algorithmus findet für ein Optimierungsproblem auf '''Unabhängigkeitssystemen''' genau dann die optimale Lösung, wenn die zulässigen Lösungen die unabhängigen Mengen eines '''Matroids''' sind.
Sonst führt der Algorithmus lediglich zu einem lokalen Optimum. Ein Unabhängigskeitssystem ist umgekehrt genau dann ein Matroid, wenn ein Greedy-Algorithmus zu jeder Gewichtsfunktion immer Basen mit minimalen/maximalen Gewicht berechnen kann.
Ein Unabhängigkeitssystem ist in der Kombinatorik eine '''Verallgemeinerung der mathematische Struktur des Matroides'''. Ein Unabhängigkeitssystem (E,U) besteht aus einer endlichen Grundmenge E und einem darüber definierten nicht leeren Mengensystem U, das bezüglich der Teilmengen-Bildung abgeschlossen ist.
<div style= "background-color:#D6D6C2; padding:10px">
=== Definition: Unabhängigkeitssystem ===
Sei <math>E</math> eine beliebige endliche Grundmenge und <math>\mathcal U</math> ein System von Teilmengen von <math>E</math> (also <math>\mathcal U\subseteq \mathcal{P} (E)</math> ), dann ist das Paar <math>(E,\mathcal{U})</math> ein Unabhängigkeitssystem, wenn die folgenden Bedingungen erfüllt sind:
# <math>\emptyset \in \mathcal{U}</math> (Nicht zu verwechseln mit <math>\emptyset \subseteq \mathcal{U}</math>, was trivial wäre, da die leere Menge Teilmenge jeder Menge ist.)
# <math>A \subseteq B, B\in \mathcal{U} \Rightarrow A\in \mathcal{U}</math> (<math>\mathcal{U}</math> ist nach unten <math>\subseteq</math>-abgeschlossen.)
1. ist äquivalent zu der Forderung dass <math>\mathcal{U}</math> nicht leer ist.
</div>
Durch Hinzufügen der sogenannten ''[[Matroid#Austauscheigenschaft|Austauscheigenschaft]]'' entsteht aus einem Unabhängigkeitssystem ein [[Matroid]].
Der Begriff Matroid entstammt der Untersuchung der Unabhängigkeit der Spaltenvektoren einer Matrix. Er ist eine Verschmelzung der Wörter "Matrix" und "Oides(griech. = ähnlichkeit)".
<div style= "background-color:#D6D6C2; padding:10px">
=== Definition: Matroid ===
Sei $E$ eine Menge und $\mathcal U \subseteq \mathcal P(E)$ ein [[Mengensystem]] über $E$. Das [[Geordnetes Paar|Paar]] $M = (E;\mathcal U)$ heißt Matroid, falls folgende Bedingungen erfüllt sind:
:1. $\emptyset \in \mathcal U$
:2. $\forall A \in \mathcal U\, \forall B \in \mathcal P(E) \colon B \subseteq A \Rightarrow B \in \mathcal U$
:3. $\forall A; B \in \mathcal U \colon \left| B \right| < \left| A\right| \Rightarrow (\exists x \in A \setminus B \colon B \cup \{x\} \in \mathcal U)$
Dabei ist $\left| A \right|$ die [[Mächtigkeit (Mathematik)|Kardinalität]] der Menge $A$.
Die Elemente von $E$ heißen die Punkte, die Elemente von $\mathcal U$ die unabhängigen Teilmengen von $M$, Mengen aus $\mathcal P(E) \setminus \mathcal U$ werden abhängig genannt.
Genügt $M$ nur den ersten beiden Eigenschaften, so bildet es ein [[Unabhängigkeitssystem]].
Erfüllt $M$ noch folgende zusätzliche Bedingung
:$\exists n\in \N \colon \forall A \in \mathcal U \colon |A|\leq n$
dann ist das Matroid von endlichem Rang und man nennt das kleinste <math>n</math>, das diese Bedingung erfüllt, den Rang des Matroides.
</div>
== Beispiele: Unabhängigkeit ...grafiken und inhalt werden nochmal bearbeitet==
herleitung von Linearer Algebra
kurze erläuterung zur linearen unabhängigkeit
definition
<table border="4" width="100%">
<tr>
<td width="40%"><center>'''Aufgaben/Beispiele'''</center></td>
<td width="15%"><center>'''Matrix'''</center></td>
<td width="20%"><center>'''Fragen'''</center></td>
<td width="20%"><center>'''Antworten'''</center></td>
</tr>
<tr>
<td height="250">Bild-weis jmd wie man bilder im wiki skaliert? ansonsten passe ich die bilder offline noch an</td>
<td><center><math>
\left(
\begin{array}{cccccc}
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1/2 & 1 & 0 \\
0 & 0 & 1 & 1/2 & 1 & 0 \\
\end{array}
\right)
</math></center></td>
<td><ul>
<li>Welcher Vektor ist nicht wie die anderen?</li><br>
<li>Welcher andere Vektor ist nicht wie die anderen?</li><br>
<li>Welches Vektorenpaar ist nicht wie die anderen?</li><br>
</ul></td>
<td><ul>
<li>A, immer wählbar ohne Abhängige Sets zu erzeugen</li><br>
<li>F, da 0-Vektor, kein "Ortswechsel" mit ihm möglich</li><br>
<li>DE, zeigen in die selbe Richtung</li><br>
</ul></td>
</tr>
<tr>
<td height="250">Bild</td>
<td><center><math>
\left(
\begin{array}{cccccc}
1 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 & 1 & 0 \\
\end{array}
\right)
</math></center></td>
<td><ul>
<li>Welche Kante ist nicht wie die anderen?</li><br>
<li>Welche andere Kante ist nicht wie die anderen?</li><br>
<li>Welches Kantenpaar ist nicht wie die anderen?</li><br>
</ul></td>
<td><ul>
<li>A, da ohne ihn der Graph in 2 Teile zerfällt</li><br>
<li>F, da kein "Ortswechsel" mit ihm möglich</li><br>
<li>DE, haben die selbe Funktion(Zwillinge)</li><br>
</ul></td>
</tr>
<tr>
<td height="250">Bild</td>
<td><center><math>
\left(
\begin{array}{cccccc}
1 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 & 0 \\
\end{array}
\right)
</math></center></td>
<td><ul>
<li>Welcher Knoten ist nicht wie die anderen?</li><br>
<li>Welcher andere Knoten ist nicht wie die anderen?</li><br>
<li>Welches Knotenpaar ist nicht wie die anderen?</li><br>
</ul></td>
<td><ul>
<li>A, da er immer Wählbar ist</li><br>
<li>F, da er niemals Wählbar ist</li><br>
<li>DE, sind niemals gleichzeitig Wählbar</li><br>
</ul></td>
</tr>
</table>
'''Aufgabe/Beispiel: Lineare Algebra'''
#*Bilde ein Menge unabhängiger Vektoren.
[[Bild:Basch_Vektoren.JPG]]
<math>
A =
\left(
\begin{array}{cccccc}
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
\end{array}
\right)
</math>
'''Aufgabe/Beispiel: Graphentheorie'''
#*Bilde eine größtmögliche Menge an Kanten ohne dabei Kreise zu bilden. Bilde die kleinstmögliche Menge an Straßen um alle Städte zu verbinden. Es dürfen dabei keine Kreise entstehen!
#*Welche Straßen definitiv?
#*Welche definitiv nicht?
[[Bild:Basch_Ungegraph.JPG]]
<math>
A =
\left(
\begin{array}{cccccc}
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
\end{array}
\right)
</math>
'''Aufgabe/Beispiel: Matching'''
#*Bilde so viele Paarungen wie möglich.
[[Bild:Basch_Matching.JPG]]
<math>
A =
\left(
\begin{array}{cccccc}
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
\end{array}
\right)
</math>
Evtl weglassen oder als zusatzaufgabe.
Aufgabe/Beispiel: Gleichungen
$a=z^3,b=x+y,c=x-y,d=xy,e=x^2y^2,f=1$
folgerungen anhand der zu erstellenden ergebnislisten welche alle gleich sind
Ergebnis für alle Aufgaben(independent set´s) {leere Menge}{a,b,c,d,e}{ab,ac,ad,ae,bc.bd,be,cd,ce}{abc,ace,abe,abd,acd}->letzteres=Bases=independent set that you con not enlarge !Ergebnisse nochmal überprüfen...
#*lineare unabhängigkeit-
#*Ungerichtete Graphen: ein Set an Kanten ist unabhängig wenn sie keine Kreise bilden
#*Gerichtete Graphen: ?
#*Matching: eine Set ist unabhängig wenn sie gleichzeitig gematcht werden kann
#*Gleichungen: eine Set an Ausdrücken ist unabhängig wenn
== Greedy-Algorithmen ==
ca 15min-20min
---was sind greedy algorithmen?
---Wie ist der allgemeine Aufbau?
---Template zeigen und auf Bsp anwenden
---evtl Beispiele für extremfälle vorstellen-globales optimum kruskal, lokales optimum rucksack0/1, fall in dem der greedy algorithmus versagt gerichteter graph
Greedy-Algorithmen oder auch gierige Algorithmen zeichnen sich dadurch aus, dass sie schrittweise und ohne zurückzusetzen, eine Lösung aufbauen indem sie
anhand lokaler Informationen den Folgezustand auswählen, welcher zum Zeitpunkt der Wahl das beste Ergebnis verspricht.
Es werden dabei nicht mehr Teillösungen konstruiert als unbedingt nötig.
Die Basis eines Greedy-Algorithmus ist eine bereits (absteigend) vorsortierte Liste. Wird diese erweitert, werden die entsprechenden Elemente direkt an die richtige Stelle einsortiert.
#*'''Vorteil:''' sehr schnell, gute (Näherungs-)Lösung.
#*'''Nachteil:'''
#*keine Berücksichtigung früherer Lösungen; keine Revision einmal getroffener Entscheidungen.
#*Endlösung möglicherweise nicht optimale Lösung. Greedy-Algorithmen sind oft schnell, lösen viele Probleme aber nicht optimal.
== Aufbau ==
'''Im Allgemeinen besteht ein Greedy-Algorithmus aus folgenden Bestandteilen:'''
# eine sich verbrauchende '''Kandidatenliste'''
# eine sich aufbauende '''Resultatliste'''
#'''Funktionen'''
#*''loesung?'', die kontrolliert, ob die aktuelle Resultatliste eine Lösung des Problems darstellt
#*''okay?'', die kontrolliert, ob die Erweiterung einer Resultatliste durch den nächsten Kandidaten zulässig ist
#*''ziel'', die den Wert einer Lösung angibt
#'''Auswahlfunktion'''
#*''nächster'', die aus der Kandidatenliste den jeweils besten "Happen" auswählt
#'''Modifikationsfunktionen'''
#* ''modify+'', die die Kandidatenliste im positiven Fall, also wenn die Erweiterung zu einer zulässigen Liste führt, modifiziert
#* ''modify-'', die die Kandidatenliste im negativen Fall, also wenn die Erweiterung nicht zu einer zulässigen Liste führen würde, modifiziert
== Greedy 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.
<code id="56905c4837a7e">
(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 '())))))
</code>
===Anwendungsbeispiel 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>
== Beispiele ==
ca 15-20min
---Algorithmen aus vorangegangenen Vorträgen vorstellen und erklären warum das ergebnis ein globales Optimum ist
---evtl weitere übungen um in kleineren graphen zu erkennen ob greedy ein lokales oder globales optimum liefern wird
<ul>
<li>Algorithmus von Kruskal für die Suche nach einem minimalen Spannbaum</li>
<li>Algorithmus von Prim für die Suche nach einem minimalen Spannbaum (das zugrundeliegende Mengensystem – die Menge der Bäume – ist aber kein Unabhängigkeitssystem)</li>
<li>Algorithmus von Dijkstra zur Suche eines kürzesten Weges</li>
<li>Färbungsalgorithmus usw</li>
</ul>
==== Kruskal-Algorithmus ====
Der Mathematiker Joseph Kruskal entwickelte einen Algorithmus zur Suche nach einem minimalen Spannbaum. Durch seine Effizienz arbeitet der Algorithmus in $\mathcal{O}\left( m \log n\right)$, wobei $m$ die Anzahl der Kanten und $n$ die Anzahl der Knoten darstellen. Sollte $m \leq n$ gelten, so arbeitet der Algorithmus in $\mathcal{O}\left( n \log n\right)$, für sehr wenige $m$, d. h. $m \leq \frac{n}{2}\left( n-1\right)$, in $\mathcal{O}\left( n^2 \log n\right)$.
Der Algorithmus lässt sich wie folgt beschreiben:
* Alle Kanten werden in aufsteigender Länge in einer Liste sortiert.
* Die erste Kante bildet mit ihren anschließenden Knoten den Startgraphen. Existeren mehrere Kanten gleicher Länge, werden alle verwendet.
* Solange noch nicht alle Knoten verbunden sind, wird dieses Verfahren wiederholt.
* Würde durch die Hinzunahme einer Kante ein Kreis entstehen, wird diese Kante aus der Liste gestrichen und mit der nächsten fortgefahren.
Am Beispiel wird der Algorithmus deutlich. Als Basis dient wieder der bereits weiter oben verwendete Graph.
<gallery widths="400" heights="300" perrow="2">
Bild:S3dafran_S3dafran_dijkstra_1.png|Wir suchen uns die Kanten mit den geringsten Werten. Dies wären $\overline{BC}$, $\overline{DE}$ und $\overline{DG}$. Welche wir wählen, ist egal.
Bild:S3dafran_Kruskal_2.png|Wir wählen die Kante $\overline{BC}$ mit ihren zugehörigen Knoten als Startgraph.
Bild:S3dafran_Kruskal_3.png|Die beiden anderen Favoriten kommen ebenfalls hinzu.
Bild:S3dafran_Kruskal_4.png|Die nun kürzeste Strecke ist die Strecke $\overline{AB}$, die nun an den Graphen "angeschlossen" wird.
Bild:S3dafran_Kruskal_5.png|Mit der Strecke $\overline{BG}$ sind nun fast alle Knoten verbunden.
Bild:S3dafran_Kruskal_6.png|Als letzte noch fehlende Strecke kommt die Strecke $\overline{AF}$ hinzu und vervollständigt den minimalen Spannbaum.
</gallery>
==== Prim-Algorithmus ====
Ein weiterer Algorithmus zur Ermittlung des minimalen Spannbaums wurde 1930 vom Mathematiker Vojtěch Jarník entwickelt, 1957 von Robert Prim und 1959 von Edsger Dijkstra wiederentdeckt. Auf Basis des Dijkstra-Algorithmus arbeitet dieser Algorithmus in $\mathcal{O}\left( n^2\right)$.
Die Funktionsweise des Algorithmus lässt sich wie folgt beschreiben:
* Ein beliebiger Knoten eines Graphen wird gewählt.
* Nun wird die angrenzende Kante mit dem geringsten Wert gewählt und der angrenzende Knoten verbunden.
* Dieses Verfahren wird so lange wiederholt, bis alle Knoten verbunden sind. Es werden nun aber alle Kanten an allen verbundenen Knoten betrachtet.
* Würde durch die Hinzunahme einer Kante ein Kreis entstehen, wird diese Kante aus der Liste gestrichen und mit der nächsten fortgefahren.
Die Erweiterung der Dijkstra-Algorithmus ergibt sich dann wie folgt:
/*
* S: Lösungsmenge
* s: Startknoten
* V: Menge aller Knoten des Graphen
*/
S := {s};
Distanz(s) := 0;
for all $v \in V\backslash \lbrace s\rbrace$ do {
Distanz(v) := Kante(s, v);
Vorgänger(v) := s;
}
while $S \neq V$ do {
Finde $u \in V\backslash S$ mit Distanz(u) = min{Distanz(v) | $v \in V\backslash S$};
S := $S \cup \lbrace u\rbrace$;
for all $v \in V\backslash S$ do {
if Kante(u, v) < Distanz(v)
then {
Distanz(v) := Kante(u, v);
Vorgänger(v) := u;
}
}
}
Auch hier soll wieder ein Beispiel des Algorithmus verdeutlichen.
<gallery widths="400" heights="300" perrow="2">
Bild:S3dafran_S3dafran_dijkstra_1.png|Wir starten wieder mit dem bereits oben verwendeten Graphen und suchen einen Startknoten.
Bild:S3dafran_Prim_2.png|In diesem Beispiel wählen wir den Knoten ''A'' als Startknoten und betrachten die an ''A'' angrenzenden Kanten.
Bild:S3dafran_Prim_3.png|Die Strecke $\overline{AB}$ ist die kürzeste und folglich wird ''B'' in den Graphen eingebunden. Zur Menge der nun in Frage kommenden Strecken kommen die an ''B'' angrenzenden Strecken hinzu.
Bild:S3dafran_Prim_4.png|Aus der Menge der an ''A'' oder ''B'' angrenzenden (noch nicht verwendeten) Kanten ist die Strecke $\overline{BC}$ am kürzesten und wird hinzugefügt. Ebenso sind nun die an ''C'' angrenzenden Kanten zu mit betrachten.
Bild:S3dafran_Prim_5.png|Die nun kürzeste Strecke ist die Strecke $\overline{BG}$ und folglich wird ''G'' hinzugefügt.
Bild:S3dafran_Prim_6.png|Die nächste kürzeste angrenzende Strecke ist $\overline{GD}$ und wird hinzugefügt.
Bild:S3dafran_Prim_7.png|Fast vollständig ist der Spannbaum, wenn die jetzt kürzeste Strecke $\overline{DE}$ hinzugefügt wird.
Bild:S3dafran_Prim_8.png|Als letzte noch fehlende Strecke kommt die Strecke $\overline{AF}$ hinzu und vervollständigt den minimalen Spannbaum.
</gallery>