Gesamter Stoff von Termin 01 enthält wichtige Grundlagen

• Welches Grundproblem behandelt die Vorlesung Routenplanung?
• Wie ist der Grobaufbau der meisten Beschleunigungstechniken?
  • Vorberechnungsphase: Graph ist bekannt, Start- und Ziel unbekannt. Relativ viel Rechenzeit und Speicher verfügbar. Aufgabe: Berechne Hilfsdaten für Anfragephase
  • Anfragephase: Graph und Hilfsdaten, sowie Start und Ziel bekannt. Berechne Distanz von Start zum Ziel (schnell!).
  • Anwendungsszenario: Server-Andwendung, die viele Anfragen bearbeiten muss.
• Wie können Graphen im Computer repräsentiert werden?

Dijkstras Algorithmus

• Wie funktioniert Dijkstras Algorithmus?
• Wie funktioniert Dijkstras Algorithmus mit Abbruchkriterium?
• Welches Implementationsproblem bleibt bei Dijkstra's Algorithmus mit Abbruchkriterium, wie kann dieses gelöst werden?
  • Vorinitialisierung aller Distanzen teuer, Lösung über timestamps.
• Wie beeinflusst die Wahl der Prioritätswarteschlange Dijkstras Algorithmus?
  • Fibonacci-Heap: Gute theoretische Laufzeit
  • Binärheap: Praktisch schnelle Implementation

Exkurs

• Welche drei Probleme unterscheiden wir im Exkurs?
  • Positive Kantengewichte, negative Kantengewichte ohne negative Zyklen, negative Kantengewichte
  • Welche davon können effizient gelöst werden und womit?
  • Wie funktioniert der Bellman-Ford Algorithmus?

Bidirektionale Suche

• Wie funktioniert Bidirektionale Suche?
• Welche Wechselstrategien gibt es?
  • Prinzipiell beliebige Strategien möglich
  • Distanzbalanziert
  • Streng alternierend
• Welche Abbruchkriterien gibt es?
• Welche Beschleunigung kann man erreichen?
  • Prinzipiell beliebig gut oder schlecht
  • Auf Straßengraphen etwa Faktor zwei
• Welche Bedeutung hat bidirektionale Suche?
  • Geringe Beschleunigung aber wichtiger Bestandteil von fortgeschrittenen Beschleunigungstechniken

A-Star Algorithmus (Zielgerichtete Suche)

• Welche Intuition steckt hinter dem A-Star Algorithmus?
  • Reihenfolge der besuchten Knoten ändern, Suche stärker zum Ziel lenken.
• Wie funktioniert der A-Star Algorithmus (Zielgerichtete Suche)?
• Welche Potentiale dürfen beim A-Star Algorithmus benutzt werden und wieso?
• Was ist die äquivalente Formulierung?
• Was ist ein zulässiges Potential pi mit pi(t)=0?
  • untere Schranke für Distanz zum Ziel
• Wie können aus zwei Potentialen ein (heuristisch) stärkeres Potential konstruiert werden?
  • Knotenweise Maximumsbildung

ALT

• Welches Potential benutzt der ALT-Algorithmus?
• Welche Intuition gibt es für den Suchraum von Dijkstra's Algorithmus und ALT
  • Dijkstra: Graphentheoretischer Kreis, ALT: Schnitt aus (pro Landmarke je ein) graphentheoretische Hyperbel und Ellipse
• Welche Vor- und Nachteile hat der Einsatz von einer großen Menge von Landmarken?
  • Vorteil: Starke Potentiale
  • Nachteil: Evaluierung (zur Laufzeit) von vielen Landmarken ist teuer
• Wie kann man den Nachteil „Evaluierung (zur Laufzeit) von vielen Landmarken ist teuer“ umgehen?
  • Landmarkenselektion zur Laufzeit
• Wie funktioniert (ganz grob) Landmarkenselektion?
  • Dynamische Wahl der Landmarken in der Anfrage
  • Anstatt zur Laufzeit mit allen vorberechneten Landmarken zu arbeiten werden immer nur ein paar (heuristisch als gut erkannte) Landmarken benutzt

