Minimale aufspannende Bäume: Unterschied zwischen den Versionen
| [gesichtete Version] | [Markierung ausstehend] |
K (Oua poganiuc verschob Seite Minimale aufspannende Bäume nach Minimale aufspannende Bäume) |
Braune (Diskussion | Beiträge) K |
||
| Zeile 5: | Zeile 5: | ||
==Allgemeine Eigenschaften== | ==Allgemeine Eigenschaften== | ||
| − | Ziel von minimal aufspannenden Bäumen ist es alle Knoten direkt oder indirekt | + | 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 | + | Eine direkte Verbindung bedeutet das eine Kante zwischen 2 Knoten existiert, indirekt das ein Weg existiert der 2 Knoten über einen oder mehrere Knoten miteinander verbindet. |
Bei der Suche nach einer optimalen Lösung werden Knoten in jedem Schritt direkt miteinander verbunden. | Bei der Suche nach einer optimalen Lösung werden Knoten in jedem Schritt direkt miteinander verbunden. | ||
| Zeile 18: | Zeile 18: | ||
1: | 1: | ||
| − | Wähle einen willkürlichen Knoten und verbinde ihn mit dem nächstliegenden Nachbarn. Nächstliegende bedeutet, den Knoten mit der kürzesten | + | Wähle einen willkürlichen Knoten und verbinde ihn mit dem nächstliegenden Nachbarn. Nächstliegende bedeutet, den Knoten mit der kürzesten Entfernung oder der minimalen Kosten usw. |
2: | 2: | ||
| Zeile 27: | Zeile 27: | ||
Bemerkung: | Bemerkung: | ||
| − | Sollten | + | Sollten mehrere kürzeste Verbindungen existieren wird eine zufällige Verbindung ausgewählt. |
===Beispiel=== | ===Beispiel=== | ||
| Zeile 35: | Zeile 35: | ||
[[image:BSP_MSP_Problem.jpg]] | [[image:BSP_MSP_Problem.jpg]] | ||
| − | Schritt 1: Wähle Knoten 1 als willkürlichen Knoten und verbinde ihn mit dem | + | Schritt 1: Wähle Knoten 1 als willkürlichen Knoten und verbinde ihn mit dem nächstliegenden Knoten 3 mit Kosten von 2 |
[[image:BSP_Prim_1.jpg]] | [[image:BSP_Prim_1.jpg]] | ||
| Zeile 51: | Zeile 51: | ||
[[image:BSP_Prim_4.jpg]] | [[image:BSP_Prim_4.jpg]] | ||
| − | Schritt 5: Als nächstliegender Knoten kommt nur noch | + | Schritt 5: Als nächstliegender Knoten kommt nur noch Knoten 4 in Frage mit Kosten von 4. |
[[image:BSP_Prim_5.jpg]] | [[image:BSP_Prim_5.jpg]] | ||
| − | Alle Knoten sind minimal miteinander Verbunden. Nach | + | Alle Knoten sind minimal miteinander Verbunden. Nach Voraussetzung des Algorithmus ist diese Lösung optimal. |
==Kruskal== | ==Kruskal== | ||
| Zeile 66: | Zeile 66: | ||
2: Wiederhole für alle j, mit j=1,...,m: | 2: Wiederhole für alle j, mit j=1,...,m: | ||
| − | Wähle die Kante kj und prüfe, ob durch Aufnahme von kj im | + | Wähle die Kante kj und prüfe, ob durch Aufnahme von kj im Graphen ein Zyklus entsteht. Wenn kein Zyklus entsteht setzte E:=E'U{kj}. |
3: Stoppe, sobald E genau n-1 Kanten hat. | 3: Stoppe, sobald E genau n-1 Kanten hat. | ||
Aktuelle Version vom 20. Juni 2013, 17:21 Uhr
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 mehrere 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 Entfernung 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 mehrere 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ächstliegenden 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 Knoten 4 in Frage mit Kosten von 4.
Alle Knoten sind minimal miteinander Verbunden. Nach Voraussetzung 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 Graphen 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.
