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.