• Wie werden gute Landmarken gewählt?
  • Viele Heuristiken möglich
  • Intuition: Landmarken die geometrisch in einer Linie entweder vor dem Start oder hinter dem Ziel liegen sind gut. Deswegen suche den „Rand des Graphen“
  • Prüfungsrelevante Strategien: Farthest-Landmarken und Planar-Landmarken

• Wie funktioniert bidirektionaler ALT?
  • Möglichkeit 1: Benutze 2 verschiedene Potentiale (Vorwärtspotential und Rückwärtspotential). Dafür schlechteres Abbruchkriterium.
  • Möglichkeit 2: Konstruiere aus Vor- und Rückwärtspotential ein gemeinsames (wahrscheinlich schwächeres Potential). Dafür besseres Abbruchkriterium.

• Was ist der Dijkstra Rank?
  • Definition: Siehe Folien. Interpretation: Maß für die Lokalität zweier Knoten
• Wieso und wofür benutzt man den Dijkstra Rank?
  • Bewerte die Lokalität einer Anfrage. Wichtig, weil Beschleunigung je nach Lokalität sehr unterschiedlich sein kann. Auswertung der Beschleunigung je nach Dijkstra Rank erlaubt genauere Interpretation der Wirksamkeit einer Technik.

• Welche Grundidee steckt hinter geometrischen Containern / Arc-Flags?
  • In Vorberechnung Kanten als unwichtig für gewisse Anfragen erkennen und diese Kanten in der Anfrage ignorieren (nicht relaxieren)
  • Arc-Flags können als zielgerichtete und hierarchische Technik angesehen werden.

• Wie funktionieren Geometrische Container?
  • Wichtig: (2-dimensionale) Zeichnung des Graphen vorhanden.
  • Vorberechnungsphase: Für jeder Kante (u,v) wird ein geometrisches Objekt C(u,v) vorberechnet und gespeichert, das alle Knoten enthält, die auf einem kürzesten Weg liegen, der mit (u,v) beginnt.
  • Anfrage: Benutze nur Kanten (u,v), für die der Zielknoten in C(u,v) liegt
• Wo ist ein Trade-Off in der Wahl der geometrischen Objekte
  • Für einfache geometrischen Objekte kann zur Laufzeit schnell überprüft werden, ob ein Knoten enthalten ist. Dafür enthalten Sie möglicherweise viel zu viele Knoten. Für komplexe geometrische Objekte verhält es sich gegenteilig. Einfache, achsenparallele Rechtecke haben sich experimentell als gut herausgestellt.
• Wie funktioniert eine Arc-Flags-Query?
• Wie berechnet man gültige Arc-Flags vor?
  • Viele Heuristiken. Geometrische Verfahren versuchen möglichst kompakte Zellen ähnlicher Größe zu finden (es ist nicht notwendig zu Wissen wie ein kd-Baum oder ein Quad-Baum konstruiert wird)
  • Laufzeit der Vorberechnung abhängig von Anzahl der Randknoten (Knoten mit einem Nachbar in einer anderen Zelle). Black-Box-Partitionierer versuchen balancierte, kleine Schnitte zu finden (balanciert: ähnliche Zellen-Anzahl, kleiner Schnitt: wenige Kanten mit Endknoten in verschiedenen Zellen)
• Welche Vorschläge/Verfahren gibt es zur Wahl der Arc-Flag Zellen?
• Was ist der Coning-Effekt bei Arc-Flags?
  • Aufspreizen des Suchraums kurz vor der Zielzelle, kein Nutzen der Arc-Flags innerhalb der Zielzelle
• Wie kann der Coning-Effekt abgeschwächt werden?
  • Bidirektionale Arc-Flag Suche
  • Multi-Level Arc-Flags

• Wie funktionieren Bidirektionale Arc-Flags?
  • Wie bidirektionale Suche. Berechne Vorwärts- und Rückwärtsflaggen vor. Benutze nur Kanten, deren entsprechende Flaggen wahr sind.
• Wie funktionieren Multi-Level Arc-Flags?

