Date post: | 05-Apr-2015 |
Category: |
Documents |
Upload: | annemarie-heinzer |
View: | 109 times |
Download: | 1 times |
Institut für Kartographie und GeoinformationProf. Dr. Lutz Plümer
Diskrete Mathematik IIVorlesung 1
SS 2001
Algorithmus von Dijkstra
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
2 2
Übersicht über das Semester
• zwei besonders wichtige Algorithmen für GIS– kürzeste Wege in einem Netz– Überlagerung von Netzen, Bestimmung aller Schnittpunkte
• effiziente Zugriffsstrukturen für räumliche Objekte
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
3 3
Übersicht Vorlesung I
• der kürzeste Weg von A nach B in einem Netz• Beispiel• Problemstellung• Animation des Algorithmus• Formulierung des Algorithmus in Pseudocode• erforderliche Datenstrukturen
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
4 4
Algorithmus von Dijkstra: Beispiel
Do
Ha
W
Du
K
D
15
8015
80
20
3020
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
6 6
Do
Ha
W
Du
K
D
20
15
80
80
20 30
15
Beispiel
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
7 7
Kürzeste Wege: Idee
• Gegeben: Gerichteter Graph, dessen Kanten mit Zahlen (Kosten, z.B. km oder min.) beschriftet sind
• Aufgabe: Berechnung des kürzesten Weges x z von einem Startknoten x zu einem Zielknoten z
• erste Idee: Berechne alle Wege und wähle den kürzesten
• Beobachtung: wenn der kürzeste Weg von x nach z über y führt, sind die Teilwege x y und y z ebenfalls kürzeste Wege
• effiziente Lösung: berechne alle kürzesten Wege und wähle den von x nach z aus
• Algorithmus von Dijkstra: jeder Schritt sitzt („Greedy“-Algorithmus)
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
8 8
Do
Ha
W
Du
K
D
20
15
80
80
20 30
15
Algorithmus von Dijkstra: Beispiel
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
9 9
Do
Ha
Du 20
80
20 30
W
K
D
8015
15
Do
Du
Ha
Do
Algorithmus von Dijkstra: Beispiel
MinimalerAbstand von Do
Du
80
Ha
20
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
10 10
Do
Ha
W
Du
K
D
20
80
80
20 30
15
15
W
Algorithmus von Dijkstra: Beispiel
Do
Du Ha
80 20
W
15
MinimalerAbstand von DO
Do
Ha
W
Du
K
D
20
80
80
20 30
15
15
W
Algorithmus von Dijkstra: Beispiel
abgearbeitet
noch in Arbeit
noch nicht betrachtet
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
12 12
Do
Du Ha
W
80 20
15
15
Do
Ha
W
Du
K
D
20
80
80
20 30
15
Bereits vorhanden Du
Kürzester Weg
Algorithmus von Dijkstra: Beispiel
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
13 13
Du
Do
Ha
W
20
15
15
Do
Ha
W
Du
K
D
20
80
80
20 30
15
K
D
Du
Algorithmus von Dijkstra: Beispiel
30
K
80
D
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
14 14
Du D K
Do
Ha
W
20
15
30 80
D
Do
Ha
W
Du
K
D
20
80
80
20 30
15
15
Bereits vorhanden
kürzester Weg
Algorithmus von Dijkstra: Beispiel
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
15 15
Du K
Do
Ha
W
D
20
15
30 80
D
Do
Ha
W
Du
K
D
20
80
80
20 30
15
15
Algorithmus von Dijkstra: Beispiel
20
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
16 16
20
Do
Ha
W
Du
K
D
80
80
20 30
15
15
Bereits vorhanden
Algorithmus von Dijkstra: Beispiel
kürzester WegDu K
Do
Ha
W
D
20
15
30 80
20
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
17 17
Do
Ha
W
Du
K
D
20
80
80
20 30
15
15
D
K
Algorithmus von Dijkstra: Beispiel
KDu
Do
Ha
W
D
20
15
30 80
20
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
18 18
Do
Ha
W
D
K
Du
20
15
30
20
K
Do
Ha
W
Du
D
20
80
80
20 30
15
15
D
KK
Algorithmus von Dijkstra: Beispiel
15
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
19 19
Formulierung des Algorithmus
Bezeichnungen
S Startknoten
K beliebiger Knoten im Graphen
dist (K) Abstand des Knotens K vom Startknoten S
GRÜN Knotenmenge
BLAU Knotenmenge
succ (K) Menge der Nachfolger(-Nachbarn) von K
für alle Elemente
dist (K, K‘) Distanz (Zeit) der Kante (K, K‘)
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
20 20
Formulierung des Algorithmus
algorithm Dijkstra (S)//berechne alle kürzesten Wege von S aus}
BLAU = ; GRÜN = {S}; dist(S) = 0;while( GRÜN ) {
wähle K GRÜN, so daß K‘ GRÜN:dist(K) dist(K‘);
färbe K blau;
for( Ki succ(K) ) { if (Ki (GRÜN BLAU) //noch nicht besuchter Knoten
färbe die Kante (K,Ki) rot;
färbe Ki grün;
dist(Ki) = dist(K) + dist(K,Ki); }
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
21 21
Formulierung des Algorithmus
dist(Ki) = dist(K) + dist(K,Ki); }
else {
if(Ki GRÜN) { // Ki erneut erreicht
if(dist(Ki) > dist(K) + dist(K,Ki)) {
färbe die Kante (K,Ki) rot;
färbe die bisher rote Kante zu Kigrün;
dist(Ki) = dist(K) + dist(K,Ki); }
else {
färbe (K,Ki) grün }}}
else {
färbe (K,Ki) grün }}} // ki BLAU
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
22 22
soweit der Algorithmus, aber ...
• wie finde ich schnell alle Nachfolger eines Knoten?– for( Ki succ(K) )...
• wie finde ich schnell– K GRÜN, so daß K‘ GRÜN:
dist(K) dist(K‘);
• Datenstruktur für den Graphen• Datenstruktur für die grünen (aktiven) Knoten• der schrittweise Entwurf des Algorithmus läßt diese
Fragen zunächst absichtlich offen• zugunsten der Konzentration auf die wesentliche Idee
Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 1
23 23
Ist der Algorithmus denn überhaupt korrekt?
• Für jeden grünen Knoten gilt:unter den rot-grünen Wegen ist der rote der kürzeste.
• Beweis: Induktion über die Folge der blau gefärbten Knoten
• Für jeden blauen Knoten gilt:unter allen Wegen ist der rote der kürzeste.
• Beweis: Induktion über die Folge der blau gefärbten Knoten
• Aufgabe: – Plausibilität am Beispiel
– versuchen Sie einen allgemeingültigen Beweis