KIT � Institut für Theoretische Informatik 1

Algorithmen I

Prof. Jörn Müller-Quade

19.06.2017

Institut für Theoretische InformatikWeb:

https://crypto.iti.kit.edu/index.php?id=799

(Folien von Peter Sanders)

KIT � Institut für Theoretische Informatik 2

Mehr zu kürzesten Wegen

Viele Arbeiten zu besseren Prioritätslisten O(m+n log logn) [Thorup 2004]

I Mehrere Zielfunktionen abwägen

I Mehrere Ziele in beliebiger Reihenfolge anfahrensiehe auch Optimierungskapitel

I Mehrere disjunkte Wege

Fast alles schwierig (NP-schwer)

KIT � Institut für Theoretische Informatik 3

Exkurs: Routing in StraÿennetzwerkenStart: Beobachtungen zu Eigenschaften von Straÿennetzwerken

I groÿ, z.B. n =18 000 000 Knoten für Westeuropa

I dünn besetzt, z.B., m = Θ(n) Kanten

I beinahe planar, d.h., wenige Kanten kreuzen sich (Brücken)

I inhärente Hierarchie, schnellste Pfade benutzen wichtige Straÿen

KIT � Institut für Theoretische Informatik 4

Straÿennetzwerke

Gängige Anwendungen:

I Routenplanungssysteme im Internet, (z. B. maps.google.com)

I Fahrzeugnavigationssysteme

I Logistik

I Verkehrssimulationen

KIT � Institut für Theoretische Informatik 5

Distanz zu einem Zielknoten t

Was machen wir, wenn wir nur die Distanz von s zu einembestimmten Knoten t wissen wollen?

Trick 0: Dijkstra hört auf, wenn t aus Q entferntwird.Spart �im Durchschnitt� Hälfte der Scans.

ts

Frage: Wieviel spart es (meist) beim Europa-Navi?

KIT � Institut für Theoretische Informatik 6

Ideen für Routenplanungmehr in Algorithmen II, Algorithm Engineering

I Vorwärts- + Rückwärtssuche

ts

I Zielgerichtete Suche

ts

I Hierarchien ausnutzen

s t

I Teilabschnitte tabellieren

s z

Meist zentrale Idee: Vorberechnung amortisiert über viele Anfragen

KIT � Institut für Theoretische Informatik 7

Straÿennetzwerke

Wir konzentrieren uns aufStraÿennetzwerke.

I mehrere nützlicheEigenschaften, die sichausnutzen lassen

I viele reale Anwendungen

I einige Techniken: anwendbar fürö�entliche Verkehrsmittel

I die meisten Techniken: unklar, wienützlich sie für weitere Graphtypensind

KIT � Institut für Theoretische Informatik 8

Approach: Transit-Node Routing[Bast, Funke, Matijevic, Sanders, Schultes]

s t

KIT � Institut für Theoretische Informatik 9

BeispielKarlsruhe → Copenhagen

KIT � Institut für Theoretische Informatik 10

BeispielKarlsruhe → Berlin

KIT � Institut für Theoretische Informatik 11

BeispielKarlsruhe → Vienna

KIT � Institut für Theoretische Informatik 12

BeispielKarlsruhe → Munich

KIT � Institut für Theoretische Informatik 13

BeispielKarlsruhe → Rome

KIT � Institut für Theoretische Informatik 14

BeispielKarlsruhe → Paris

KIT � Institut für Theoretische Informatik 15

BeispielKarlsruhe → London

KIT � Institut für Theoretische Informatik 16

BeispielKarlsruhe → Brussels

KIT � Institut für Theoretische Informatik 17

BeispielKarlsruhe → Copenhagen

KIT � Institut für Theoretische Informatik 18

BeispielKarlsruhe → Berlin

KIT � Institut für Theoretische Informatik 19

BeispielKarlsruhe → Vienna

KIT � Institut für Theoretische Informatik 20

BeispielKarlsruhe → Munich

KIT � Institut für Theoretische Informatik 21

BeispielKarlsruhe → Rome

KIT � Institut für Theoretische Informatik 22

BeispielKarlsruhe → Paris

KIT � Institut für Theoretische Informatik 23

BeispielKarlsruhe → London

KIT � Institut für Theoretische Informatik 24

BeispielKarlsruhe → Brussels

KIT � Institut für Theoretische Informatik 25

Erste Beobachtung

Lange Strecken benutzen

nur wenige `wichtige' Zugänge zum Fernverkehrsnetzwerk,sog. access points

( wir können alle Zugangspunkte vorberechnen)

[in Europa: etwa 10 Zugangspunkte pro Knoten im Mittel]

KIT � Institut für Theoretische Informatik 26

BeispielKarlsruhe → Berlin

KIT � Institut für Theoretische Informatik 27

BeispielKarlsruhe → Berlin

KIT � Institut für Theoretische Informatik 28

BeispielKarlsruhe → Berlin

KIT � Institut für Theoretische Informatik 29

Zweite Beobachtung

Jeder Zugangspunkt ist für mehrere Knoten relevant.

Gesamtmenge aller Zugangspunkte ist klein,Transitknotenmenge

( wir können alle Abstände zwischen allen Transitknoten speichern)

[in Europa: ≈ 10 000 Transitknoten]

KIT � Institut für Theoretische Informatik 30

Transit-Node Routing

Preprocessing:

I Identi�ziere Transitknoten T ⊆ V

I Berechne |T |× |T | AbstandstabelleI Für jeden Knoten: identi�ziere Zugangsknoten

(Abbildung A : V → 2T ),speichere Abstände

Query (geg. Start s und Ziel t): berechne

dtop(s, t) := min{d(s,u)+d(u,v)+d(v , t) : u ∈ A(s),v ∈ A(t)}

KIT � Institut für Theoretische Informatik 31

Transit-Node Routing

Lokalitäts�lter:lokale Fälle aus�ltern ( Spezialbehandlung)

L : V ×V →{true, false}

¬L(s, t) impliziert d(s, t) = dtop(s, t)

KIT � Institut für Theoretische Informatik 32

Beispiel: Transitknoten

KIT � Institut für Theoretische Informatik 33

Experimente

I sehr schnelle Anfragen (queries)(4 µs, > 1 000 000 mal schneller als Dijkstra)

I Gewinner der 9. DIMACS Implementation Challenge

I erträglich: Vorberechnungszeiten (1:15 h) undSpeicherbedarf (247 bytes/Knoten)

I Neuere Werte: < 2µs, 5 Minuten PP, 150 Bytes/Knoten

s t

KIT � Institut für Theoretische Informatik 33

Experimente

I sehr schnelle Anfragen (queries)(4 µs, > 1 000 000 mal schneller als Dijkstra)

I Gewinner der 9. DIMACS Implementation Challenge

I erträglich: Vorberechnungszeiten (1:15 h) undSpeicherbedarf (247 bytes/Knoten)

I Neuere Werte: < 2µs, 5 Minuten PP, 150 Bytes/Knoten

s t

KIT � Institut für Theoretische Informatik 34

O�ene Fragen

I Wie bestimmt man die Transitknoten?

I Wie bestimmt man die Zugangsknoten e�zient?

I Wie bestimmt man die Lokalitäts�lter?

I Wie handhabt man lokale Anfragen?

Antwort:

I Andere Routenplanungstechniken benutzen!