• Auf welcher Grundbeobachtung basiert Transit-Node-Routing?
  • Für Straßengraphen gilt: Es gibt eine relativ kleine Menge T von Punkten, so dass (fast) alle lange kürzeste Wege einen Punkt aus T nahe am Start einen Punkt aus P nahe am Ziel besitzen.
  • Intuition für T: Autobahnauffahrten

• Wie ist die allgemeine Vorgehensweise bei einer Transit-Node-Routing Anfrage?
• Wie (grob) funktioniert die geometrische Transit-Node-Routing-Variante?
• Wie (grob) funktioniert mehrstufiges Transit-Node-Routing?
• Was ist der Trick bei mehrstufigem Transit-Node-Routing?

• Bis jetzt haben wir immer nur Distanzen berechnet. Wie kann man die zugrundeliegenden kürzesten Wege konstruieren?
  • Prinzipiell können alle behandelten Verfahren so abgeändert werden, dies bei der Query maßgeschneidert mitzuberechnen / vorzuspeichern. Dabei muss für jede Technik separat argumentiert werden.
  • Allgemeines (nicht ganz so schnelles Verfahren): Hat man einen Graphen mit beschränktem Knotengrad und ein sehr schnelles Verfahren zur Berechnung von Distanzen, so kann dies wie folgt benutzt werden um kürzeste Wege zu berechnen:
    • Starte mit dem Weg P=<s>
    • Solange für den Weg P=(v1, …, vk) nicht vk=t ist
      • für alle ausgehenden Kanten (vk,w) von vk
        • Wenn dist(s,vk)+len(vk,w)+dist(w,t)=dist(s,t) dann füge w an P an und breche die Schleife ab

Multilevel-Overlay Graph

• Was ist der Overlay Graph eines Eingabegraphen (zusammen mit Level-Sequenz)?
• Wie funktioniert die Vorberechnung Multilevel-Overlay-Technik?
• Wie funktioniert die Query der Multilevel-Overlay-Technik?
• Welche Möglichkeiten gibt es um die Knoten für den nächsten Level auszuwählen?
  • Eigentlich beliebige Strategien möglich
  • Experimentell gut: Finde zentrale Knoten, finde gute Separatoren
• Wie kann man mit der MOL-Technik mit verschiedenen Metriken umgehen?
  • (Strategie aus Customizable Route Plannung, SEA11)
  • Benutze gute Separatoren als Knoten für nächsten Level
  • Behalte Knotenwahl bei Änderung der Metrik bei, aber berechne Overlay-Graph neu
  • Strategie ist praktikabel falls Separatoren und Graph hinreichend gut

Contraction Hierarchies

• Was ist Knotenkontraktion?
• Wie funktioniert die Contraction Hierarchies Vorberechnung?
• Was ist die Ausgabe der Contraction Hierarchies Vorberechnung?
• Wie funktioniert die Contraction Hierarchies Anfrage?
• Wie wird die Reihenfolge bestimmt, in der in der CH-Technik Knoten kontrahiert werden?
  • Heuristische Vorgehensweise: Jedem Knoten werden Kosten zugewießen, wähle beliebigen Knoten mit kleinsten Kosten. Die Kosten sind ein gewichtetes Mittel aus verschiedenen Werten wie Anzahl der schon gelöschten Nachbarn, Betweenness-Wert des Knoten und Anzahl der Kanten die eingefügt werden müssen wenn der Knoten kontrahiert wird.

• Wie ist der Reach-Wert eines Knotens (bzgl eines Graphs) definiert?
• Wie berechnet man Reach-Werte (auf kanonische Art)?
  • Dijkstra für jeden Knoten im Graphen
• Wie funktioniert die Bidirectional Self-Bounding Reach-Dijkstra Query?
• Wie funktioniert die Bidirectional Distance-Bounding Reach-Dijkstra Query?
• Wie kann man die lange Vorberechnung beschleunigen?
  • Berechnung von oberen Schranken anstatt exakter Reach-Werte.
• Wie (grob) funktioniert die schnelle Vorberechnung von oberen Schranken für Reach-Werte?
  • Hauptzutaten: Iteratives Vorgehen, in jedem Schritt:
  • Berechne Reach-Werte von Kanten mit Reach kleiner einem bestimmten Wert durch beschränkte Kürzeste-Wege-Bäume
  • Lösche diese Kanten
  • Berücksichtige gelöschte Kanten durch Penalties
  • Zusätzlich: Benutze Shortcuts/Graphkontraktion
