Minimale aufspannende Bäume
Inhaltsverzeichnis
Minimale aufspannende Bäume
Für eine Suche in Problemräumen gibt es mehere Möglichkeiten. Eine davon sind Minimale aufspannende Bäume.
Allgemeine Eigenschaften
Ziel von minimal aufspannenden Bäumen ist es alle Knoten direkt oder indirekt so miteinander zu verbinden, dass die gesamte Länge der Kanten (oder die Kosten) minimiert wird (werden).
Eine direkte Verbindung bedeutet das eine Kante zwischen 2 Knoten existiert, indirekt das ein Weg existiert der 2 Knoten über einen oder mehere Knoten miteinander verbindet.
Bei der Suche nach einer optimalen Lösung werden Knoten in jedem Schritt direkt miteinander verbunden.
Prim
Eine Möglichkeit um minimale aufspannende Bäume zu erzeugen ist der Prim-Algorithmus. Dieser Algorithmus führt immer zu einer optimalen Lösung.
Ablauf
1: Wähle einen willkürlichen Knoten und verbinde ihn mit dem nächstliegenden Nachbarn. Nächstliegende bedeutet, den Knoten mit der kürzesten Entfernenung oder der minimalen Kosten usw.
2: Wähle den noch nicht verbundenen Knoten aus der am nächsten an der Menge der verbunden Knoten liegt aus.
3: Wiederhole Schritt 2 solange bis alle Knoten verbunden sind
Bemerkung: Sollten mehere kürzeste Verbindungen existieren wird eine zufällige Verbindung ausgewählt.
Beispiel
Ausgangsproblem:
Schritt 1: Wähle Knoten 1 als willkürlichen Knoten und verbinde ihn mit dem nächsteligenden Knoten 3 mit Kosten von 2
Schritt 2: Als nächstliegender Knoten kommt nur Knoten 5 in Frage mit Kosten von 3
Schritt 3: Als nächstliegender Knoten kommt nur Knoten 2 in Frage mit Kosten von 3
Schritt 4: Als nächstliegender Knoten kommt nun Knoten 4 und 6 in Frage mit Kosten von 4. Wähle willkürlich Knoten 6.
Schritt 5: Als nächstliegender Knoten kommt nur noch Knaoten 4 in Frage mit Kosten von 4.
Alle Knoten sind minimal miteinander Verbunden. Nach Vorraussetzung des Algorithmus ist diese Lösung optimal.
Kruskal
Grundlage für den Kruskal-Algorithmus ist ein gewichteter, zusammenhängender, schleifenfreier und ungerichteter Graph G=[V,E,c] mit n Konten und m Kanten.
Ablauf
1: Sortiere und nummeriere alle Kanten ki von G in der Folge k1, k2,..., km mit monoton steigenden Gewicht c(ki), so dass c(k1)<= c(k2)<=...<=c(km).
2: Wiederhole für alle j, mit j=1,...,m:
Wähle die Kante kj und prüfe, ob durch Aufnahme von kj im Grpehn ein Zyklus entsteht. Wenn kein Zyklus entsteht setzte E:=E'U{kj}.
3: Stoppe, sobald E genau n-1 Kanten hat.
Der optimale minimal aufspannende Baum T= [V.E] wurde gefunden
Beispiel
Problem: Graph mit n=6 Knoten und m=10 Kanten. Für die optimale Lösungen werden n-1=5 Kanten benötigt.
Sotieren der Kanten:
Ausgangssituation:
Schritt 1: Anzahl der Kanten 1<5
Schritt 2: Anzahl der Kanten 2<5
Schritt 3: Anzahl der Kanten 3<5
Schritt 4: Anzahl der Kanten 3<5, da Zyklus
Schritt 5: Anzahl der Kanten 4<5
Schritt 5: Anzahl der Kanten 5=5
Optimale Lösung gefunden.
