05: Algorithmen II, Vorlesung, WS 2018/19, 29.10.2018
1 hour 29 minutes Posted Oct 30, 2018 at 9:50 am.
Start
Kürzeste Wege
Allgemeine Definition
Monotone ganzzahlige Prioritätslisten
Laufzeit Dijkstra mit Bucket-Queues
Radix-Heaps
Radix Heap: deleteMin
Beispiel
Laufzeit Dijkstra mit Radix-Heaps
Lineare Laufzeit für zufällige Kantengewichte
Änderung im Algorithmus für zufällige Kantengewichte
Analyse
All-Pairs Shortest Paths
Knotenpotenziale
Hilfsknoten
Definition der Potenziale
Algorithmus
Laufzeit
Distanz zu einem Zielknoten
Ideen für Routenplanung
Biderktionale Suche
A*-Suche
Benötigte Eigenschaften von f(v)
Wie finden wir f(v)?
Landmarks
Zusammenfassung: Kürzeste Wege
0:00
1:29:53
Show notes
05 |
Watch Video