• Welche weitere Verbesserung gibt es?
  • Kombination mit ALT. Doppelter Nutzen: Schärfere Schranken für Pruning und zusätzliche Zielrichtung.

• Wieso ist die Berechnung eines Kürze-Wege-Baums durch Dijkstra's Algorithmus viel langsamer als man erwarten würde?
  • Flaschenhals ist nicht Prozessorgeschwindigkeit sondern Bandbreite des Transfers vom Speicher zum Prozessor
• Was „macht“ der Phast-Algorithmus
  • Schnelle Berechnung von Kürzeste-Wege-Bäumen nach kurzer Vorberechnungsphase
  • Dies erlaubt auch schnelles APSP
• Wie funktioniert der PHAST-Algorithmus?
  • Vorberechnung: Wie Contraction Hierarchies
  • Berechnung eines konkreten Kürzeste-Wege-Baums:
    • Erst gewöhnliche Aufwärtssuche in Contraction Hierarchy
    • Dann Abwärtssuche in Contraction Hierarchy als Sweep in vorher festgelegter Reihenfolge
• Welche Vorteile hat der PHAST-Algorithmus?
  • Der größte Teil der Query (Abwärts-Teil) benötigt keine Priority-Queue mehr
  • Ermöglicht Cache-effiziente Implementierung durch vorher festgelegte Knotenreihenfolge/Neuordnung für die Abwärtssuche
  • Erlaubt Parallelisierung (der Abwärtssuche, die Aufwärtssuche ist Laufzeit-unkritisch)
  • Gut für GPU parallelisierbar
• Für welche Graphen funktioniert das Verfahren?
  • Mehrere Sichtweisen möglich
  • Eine mögliche Sichtweise: Contraction Hierarchie des Eingabegraphen besitzt nur Wege mit relativ wenigen Knoten („besitzt also wenige level“, ist „flach und breit“)

• Kein prüfungsrelevanter Stoff

Die do-it-yourself Vorlesung war ein Versuch rauszufinden, ob dieser Vorlesungs-Modus sinnvoll eingesetzt werden kann (Ergebnis: Würde ich nicht nochmal so machen). Deswegen sind nur untenstehende Fragen prüfungsrelevant:

Dissertation Daniel Delling

• Wie funktioniert Multikriterieller Dijkstra?

Car or Public Transport – Two Worlds

• (Dieses Papier ist sehr lesenswert!)
• Welche grundlegenden Techniken gibt es in der gewöhnlichen Routenplanung?
  • Bidirektionale Suche, Hierarchie, Shortcuts/Kontraktion, Zielrichtung, Distanztabellen

Fast Routing in Very Large Public Transportation Networks using Transfer Patterns

• Wie lassen sich Public Transportation Networks modellieren?

• Was muss man bei der theoretischen Betrachtung von Algorithm Engineering Ansätzen betrachten?
  • Interpretation wichtig, Modell muss zur Aufgabenstellung passen
  • so knapp wie möglich, so ausführlich wie nötig: Genau die wichtigen Aspekte sollten enthalten sein
• Welche theoretische Fragestellung wurde in der Vorlesung behandelt?
  • Komplexität der Vorberechnungsphase von vielen Beschleunigungstechniken.
  • Wie schwer ist es, den Freiheitsgrad der Vorberechnung so zu füllen, dass der durchschnittliche Suchraum von gleichverteilt zufälligen Anfragen minimal wird.
  • Ergebnis: NP-schwer für alle betrachteten Techniken. Dies rechtfertigt den Einsatz von Heuristiken.
