View
4.193
Download
3
Category
Preview:
DESCRIPTION
Eine sehr geile Präsentation zum Thema Routenplaner. Wie funktioniert er und was ist die Mathematik dahinter?
Citation preview
Der kürzeste Weg zum Ziel(die Mathematik im Routenplaner)
Sven O. Krumke, 13. Oktober 2005
krumke@mathematik.uni-kl.de
Reiseplanung
Wie komme ich nach Halver?
Anforderungen
Wir wollen eine Antwort, die
• richtig
• schnell
• praktikabel
ist.
Überblick
• Kürzeste Wege
• Navigationsysteme
• Graphen und Netzwerke
• Algorithmen und Datenstrukturen
Kürzeste Wege I
Tell: Nennt mir den nächsten Weg nach Arth und KüssnachtFischer: Die offne Straße zieht sich über Steinen,
doch einen kürzern Weg und heimlichernkann Euch mein Knabe über Lowerz führen.
Kürzeste Wege II
Wege überhaupt
Theseus fand den Weg aus den Labyrinth dank eines Fadens von Ariadne.
Navigationssysteme
Navigation mit System
Lokalisation
Routenplanung
Lokalisation und Routenplanung
Lokalisation ist „einfach“ …
Bei der Routenplanung haben wir
• ca. 5 022 028 Kreuzungen
• ca. 6 169 904 Straßen
• ca. 10100 potentielle Reiserouten
Das Problem
Wie zum #!?*$!} können wir in1 Sekunde
einenkürzesten Weg
finden?
Vielleicht sollten wir mal die Mathematiker fragen?
Historisches
1736 suchten die Menschen in Königsberg einen Rundweg, der über alle 7 Brücken genau einmal führte.
Historisches
1736 suchten die Menschen in Königsberg einen Rundweg, der über alle 7 Brücken genau einmal führte.
Irgendwie geht das nicht!
Euler und die Graphentheorie
Leonhard Euler
D
C
B
A
Euler und die Graphentheorie
Leonhard Euler
D
C
B
A
Ein Graph besteht aus einer
• Menge von Ecken
• Menge von Kanten
Es gibt keinen Rundweg, weil alle Ecken ungeraden
Grad haben!
Satz von Euler:
Es gibt genau dann einen Rundweg, wenn G zsh. und alle Eckengrade gerade sind.
Der Satz von Euler
Satz von Euler:
Es gibt genau dann einen Rundweg, wenn G zsh. und alle Eckengrade gerade sind.
Zeige: Alle Eckengrade gerade es gibt Euler-Kreis
Betrachte längsten Kreis K in G
Fall 1: K ist eulersch
Der Satz von Euler
Satz von Euler:
Es gibt genau dann einen Rundweg, wenn G zsh. und alle Eckengrade gerade sind.
Zeige: Alle Eckengrade gerade es gibt Euler-Kreis
Betrachte längsten Kreis K in G
Fall 1: K ist eulersch
Fall 2: K ist nicht eulersch
Der Satz von Euler
Satz von Euler:
Es gibt genau dann einen Rundweg, wenn G zsh. und alle Eckengrade gerade sind.
Zeige: Alle Eckengrade gerade es gibt Euler-Kreis
Betrachte längsten Kreis K in G
Fall 1: K ist eulersch
Fall 2: K ist nicht eulersch
Neuer Kreis W
Es gibt einen längerenKreis als K!
Graphen
D
C
B
A D
C
B
A
ungerichteter Graph gerichteter Graph
In einem gerichteten Graphen G=(V,E) hat jede Kante (u,v)eine Richtung.
u v
Unser Problem in neuem Gewand
Gegeben: Gerichteter Graph G=(V,E)
• Start s, Ziel t
• Kantengewichte
Gesucht: ein kürzester s-t-Weg
A
B C
D E1
2
4
8
3
6
2s(start)
t(target)
Mr. Bruteforce
Hahahaha!
Mit meinem schnellen Computerprobiere ich einfach
alle Wege aus!
Ich weiss ja nicht …
Auf den Spuren des Zufalls
Wie viele s-t-Wege gibt es in einem zufälligen Graphen?
n Eckenfür jede der n(n-1) möglichen Kanten werfen wir eine Münze
?
?
?
??
?
Auf den Spuren des Zufalls
Wie viele s-t-Wege gibt es in einem zufälligen Graphen?
n Eckenfür jede der n(n-1) möglichen Kanten werfen wir eine Münze
Mögliche #Wege mit n-1 Kanten:
W‘keit, dass ein fester Weg existiert:
Erwartete Anzahl von Wegen:
Kopf gegen Kraft
Mit roher Kraft geht es wohl nicht!
Kürzester s-t-Weg = Kürzester s-z-Weg
+ Kürzester z-t-Weg
210
Kopf gegen Kraft (II)
• s ist von sich selbst 0 entfernt
• alle direkten Nachfolger von s sind 1 entfernt
• alle deren Nachfolger, die nicht 1 entfernt sind, sind 2 entfernt
• …
Der Algorithmus von Dijkstra
A
B C
D E1
2
4
8
3
6
2
Gesucht: Kürzester Weg von A nach C
Der Algorithmus von Dijkstra
A
B C
D E1
2
4
8
3
6
2
Permanent markierte Ecken
0
∞ ∞
∞∞
„unendlich“
Der Algorithmus von Dijkstra
A
B C
D E1
2
4
8
3
6
2
Permanent markierte Ecken
0
∞ ∞
∞∞
Der Algorithmus von Dijkstra
A
B C
D E1
2
4
8
3
6
2
Permanent markierte Ecken
0
∞ ∞
∞∞
A
0
4
1
Der Algorithmus von Dijkstra
A
B C
D E1
2
4
8
3
6
2
Permanent markierte Ecken
0
∞
∞
A
0
4
1
7
4
Der Algorithmus von Dijkstra
A
B C
D E1
2
4
8
3
6
2
Permanent markierte Ecken
0
∞
∞
A
0
4
1
D
1
7
4
3
Der Algorithmus von Dijkstra
A
B C
D E1
2
4
8
3
6
2
Permanent markierte Ecken
0
∞
A
0
1
D
1
7
4
3
Der Algorithmus von Dijkstra
A
B C
D E1
2
4
8
3
6
2
Permanent markierte Ecken
0
∞
A
0
1
D
1
7
4
3
B
3
5
Der Algorithmus von Dijkstra
A
B C
D E1
2
4
8
3
6
2
Permanent markierte Ecken
0
∞
A
0
1
D
1
5
4
3
B
3
Der Algorithmus von Dijkstra
A
B C
D E1
2
4
8
3
6
2
Permanent markierte Ecken
0
∞
A
0
1
D
1
5
4
3
B
3
E
4
Der Algorithmus von Dijkstra
A
B C
D E1
2
4
8
3
6
2
Permanent markierte Ecken
0
∞
A
0
1
D
1
5
4
3
B
3
E
4
Der Algorithmus von Dijkstra
A
B C
D E1
2
4
8
3
6
2
Permanent markierte Ecken
0
∞
A
0
1
D
1
5
4
3
B
3
E
4
C
5
Der Algorithmus von Dijkstra
A
B C
D E1
2
4
8
3
6
2
0
∞1
7
4
3• In jeder Iteration wird die nicht permanent markierte Ecke mit geringstem „Schlüsselwert“permanent markiert
• für alle ihre Nachfolger wird der Schlüsselwert angepasst
Gesamtaufwand(n Ecken und m Kanten):
Laufzeit des Algorithmus von Dijkstra
…
2C
3B
5A
SchlüsselwertEcke
2
Rechenzeit
1.5 h100.0000
…
0,0036s
0,0025s
0,0016s
0,0009s
0,0004s
366 Jahrhunderte
60
37,7 Jahre50
12,7 Tage40
17,9 min30
1s20
n
Rechenzeit
0
500
1000
1500
2000
2500
3000
3500
4000
4500
5000
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
Das muss doch noch besser gehen!
Haufenweise Haufen
Das Problem liegt hier!
Ein Heap (Haufen) hilft:
2
5 3
9 9 7 7
10 14 11 9 14
Kleinstes Element
(=Minimum)
„Höhe“ log n
Minimum: Zeit 1Verringern:
4
5
n mal Minimum
9
???????
Laufzeit „reloaded“
…2C
3B
5A
SchlüsselwertEcke
Rechenzeit
0
200
400
600
800
1000
1200
1400
1600
1800
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
Reihe2
Reihe1
Höhere Mathematik
Mit noch ausgeklügelterenAlgorithmen und Datenstrukturen kann man die Laufzeit weiter verringern.
Zusammenfassung
• Hinter dem Routenplaner steckt eine Menge Mathematik
• Denken ist besser als rohe Gewalt
• Netzwerkoptimierung:
Vielen Dank!
http://www.mathematik.uni-kl.de/~krumke
Recommended