AuK/Minimaler Spannbaum SS12
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
Minimale Spannbäume (englisch: ''Minimal Spanning Tree'', Abkürzung: '''MST''') können zum lösen vieler Probleme genutzt werden. Ein Problem, dass man mit MST lösen kann ist z.B., dass verbinden mehrerer Inseln mit Brücken. Man möchte, dass alle Inseln miteinander verbunden sind und die Brücken minimale Länge haben und damit minimale Kosten entstehen. Dabei sollen die Inseln so verbunden werden, dass man alle Inseln über die Brücken berreisen kann und keine redundanten Brücken entstehen. Redundante Brücken sind Brücken mit der man eine Insel erreicht, die man auch über einen anderen ggf. längeren Weg hätte erreichen können. Längerer Weg heißt in diesem Fall, dass man über (eine) andere Brücke(n) reisen muss um die Insel zu erreichen.
== Spannbäume ==
[[Bild:Muessigd_Spannbaum.png|miniatur|Spannbaum]]
Im Folgenden soll eine Einführung in die Begriffe und Grundvorraussetzungen für MST gegeben werden. Die Begriffe werden dabei anhand des obigen Beispiels erklärt. <br/>
Im allgemeinen hat man $n$-Knoten die man zu einem Spannbaum verbinden möchte. Wir haben also $n$-Inseln die miteinander verbunden werden sollen. Dazu benötigt man immer $n-1$ Kanten (Brücken). <br/>
Man geht immer von einem zusammenhängenden, gewichteten und ungerichteten Graphen $G=(V,E)$ aus. $V$ ist die Menge der Knoten und $E$ ist die Menge der möglichen Verbindungen zwischen allen Parren von Knoten. In unserem Beispiel also alle möglichen Brücken. Jede Kante $(u,v)\in E$ besitzt ein Gewicht $w(u,v)$ (deshalb gewichtet), dass die Länge (auch Kosten gennant) angibt. Ein Graph $G$ ist ungerichtet, wenn die Kanten des Graphen keine Pfeile sondern Striche sind. Das heißt also, dass es innerhalb des Graphen keine Einschränkung der Wege gibt. Ein ungerichteter Graph heißt zusammenhängend, wenn es zu je zwei belliebigen Knoten $u$ und $v$ einen ungerichteten Weg gibt mit $u$ als Startknoten und $v$ als Endknoten.<br/>
Die Kante $(u,v)$ ist die Kante, die die beiden Knoten $u$ und $v$ verbindet. Ist $S$ eine azyklische Teilmenge $S \subseteq E$ die alle Knoten verbindet so ist dies ein Spannbaum. Azyklisch bedeutet, dass sich keine Kreise bilden dürfen. Da dies eine nötige Bedingung für Baum ist. Der Spannbaum ist eine Sonderform des Baums, denn es ist ein Baum der einen Graphen aufspannt.
=== Minimale Spannbäume ===
[[Bild:Muessigd_Spannbaumkrusk.png|miniatur|minimaler Spannbaum]]
Die azyklische Teilmenge $T \subseteq E$, die alle Knoten miteinander verbindet ist ein Spannbaum. Ist das Gesamtgewicht minimal so ist dies ein minimaler Spannbaum.
$$w(T)=\sum_{(u,v)\in{}T}{w(u,v)}$$
Scheme-Prozedur zur Berechnung des Gewichts.
<code id="4fb23af8e7809">
(define gewicht
(lambda (baum)
(if (eq? baum '())
0
(+ (cadar baum) (gewicht (cdr baum))))))
</code>
Auf der rechten Seite ist ein minimaler Spannbaum zu sehen. Die roten Kanten sind die Kanten des minimalen Spannbaums die grauen Kanten, sind die Kanten, die vom Graphen nicht benötigt werden.
Zur Bestimmung minimaler Spannbäume gibt es zwei bekannte Algorithmen. Einen von Kruskal und einen von Prim. Beide haben eine Laufzeit unter Verwendung binärer Heaps von $\mathcal{O}(E\lg{}V)$. Der Prim-Algorithmus läuft jedoch effektiver unter Verwendung von Fibonacci-Heaps mit einer Laufzeit von $\mathcal{O}(E+V\lg{}V)$. Dies ist eine Verbesserung unter der Vorraussetzung, dass $|V|$ wesentlich kleiner ist als $|E|$.
Beide Algorithmen sind [[AuK/Greedy-Algorithmen_SS09#Einf.C3.BChrung|Greedy-Algorithmen]]
=== Beispiel ===
<code id="4faa558938b93" hidden>(define Faehren '(((A . B) 67) ((A . C) 58) ((A . D) 90) ((A . F) 386) ((A . G) 390)
((B . C) 60) ((B . E) 202)
((C . D) 28) ((C . E) 154)
((D . E) 62) ((D . F) 217)
((E . F) 117) ((E . G) 171)
((F . G) 16)))
(define Inseln '(A B C D E F G))</code>
[[Bild:Muessigd_Graph-kanaren.jpg|miniatur|350px|Graph Kanaren]]
$G=(V,E)$<br>
$V=\{A, B, C, D, E, F, G\}$<br>
$E=\{(A, B), (A, C), (A, D), (A, F), (A, G),$<br>
$(B, C), (B, E),$<br>
$(C, D), (C, E),$<br>
$(D, E), (D, F),$<br>
$(E, F), (E, G),$<br>
$(F, G)\}$
Gewicht der Kanten (in km):<br>
$w(A, B)=67$ $w(A, C)=58$ $w(A, D)=90$ $w(A, F)=386$ $w(A, G)=390$<br>
$w(B, C)=60$ $w(B, E)=202$<br>
$w(C, D)=28$ $w(C, E)=154$<br>
$w(D, E)=62$ $w(D, F)=217$<br>
$w(E, F)=117$ $w(E, G)=171$<br>
$w(F, G)=16$<br>
<popup title="Namen der Inseln">
$A$ - Isla de la Palma<br>
$B$ - Hierro<br>
$C$ - Isla de la Gomera<br>
$D$ - Tenerife<br>
$E$ - Gran Canaria<br>
$F$ - Fuerteventura<br>
$G$ - Lanzarote<br>
</popup>
'''Aufgabe 1'''<br>
Der Graph zeigt die Kanarischen Inseln zwischen diesen Inseln sollen durch Fähren verbunden werden. Dabei sollen die Fähr-Verbindungen so billig wie möglich sein. Es ist davon auszugehen, dass je kürzer die Entfernung ist, desto billiger ist die Fähr-Verbindung. Es muss einen Weg zwischen je zwei Inseln geben, direkte Verbindungen sind nicht notwendig. Die Menge der Kanten sind die möglichen Fähr-Verbindungen.<br>
Wie viele Fähr-Verbindungen sind notwendig?
Welche Verbindungen sollten gewählt werden?
Wie groß ist die Gesamtstrecke der Fähr-Verbindungen?
<popup title="Lösung">
$6$ Fähr-Verbindungen sind notwendig.<br>
Kanten des minimalen Spannbaums mit Wichtung:<br>
$w(A, C)=58$ $w(C, D)=28$ $w(B, C)=60$ $w(D, E)=62$ $w(E, F)=117$ $w(F, G)=16$<br>
Die Gesamtstrecke der Fähr-Verbindung beträgt $341$km</popup>
== Grundbegriffe Schnitt und Zyklus ==
=== Schnitt ===
[[Bild:Chlorophyllkid_Schnitt.png|thumb|390px|right|Cut-Property]]
Ein ''Schnitt'' in einem verbundenen Graphen ist eine Teilmenge $E'$ von Kanten, so dass $G \setminus E'$ nicht verbunden ist.
'''Schnitteigenschaft:''' (engl. Cut-Property) <br>
Sei $E'$ ein Schnitt und $e$ eine Kante mit minimalen Kosten in $E'$. Dann gibt es einen Spannbaum $T$ von $G$ der $e$ enthält. Außerdem, wenn $T'$ in einem minimalen Spannbaum vorkommt und $T'$ keine Kante von $E'$ enthält, dann ist $T' \cup {e}$ in einigen minimalen Spannbäumen enthalten.
'''Beispiel:'''
$e$ ist die billigste Kante im Schnitt $E'$ und $p$ ist ein Pfad im MST, der die Endpunkte von $e$ $(u, v)$ verbinden soll. Man kann also die Kante $e'$ aus dem Spannbaum entfernen und durch $e$ ersetzen, sodass immer noch die Baumeigenschaft gilt.
=== Zyklus ===
[[Bild:Chlorophyllkid_Zyklus.png|thumb|390px|right|Cycle-Property]]
Ein ''Zyklus'' in einem verbundenen Graphen ist ein...
'''Zykleneigeschaft:''' (engl. Cycle-Property) <br>
Sei $C$ ein Zyklus in $G$, $e$ eine Kante aus $C$ mit maximalem Gewicht und $T$ ein Spannbaum der $e$ enthält.
$Tu$ und $Tv$ seien Teilbäume aus $T \setminus e$ und $e'$ eine Kante aus $C$ welche ebenfalls $Tu$ und $Tv$ verbindet. Dann existiert ein Spannbaum mit geringerem Gewicht als $T$, indem man $e$ aus dem Spannbaum entfernt und $e'$ hinzufügt.
----
== Algorithmen zum Bilden minimaler Spannbäume ==
=== Generischer Algorithmus ===
Im generischen Algorithmus ist die Greedy-Strategie verarbeitet. Dies bedeutet, dass in jedem Schritt eine Kante dem Baum hinzugefügt wird.
==== Idee ====
$A$ ist eine Kantenmenge und wird vom Algorithmus verarbeitet. Dabei ist $A$ vor jeder Iteration eine Teilmenge eines minimalen Spannbaums. Während der Laufzeit des Algorithmus wird in jedem Schritt eine Kante $(u,v)$ bestimmt, sodass auch $A\cup{}{(u,v)}$ eine Teilmenge eines minimalen Spannbaums ist.
$A$ muss dabei immer azyklisch sein, damit wenn der Algorithmus terminiert $A$ ein Spannbaum ist. Solange der Algorithmus ausgeführt wird, ist der Graph $G_{A}=(V,A)$ ein Wald. Die Zusammenhangskomponenten des Waldes sind Bäume. Diese Bäume können auch nur aus einem einzigsten Knoten bestehen. Dies ist zum Beispiel zu Beginn der Fall. Zu diesem Zeitpunkt gibt es $|V|$ Bäume. Die ''while''-Schleife wird $|V|-1$ mal ausgeführt, da ein Spannbaum aus $Knoten - 1$ Kanten besteht. Nach jedem Schleifendurchlauf verringert sich die Anzahl der Bäume im Wald um eins. Sobald der Wald aus nur noch einem Baum besteht terminiert der Algorithmus.
==== Pseudocode ====
Generischer_minimaler_spannbaum(G, w)
$A\leftarrow{}\emptyset{}$
'''while''' $A$ kein Spannbaum
'''do''' bestimme sichere Kante $(u,v)$ für $A$
$A\leftarrow{}A\cup{}{(u,v)}$
'''return''' $A$
==== Beweis ====
=== Algorithmus von Kruskal ===
==== Idee ====
Basierend auf dem generischen Algorithmus funktioniert der Algorithmus nach Kruskal nach folgendem Prinzip:
<ol>
<li>Nimm die kleinste Kante (u,v) aus E(G).</li>
<li>Prüfe ob die Kante für den Spannbaum nützlich ist.</li>
<li>Füge die Kante dem Baum hinzu.</li>
</ol>
Dieses Verfahren nenn man auch die '''FIND'''-'''UNION'''-Methode.
'''Verständnis-Aufgabe:'''
[http://students.ceid.upatras.gr/~papagel/project/kruskal.htm Applet Kruskal-Algorithmus]
==== Pseudocode ====
Aus der Idee lassen sich nun folgende Pseudocodes entwickeln:
<table>
<tr> <td>
:'''Iterativ''':
Spannbaum T = null;
<b>for</b> alle v aus V[G]
Knoten(v);
Leader(v) = v;
<b>for</b> alle (u,v) aus E[G]
<b>if</b> ( Leader(u) != Leader(v) )
Leader(u) = v;
T = T + (u,v);
<b>return</b> T;
</td><td></td><td>
:'''Rekursiv''':
</td></tr></table>
==== Implementierung ====
<code id="4faa558938b10" hidden>
; DEFINITION DER KLASSE knoten
(define knoten%
(lambda (name)
(let
([leader name])
(let*
([set-leader!
(lambda (new-leader) (if (list? leader)
(set! leader leader)
(set! leader new-leader)))]
[get-leader!
(lambda () (if (list? leader)
(eval leader)
leader))])
(let
([dispatcher
(lambda (messagename)
(case messagename
((set-leader!) set-leader!)
((get-leader!) get-leader!)
(else #f)))])
(lambda (messagename . args)
(let*
([method (dispatcher messagename)])
(cond
[method (let ((result (apply method args)))
(cond
((not (eq? result 'rejected))result)
(else (error 'knoten% "~s is not applicble to ~s " messagename args))))]
[else (error 'knoten% "doesn't understand ~s" messagename)]))))))))
</code>
<code id="4fa11ae8c335f">
; INITIALISIERUNG ALLER KNOTEN
(define A (knoten% 'A))
(define B (knoten% 'B))
(define C (knoten% 'C))
(define D (knoten% 'D))
(define E (knoten% 'E))
; KRUSKAL ALGORITHMUS
(define kruskal
(lambda ()
; LISTE MIT ALLEN KANTEN NACH GRÖSSE GEORDNET
(let* ([kanten '(((A . C) 1)
((A . B) 2)
((A . D) 3) ((B . E) 3)
((B . C) 4) ((D . E) 4)
((C . D) 5) ((C . E) 5))])
; HILFSPROZEDUR
(letrec ([FIND (lambda (x)
(let ([fst (eval (car x))]
[snd (eval (cdr x))])
(not (eq? (fst 'get-leader!) (snd 'get-leader!)))))]
; PROZEDUR ZUR ERSTELLUNG DES BAUMES
[MST (lambda (kante)
(cond
[(eq? kante '()) '()]
[(FIND (caar kante)) ((eval ((eval (cdaar kante)) 'get-leader!)) 'set-leader! `(,(eval (caaar kante)) 'get-leader!))
((eval (cdaar kante)) 'set-leader! `(,(eval (caaar kante)) 'get-leader!))
(cons (car kante) (MST (cdr kante)))]
[else (MST (cdr kante))]))])
(MST kanten)))))
</code><run id="4fa11ae8c33da">(kruskal)</run>
Das Gewicht des minimalen Spannbaums lässt sich mit der oben erläuterten Scheme-Prozedur berechnen.
<run id="4fb23af8e79fc">(gewicht (kruskal))</run>
=== Algorithmus von Prim ===
[[Bild:Muessigd_Prim.gif|thumb|390px|right|Algorithmus von Prim Animation]]
Der Jarnik-Prim-Algorithmus für minimale Spannbäume ist dem Dijkstra Algorithmus für kürzeste Wege sehr ähnlich. Beginnend bei einem zufälligen Startknoten $s$, wächst der Baum zu einem minimalen Spannbaum durch das hinzufügen eines Knoten nach dem anderen.
==== Idee ====
Bei jeder Iteration ist $S$ die Menge der bereits zum minimalen Spannbaum hinzugefügten Knoten und der '''Schnitt''' $E'$ ist die Menge der Kanten die genau einen Endpunkt in $S$ haben. In jeder Wiederholung wird eine Kante minimalen Gewichts dem Baum hinzugefügt. Die größte Herausforderung ist es die Kante effizient zu finden.
==== Pseudocode ====
Der Folgende Pseudocode soll die Scheme-Prozedur veranschaulichen. Da diese ohne Seiteneffekte arbeitet wird bei jeder Iteration die Menge $S$ und $E'$ neu bestimmt. Die Prozedur '''verwendeteKnoten''' erstellt die Menge $S$ und die Prozedur '''moeglicheKanten''' erstellt die Menge $E'$. Als letztes sucht die Prozedur '''kuerztKante''' die Kante mit den minimalen Kosten. Dise wird dann dem MST hinzugefügt.
prim($V$,$E$,$ls$)
'''if''' length($V$) $-$ $1$ == length($ls$)
'''then return''' $ls$
'''else'''
'''if''' $ls$ == $null$
'''then''' $ls$ $\leftarrow{}$ kuerztKante(erstesElement($V$))
'''else''' $vls$ $\leftarrow{}$ verwendeteKnoten($ls$)
$mls$ $\leftarrow{}$ moeglicheKanten($vls$)
$ls$ $\leftarrow{}$ $ls +$ kuerztKante($mls$)
prim($V$,$E$,$ls$)
==== Implementierung ====
<code id="4fa51c55d805e">
(define Kn '(A B C D E F))
(define Ka '(((A . B) 1) ((B . E) 1) ((D . E) 1)
((C . F) 2)
((A . D) 3)
((E . F) 4) ((C . E) 4)
((B . D) 5)
((B . C) 6)))
(define Knotenmenge Kn)
(define Kantenmenge Ka)
</code>
<code id="4fb23af8e78c1" hidden>
(define mKanten
(lambda (lsKa lsvK)
(cond [(null? lsKa) lsKa]
[(null? lsvK) lsKa]
[(and (list? (member (caaar lsKa) lsvK)) (list? (member (cdaar lsKa) lsvK))) (mKanten (cdr lsKa) lsvK)]
[(not (or (list? (member (caaar lsKa) lsvK)) (list? (member (cdaar lsKa) lsvK)))) (mKanten (cdr lsKa) lsvK)]
[else (cons (car lsKa) (mKanten (cdr lsKa) lsvK))])))
(define vKnoten
(lambda (primls ergls)
(if
(= (length primls) 0)
(cons (car Knotenmenge) '())
(if
(= (length ergls) 0)
(vKnoten primls (cons (caaar primls) '()))
(if
(= (length primls) 1)
(cond [(null? primls) ergls]
[(not (list? (member (caaar primls) ergls))) (cons (caaar primls) ergls)]
[(not (list? (member (cdaar primls) ergls))) (cons (cdaar primls) ergls)])
(cond [(null? primls) ergls]
[(not (list? (member (caaar primls) ergls))) (vKnoten (cdr primls) (cons (caaar primls) ergls))]
[(not (list? (member (cdaar primls) ergls))) (vKnoten (cdr primls) (cons (cdaar primls) ergls))]))))))
(define kuerzt
(lambda (pruef)
(cond [(null? (cdr pruef)) (cons (car pruef) '())]
[(< (cadar pruef) (cadadr pruef)) (kuerzt (cons (car pruef) (cddr pruef)))]
[(>= (cadar pruef) (cadadr pruef)) (kuerzt (cdr pruef))])))
</code><code id="4fb23af8e794c">
(define prim
(lambda
(ls)
(if
(= (- (length Knotenmenge) 1) (length ls))
ls
(if
(= (length ls) 0)
(prim (kuerzt (mKanten Kantenmenge (vKnoten ls '()))))
(prim (append ls (kuerzt (mKanten Kantenmenge (vKnoten ls '())))))))))</code>
<run id="4fa51c55d80d8">(prim '())</run>
Das Gewicht des minimalen Spannbaums lässt sich mit der oben erläuterten Scheme-Prozedur berechnen.
<run id="4fb23af8e7a8b">(gewicht (prim '()))</run>
== Algorithmus von Sibeyn ==
== Anwendungen ==
Den minimalen Spannbaum kann man zum lösen vieler anderer Graphenprobleme verwenden. Im Folgenden sollen das Steinerbaumproblem und das Problem des Handelsreisenden erläutert werden.
=== Steinerbaumproblem ===
=== Touren des Handelsreisenden ===
== Bewertung und Vergleich ==
== Literatur ==