• Wie funktioniert das in der Vorlesung behandelte Modell von Contraction Hierarchies?
  • Suchraum wird in besuchten Knoten gemessen.
  • Ausgangsposition: „Echter Algorithmus“
  • In Vorberechnung, vereinfache Kontraktion zu „scharfer Kontraktion“. Füge nur Kanten ein, die unbedingt notwendig sind.
  • In Anfrage: Relaxiere Abbruchkriterium (macht Anfrage ungefähr Faktor 2 schlechter). Damit auch Strategie für Wechseln der beiden Suchen egal. Außerdem benutze kein stall-on-demand (nicht wichtig zu wissen, was stall-on-demand ist)
  • Ergebnis: Anfragesuchraum kann sehr einfach dargestellt werden (Formel siehe Folien)
• Welche (groben) Ansätze zur Generierung von synthetischen Straßennetzwerken haben wir gesehen?
  • Ansatz 1: Ansatz über Voronoipartitionierung. Wähle ausgehend von einer beliebigen Voronoipartionierung zufällig Zellen und zerlege diese weiter in Voronoizellen. Dünne das Ergebnis aus.
  • Ansatz 2: Versuche die Entstehung von Straßennetzwerken nachzuahmen: Füge iterativ neue Knoten zu einem Netzwerk hinzu und verbinde diese mit nahen Nachbarn. Modelliere dabei Knoten verschiedener Wichtigkeit hinzu. Neue Knoten die weit entfernt von wichtigen Knoten auftauchen werden auch wichtig.

• Was sind die Vor- und Nachteile der Einzelnen Techniken (Landmarken, Bidirektionale Suche, Kontraktion, Arc-Flags, Distanztabellen)
• Welche Kombinationen lohnen sich also anzuschauen?

• Wie funktioniert Core-ALT, und worauf muss man achten wenn das Ziel nicht im Core enthalten ist?
• Wie funktioniert SHARC (welchen Nachteil welcher Technik versucht man damit auszubessern?)?
• Was ist Flaggenverfeinerung? Wozu Flaggenverfeinerung?
• Was sind partielle Flaggen? Wozu partielle Flaggen?
• Was ist die Motivation von CHASE? Wie funktioniert CHASE?
• Was ist das Hauptproblem von CHASE, wenn man einfach Arc-Flags auf dem Suchgraphen einer CH berechnen würde?
• Lösungsansatz?
• Wie kann man Transit-Node-Routing noch weiter beschleunigen?

• Welche Szenarien fallen unter „Zeitabhängige Routenplanung“?
• Was ist der grundlegende Unterschied zu zeitunabhängiger Routenplanung bei der Modellierung?

• Was ist eine Travel-Time Funktion? Welche zwei „Arten“ von Funktionen haben wir betrachtet?
• Was ist die FIFO-Eigenschaft?
• Warum muss man darauf achten, dass alle Kanten im Graphen die FIFO-Eigenschaft erfüllen?
• Wie haben wir die Graph-Datenstruktur erweitert um Travel-Time Funktionen zu unterstützen?

• Welche Anfrageszenarien haben wir im zeitabhängigen Fall betrachtet?
• Wie kann man Zeit-Anfragen berechnen? Was ist der Unterschied zu Dijkstra's Algorithmus?
• Was ist ein Algorithmus für Profil-Anfragen? Welchen Unterschied hat er zu Dijkstra?
• Warum verliert der Label-Correcting-Algorithmus die Label-Setting-Eigenschaft bei Profilsuchen überhaupt?

• Welche Operationen auf Travel-Time-Funktionen haben wir betrachtet?
• Was ist der Unterschied zwischen Auswertung bei Straße und Schiene?
• Wie ist die Komplexität von Auswertung, Linken und Merge?
• Wieviel Interpolationspunkte können in einer gelinkten bzw. gemergten Funktion enthalten sein (Straße bzw. Schiene)?
• Warum ist intuitiv das Linken bei Schienenfunktionen „gutmütiger“?

• Warum funktionieren Profilsuchen in der Praxis nicht (gut) auf Straßennetzen?

• Welche Bausteine (von Beschleunigungstechniken) lassen sich gut auf den zeitabhängigen Fall übertragen?

• Wie kann man ALT anpassen?
• Warum ist es korrekt auf dem Lower-Bound-Graphen die Distanzen vorzuberechnen?
• Warum funktioniert Time-Dependent ALT nicht gut auf Eisenbahnnetzen?

