- 1
- eventuell leer
- 2
- nicht zu verwechseln mit
voll: entweder Blatt oder genau zwei geordnete Kinder.
Vollständig heißt, es gibt keine teilgefüllten ``Ebenen'' des Baumes.
Falls nicht die passende Anzahl von elementen vorganden sind, kann
man sich die Letzte Reihe mit leeren Knoten aufgefüllt
denken, insofern ist auch die letzte Ebene gef"ullt.
- 3
- 'a Btree = Leaf | Node of ('a Btree *
'a * 'a Btree) oder, genauer auch 'a Btree = Leaf of 'a |
Node of ('a Btree * 'a * 'a Btree), was mehr
[CLR90] entspricht
- 4
- Länge des Arrays
l = 2n -1 mit 2n - 1 ³ heapsize für minimales n. Da
die letzte Ebene teilgefüllt sein kann ist streng genommen der Baum
nicht mehr vollständig, zumindest auf den ersten Blick. Nach der
Sichtweise von [CLR90], Ist ein Knoten
mit Verweisen auf 2 Kindern als Nil-Pointer kein Blatt, sondern hat
zwei leere Knoten als Kindern, die dann die Blätter darstellen. Die
Sprechweise in [CLR90] ist auf
jedenfall nicht 100% konsistent, denn wenn jeder Knoten auf jeden fall
noch 2 nil-Kinder hat, dann ist wiederum der Baum nicht vollkommen
balanciert.
- 5
- es gibt daneben
Durchlaufen in Präordnung und Postordnung.
- 6
- Beachte: die rekursive L"osung
ist endrekursiv.
- 7
- Wenn die Schlüssel alle
unterschiedlich sind, gilt für die beiden ersten Ungleichungen
schärfer < anstelle £. Die erste Ungleichung gilt nur
falls das linke Kind existiert.
- 8
- einfacher Pfad: alle Knoten (des Pfades)
unterschiedlich. Falls die Pfade nur von der Eltern zu den Kindern
erlaubt sind, sind alle Pfade einfach!
- 9
- = Länge des kürzesten Pfades von s zum Knoten,
falls unerreichbar, Abstand = ¥.
- 10
- Daß man 2 Farben braucht, sollte klar sein, die
dritte kennzeichnet Knoten die man bereits entdeckt hat, deren
adjazierene Knoten man aber noch nicht kennt. Wg. Breitenstrategie
arbeitet man die Nachbarn eines neuentdeckten Knotens nicht sofort ab.
Das sind die grauen Knoten.
- 11
- graue Knoten: auf der ``Grenze'' der Breitensuche:
ein schwarzer Knoten kann nie einem weißen benachbart sein.
- 12
- Queue-Operationen enqueue und
dequeue kosten O(1), siehe
Kapitel 5.
- 13
- der vorgestellte
Algorithmus wendet dies auf alle Knoten der Reihe nach an, das ist aber
nicht zentral. Die eigentliche Tiefensuche ist DFS-Visit.
- 14
- Ein
weißer Pfad ist ein Pfad, der nur weiße Knoten enthält.
- 15
- sonst wäre v ein
Vorfahre; damit h"atten wir eine Rückwärtskante, was der Annahme der
Kreisfreiheit widerspricht.
- 16
- Sei G = (V, E) gegeben, dann ist Gt = (V, Et)
wobei (v, u) Î Et, gdw. (u,v) Î E. Die starken
Zusammenhangskomponenten von G und Gt stimmen
überein.
- 17
- jeder von jedem
erreichbar. Zum Vergleich mit den starken Zusammenhangskomponenten: der
Graph ist hier ungerichtet!
- 18
- Es kann natürlich
mehrere leichte/minimale Kanten geben.
- 19
- unter der
Voraussetzung, daß a(E,V) = O(logE), z.B.,
heap-Implementierung.
- 20
- genauer: alle
anderen Bäume des Waldes sind nur Einzelknoten.
- 21
- es kann mehrere Bäume mit
kürzesten Pfaden geben. In der Regel will man einen davon.
- 22
- Vergleiche Breitensuche und
Vorgängergraph. Der Vorgängergraph des
Breitensuchalgorithmus entspricht für den Spezialfall, daß alle
Kanten das Gewicht 1 haben, den Baum der
kürzesten Pfade.
- 23
- extrahieren kostet O(V) (z.B.
Arrayimplementierung), wenn man nicht noch Zusatzannahmen macht.
- 24
- konkrete Beispiele aus der Vorlesung: Problem der
k"urzesten Pfade. Speziell f"ur D&C: Quicksort, Mergesort.
- 25
- nach
Leonardo von Pisa, ``Sohn des Bonacci'' [dPF02].
- 26
- Das Beispiel wird manchmal mi"sinterpretiert als:
``Fibonacci zeigt, wieviel schlechter rekursive L"osungen gegen"uber
iterativen sind''. Das ist hier nicht der Punkt. Man erh"alt eine
effiziente rekursive L"osung mittels
Parameterakkumulation.
- 27
- Punkt 1 und 2 des Vorgehens
bei DP
- 28
- zweifache Schleife,
eine f"ur min, eine f"ur die Summe.
- 29
- der Algorithmus l"auft
tats"achlich mit nur mit O(k n2), denn bei der Berechnung
der Summen åj=i+1n si kann man ebenfalls sparen, in dem
man Teilsummen wiederverwendet.
- 30
- Die Wahl
der Strategie h"angt nat"urlich auch von der Struktur des Problems ab;
wenn man keine speziellen Eigenschaften des Suchraums kennt/ausnutzen
will, ist Tiefensuche meist die erste Wahl, Breitensuche eher selten.
- 31
- Anwendbar meint: im Prinzip
anwendbar, aber das faktorielle Wachstum macht das Problem
``unbehandelbar'' (intractable).
- 32
- die
charakteristische Funktion
- 33
- die Abst"ande/Kosten seien als immer ³ 0
angenommen
- 34
- Es gibt Algorithmen, die Gausselimination in
O(b n2) machen, wobei b die Bandbreite ist.
- 35
- man kennt nichtmal
Approximationen mit garantierter G"ute. Allerdings gibt es ad-hoc
Heuristiken
- 36
- von denen sehr
viele ``hart'' sind
- 37
- zumindest
komplexit"atsm"a"sig
- 38
- alternativ: gibt es eine Rundreise mit Kosten £
k