Greedy:
Erstelle inkrementell eine L¨osung, bei der nicht
vorausschauend ein lokales Kriterium zur Wahl der jeweils n¨achsten
hinzuzufugenden L ¨ ¨osungskomponente verwendet wird.
Divide-and-Conquer:
Teile ein Problem in Teilprobleme auf. L¨ose
jedes Teilproblem unabh¨angig und kombiniere die L¨osung fur die ¨
Teilprobleme zu einer L¨osung fur das urspr ¨ ungliche Problem.
Greedy-Algorithmus:
- Eine Lösung wird schrittweise aufgebaut, in jedem Schritt wird
das Problem auf ein kleineres Problem reduziert. - Greedy-Prinzip: Fuge jeweils eine lokal am attraktivsten erscheinende Lösungskomponente hinzu.
- Einmal getätigte Entscheidungen werden nicht mehr
zuruckgenommen. - Meist einfach zu konstruieren und zu implementieren
- Kann eine optimale L¨osung liefern, muss es i.A. aber nicht.
Minimaler Spannbaum:
Ein minimaler Spannbaum (Minimum
Spanning Tree, MST) ist ein Teilgraph GT = (V, T) von G mit
gleicher Knotenmenge und einer Teilmenge der Kanten T ⊆ E,
sodass er ein aufspannender Baum mit minimaler Summe der
Kantengewichte ist.
Это такое дерево которое охватывает все кноты не при этом сумма кантей является минимальной
Kantenschnittlemma:
Sei S eine beliebige Teilmenge von Knoten
und sei e die minimal gewichtete Kante mit genau einem
Endknoten in S. Dann enthält der MST die Kante e.
Kreislemma:
Sei C ein beliebiger Kreis und sei f die maximal
gewichtete Kante in C. Dann enthält der MST f nicht.
Paritätslemma
Ein beliebiger Kreis und eine beliebige
Kantenschnittmenge haben eine gerade Anzahl von Kanten
gemeinsam
Algorithmus von Prim:
Starte mit einem beliebigen
Startknoten s. Fuge in jedem Schritt eine billigste Kante e zu
T hinzu, die genau einen noch nicht angebundenen Knoten
mit dem bisherigen Baum verbindet.
Prim und Kruskal bilden beide immer einen MST.
Algorithmus von Kruskal:
Starte mit T = ∅. Betrachte die
Kanten in aufsteigender Reihenfolge ihrer Kosten. Fuge Kante ¨
e nur dann zu T hinzu, wenn dadurch kein Kreis erzeugt wird.
Prim und Kruskal bilden beide immer einen MST.
Laufzeit von Kruskal:
- Union-Find-Operation ist praktisch in konstanter Zeit möglich,
d.h. der zweite Teil des Kruskal-Algorithmus hat nahezu
lineare Laufzeit. - Der Gesamtaufwand wird nun durch das Kantensortieren
bestimmt und ist somit O(m log n).
Laufzeit von Prim:
- Wird als Priority Queue ein klassischer Heap verwendet, dann
ist der Gesamtaufwand O(m logn) - Wird ein sogenannter Fibonacci-Heap verwendet, so reduziert
sich die Laufzeit auf O(m + n log n).
Prim und KruskalAnwendung in der Praxis:
- Fur dichte Graphen ( m = Θ(n^2)) ist Prims Algorithmus
besser geeignet. - Fur dunne Graphen ( ¨ m = Θ(n)) ist Kruskals Algorithmus
besser geeignet.