• Warum funktionieren bidirektionale Zeit-Anfragen nicht?
• Wie kann man eine bidirektionale Profilsuche berechnen? Wann darf man die Suche abbrechen?

• Was ist eine Korridorsuche? Wozu kann man sie benutzen?
• Wie kann man Kontraktion anpassen (Knoten- und Kantenreduktion)?
• Was ist das Hauptproblem bei der Kantenreduktion?
• Welche zwei Ansätze haben wir gesehen um die zeitabhängige Kontraktion zu beschleunigen?

• Wie kann man Arc-Flags anpassen?
• Was ist der Nachteil bei der Anpassung (bzgl. Vorberechnung)?
• Welche zwei Möglichkeiten haben wir kennengelernt um die Vorberechnung zu beschleunigen?

• Welche Kombinationen von Beschleunigungstechniken sind gute Kandidaten für das zeitabhängige Szenario?
• Wie funktioniert bidirektionaler zeitabhängiger ALT?
• Wie kann man den Algorithmus weiter beschleunigen wenn man nur an einer Faktor-K-Approximation interessiert ist?
• Wie funktioniert bidirektionaler zeitabhängiger Core-ALT?
• Welche zwei Ansätze haben wir gesehen um den Speicherverbrauch bei SHARC zu reduzieren?
• Was funktioniert die zeitabhängige Suche bei Contraction Hierarchies?

• Welche zwei Ansätze gibt es um einen Fahrplan als Graph zu modellieren?
• Wie berechnet man Zeitanfragen jeweils in den beiden Modellen?
• Was sind die strukturellen Unterschiede zwischen Eisenbahnnetzen und Straßennetzen, und welche Auswirkungen hat das auf die Beschleunigungstechniken die für Straßennetzwerke entwickelt wurden?

• Wie kann man eine Profilsuche in einem Schienennetz auf Zeitanfragen reduzieren? Welche Beobachtung liegt dem zu Grunde?
• Was ist Dominanz von Verbindungen?
• Wie kann man sich die Dominanz von Verbindungen algorithmisch geschickt zu Nutze machen um Verbindungen zu prunen?
• Wie lässt sich Self-Pruning mit O(n) Speicherverbrauch in den Algorithmus integrieren?
• Was ist eine Connection-Reduction, und wozu benötigt man sie?

• Wie lässt sich der Algorithmus auf einfache Weise parallelisieren?
• Was ist Inter-Thread-Pruning und wie kann man es in den Algorithmus integrieren?

• Wie lässt sich das Stoppkriterium von Dijkstra's Algorithmus auf den Algorithmus übertragen?

• Was versucht man mit der Theorie von Highway-Dimension zu erklären?
• Was ist die wissenschaftliche Methode? Wie fand sie bei der Routenplanung Anwendung?

• Auf welcher Beobachtung welcher Technik baut die Highway-Dimension-Theorie auf?
• Was ist Highway-Dimension?
• Was ist ein (r,k)-Shortest Path Cover?
• Wie hängen die beiden Definitionen zusammen?

• Was ist die zentrale Vermutung auf der die Theorie aufbaut? Warum ist es lediglich eine Vermutung?

• Was ist der generische Preprocessing-Algorithmus?
• Was kann man über ihn beweisen?

• Welche Vereinfachung wird getroffen um die Query-Zeit zu beweisen?
• Was ist die Intuition hinter dem Beweis der Schranke für Reach?
• Wie kann man eine Schranke für Contraction-Hierarchies berechnen? Wie haben wir den generischen Preprocessing-Algorithmus dazu modifiziert?

• Was ist ein Label?
• Was ist die Labeling-Eigenschaft?
• Wie funktioniert die Anfrage bei einem Labeling-Algorithmus? Was sollte also für die Label gelten damit der Algorithmus schnell ist?

• Was sind Shortest-Path-Cover-Label?
• Was gilt für ihre Größe und somit für die Query-Zeit eines darauf basierenden Labeling-Algorithmus?
• Welche andere bekannte Technik induziert bereits gültige Label?
• Warum haben bei CH-Labeln nicht alle Knoten die korrekte Distanz?
• Wie kann man CH-Label ausdünnen? Was ist in diesem Zusammenhang Bootstrapping?