Routenplaner

Der kürzeste Weg zum Ziel(die Mathematik im Routenplaner)

Sven O. Krumke, 13. Oktober 2005

[email protected]

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:


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:





Fall 2: K ist nicht eulersch

Der Satz von Euler

Satz von Euler:





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


A

B C

D E1

2

4

8

3

6

2

Permanent markierte Ecken

0

∞ ∞

∞∞

„unendlich“


A

B C

D E1

2

4

8

3

6

2


0

∞ ∞

∞∞


A

B C

D E1

2

4

8

3

6

2


0

∞ ∞

∞∞

A

0

4

1


A

B C

D E1

2

4

8

3

6

2


0

∞

∞

A

0

4

1

7

4


A

B C

D E1

2

4

8

3

6

2


0

∞

∞

A

0

4

1

D

1

7

4

3


A

B C

D E1

2

4

8

3

6

2


0

∞

A

0

1

D

1

7

4

3


A

B C

D E1

2

4

8

3

6

2


0

∞

A

0

1

D

1

7

4

3

B

3

5


A

B C

D E1

2

4

8

3

6

2


0

∞

A

0

1

D

1

5

4

3

B

3


A

B C

D E1

2

4

8

3

6

2


0

∞

A

0

1

D

1

5

4

3

B

3

E

4


A

B C

D E1

2

4

8

3

6

2


0

∞

A

0

1

D

1

5

4

3

B

3

E

4


A

B C

D E1

2

4

8

3

6

2


0

∞

A

0

1

D

1

5

4

3

B

3

E

4

C

5


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

Documents

Routenplaner