SS 2006: Wegeprobleme in Graphen (2V(+1Ü))

Dr. Stefan Lewandowski / Dr. Wolfgang Schmid
Fr 9.45-11.15, Raum 0.124, Übung Fr 8.45-9.30, Raum 0.124

Übung + Vorlesungsbeginn ab 7.7. wieder um 8h45!!!

Dies ist kein vollständiges Skript(!), gibt aber eine Übersicht über die behandelten Themen.

Opera zeigt alles korrekt an, IE zeigt alles lesbar an, Mozilla verschluckt einige mathematische Symbole, sonstige Browser ... ?

Inhaltsverzeichnis

  1. Kürzeste Wege: Eigenschaften und Algorithmen
    1. Wiederholung: Grundlegende Definitionen, Dijkstras Algorithmus.
      Generische Kürzeste-Wege-Algorithmen
    2. Entfernungskorrigierende Algorithmen: Bellman-Ford und Varianten (D'Esopo-Pape, Pallottino → Übungen)
    3. Entfernungssetzende Algorithmen: SSSP in azyklischen Graphen, Dijkstras Algorithmus, A*-Algorithmus
    4. Verwendung von Buckets (Algorithmen von Dial, Dinitz und andere Bucketstrukturen)
    5. k-kürzeste-Wege-Algorithmen
  2. Wegesuche mit verbotenen Strukturen
    1. Wegeberechnung mit Abbiegeverboten
    2. Wegeberechnung mit Wegeverboten
  3. Ausgewählte Kapitel
    1. Potentialfunktionenen, Anwendung beim APSP-Problem, Dijkstra vs. A*
    2. Beidseitige Algorithmen (Dijkstra, Ikeda et.al.)
    3. Verwendung von Buckets (Linearzeit-Algorithmus von Goldberg) (entfällt)
    4. Skalierungstechniken (Algorithmen von Gabow und Goldberg)
    5. Wegesuche in hierarchischen Graphen (entfällt)
Übungen: Blatt 01 (
pdf), 02 (pdf), 03 (pdf), 04 (pdf), 05 (pdf), 06 (pdf), 07 (pdf), 08 (pdf)
Die Übungen werden jeweils Freitags ab 8h45-9h30 (Raum 0.124) besprochen.
27.04.06

I. Kürzeste Wege: Eigenschaften und Algorithmen

Literatur

  1. Ahuja/Magnanti/Orlin. Network flows. (Informatikbibliothek, Signatur: Ahuj-16727)
  2. Cherkassky/Goldberg/Radzik. Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming 73 (1996), 129-174. Vorabversion: http://citeseer.ist.psu.edu/cherkassky93shortest.html
  3. Lewandowski. Vereinheitlichte Darstellung von effizienten Techniken zur Kürzeste-Wege-Suche. Dissertation. Universität Stuttgart, 2005.
  4. Schmid. Berechnung kürzester Wege in Straßennetzen mit Wegeverboten. Dissertation. Universität Stuttgart, 2000.
  5. Turau. Algorithmische Graphentheorie. Addison-Wesley, 1996. (UB, Signatur: 4H 4990)

I.1 Eine kurze Geschichte der kürzesten Wege

I.1.1 Klassifizierung der Kürzeste-Wege-Probleme

I.1.2 Definitionen

I.1.3 Notationen

Ist im Kontext klar, welches v0 gemeint ist, wird auf den Index verzichtet.

I.1.4 Wiederholung des Dijkstra-Algorithmus

I.1.5 Teilwege kürzester Wege sind kürzeste Wege: w = v0v1...vk ist kürzester Weg ⇒ wij = vivi+1...vj ist kürzester Weg

I.1.6 Eigenschaft der kürzesten Entfernungen: w = v0v1...vk ist kürzester Weg ⇔ d(vi) + γ(vi,vi+1) = d(vi+1)

I.1.7 Existenz des Kürzeste-Wege-Baums: Sei G = (V,E,γ) ohne negative Zyklen, so existiert ein Spannbaum T = (V,ETT) so, dass sich die kürzesten Entfernungen in G und T nicht unterscheiden. Sind die d(·) bekannt, so lässt sich T in O( n + m ) berechnen.

I.1.8 Eine notwendige Bedingung für D(·) = d(·): ∀ (u,v) ∈ E: D(v) ≤ D(u) + γ(u,v), Kanten mit dieser Eigenschaft heißen konsistent (sonst verkürzend)

I.1.9 Hinreichende Bedingung für D(·) = d(·): D(v0) = 0, ∀ v ∈ V: D(v) ≥ d(v), ∀ (u,v) ∈ E: D(v) ≤ D(u) + γ(u,v) ⇒ ∀ v ∈ V: D(v)=d(v)

I.1.10 Der generische Kürzeste-Wege-Algorithmus: Solange verkürzende Kanten (u,v) existieren, setze D(v) := D(u) + γ(u,v).

05.05.06

I.1.11 Der modifizierte generische Kürzeste-Wege-Algorithmus: Verwalte in R die Knoten, die ausgehende verkürzende Kanten haben könnten. Algorithmus: Solange R ≠ ∅ entferne einen Knoten u ∈ R und setze für die ausgehenden verkürzenden Kanten (u,v) D(v) := D(u) + γ(u,v) und füge v zu R hinzu.
Laufzeit O( n·2n ) (ohne Beweis), für ganzzahlige Kantengewichte O( n·m·γ|max| ) (mit Beweis).

I.2 Entfernungskorrigierende Algorithmen

I.2.1 Verwaltung der Knotenmenge R als FIFO (Bellman-Ford) (Ablauf des Algorithmus in Phasen)

I.2.2 Phasen-Lemma: Sei wk = v0v1...vk, so gilt nach k Phasen, dass D(vk) ≤ γ(wk). Dies gilt auch, wenn der Graph negative Zyklen hat!

I.2.3 Korollar: Kürzeste Wege mit k Kanten sind nach k Phasen berechnet

I.2.4 Laufzeit Bellman-Ford: Sei t die geringste Tiefe aller Kürzeste-Wege-Bäume, so löst Bellman-Ford in O( t·m ) das SSSP-Problem oder findet einen negativen Zyklus in O( n·m )

I.2.4b Beispiel: Anzahl der Phasen kann kleiner als die Tiefe jedes Kürzeste-Wege-Baums sein

I.2.5 Verbesserung durch Vorgängerheuristik: Wird v aus R entfernt und der Vorgänger pred(v) ist in R, so hat sich D(pred(v)) wieder verringert und die von v ausgehenden Kanten brauchen nicht betrachtet zu werden, da sich D(v) wieder verringern wird (spätestens, wenn pred(v) aus R entfernt wird).

12.05.06

I.2.6 Knoten-Verwaltung als Deque (D'Esopo-Pape): Idee: Korrigiere falsch berechnete Teile so früh wie möglich, bevor mit noch nicht betrachteten Knoten weitergearbeitet wird: Knoten mit D(v) < ∞ werden vorne in die Deque (double ended queue) eingefügt (wie beim Stack), Knoten mit D(v) = ∞ hinten (wie bei einer Queue)
Laufzeit: Worst Case O( n·2n ), aber in der Praxis meist schneller als Bellman-Ford oder Dijkstra.

I.2.7 Knoten-Verwaltung mit zwei Queues (Pallottino - Übung): Idee wie bei D'Esopo-Pape, aber statt Deque (entspricht Kopplung von Stack und Queue) Verwendung einer weiteren Queue anstelle des Stacks für die wiederholt bearbeiteten Knoten.
Laufzeit: in der Praxis ähnlich schnell wie D'Esopo-Pape, aber Worst Case "nur" O( n2·m )

I.3 Entfernungssetzende Algorithmen

I.3.1 Generischer Kürzeste-Wege-Algorithmus mit optimaler Reihenfolge der Knotenauswahl: Bisher: Unnötiger Aufwand in den Algorithmen, da sich die D(v) verringern können, nachdem die von v ausgehenden Kanten schon konsistent gemacht wurden. Idee: Wähle den Knoten v so, dass D(v) = d(v) gilt.

I.3.2 Invariante ∀ v ∈ R: D(v) = min { d(u) + γ(u,v) | u ∈ B }:

I.3.3 Korrektheit von I.3.1: Es existiert stets ein v ∈ R mit D(v) = d(v)

I.3.4 Das SSSP-Problem mit γ(u,v) = 1, (u,v) ∈ E lässt sich in O( n + m ) lösen: (Beweis: Übung!)

I.3.5 Das SSSP-Problem in azyklischen Graphen lässt sich in O( n + m ) lösen

19.05.06

I.3.6 Dijkstras Algorithmus: Sei γ ≥ 0: Sei v ∈ R mit D(v) = min { D(v') | v' ∈ V−B }, so gilt D(v) = d(v)

I.3.7 Das SSSP-Problem in Graphen mit γ ≥ 0 lässt sich in O( n2 ) bzw. O( m·log n ) lösen: Dijkstras Algorithmus mit Listen bzw. Heaps

I.3.8 Das SSSP-Problem in Graphen mit γ ≥ 0 lässt sich in O( m + n·log n ) lösen: Dijkstras Algorithmus mit Fibonacci-Heaps (ohne Beweis / ohne Einführung der Datenstruktur)

I.3.9 Beim Dijkstra-Algorithmus werden die Knoten in aufsteigender Reihenfolge der Entfernung zum Startknoten betrachtet: Beweis: Übung!

I.3.10 Jede vergleichsbasierte Implementierung von Dijkstras Algorithmus benötigt im Worst-Case Ω( m + n·log n ) Schritte: Rückführung auf das Sortierproblem

I.3.11 Definitionen für den A*-Algorithmus: Eine Schätzfunktion edz : V→R heißt zulässig gdw. edz(v) ≤dist(v,z), v∈V. Sie heißt konsistent gdw. edz ist zulässig und edz(u) ≤ γ(u,v) + edz(v).

I.3.12 A*-Algorithmus: Sei v ∈ R mit D(v) + edz(v) = min { D(v') + edz(v') | v' ∈ V−B }, so gilt D(v) = d(v)

26.05.06

I.3.13 Der A*-Algorithmus mit konsistenter Schätzfunktion löst das SPSP- und das SSSP-Problem in O( m + n·log n ): Verwendung von Fibonacci-Heaps, sonst Laufzeiten wie in I.3.7. Entsprechen Kantenlängen und Schätzfunktion der Luftlinie, so beträgt die Laufzeit zur Lösung des SPSP-Problems im Mittel nur O(n) (Sedgewick/Vetter '86) - unabhängig von der Anzahl der Kanten!

I.3.14 Sind die Kantengewichte positiv, so entspricht der A*-Algorithmus mit Schätzfunktion konstant 0 dem Dijkstra-Algorithmus. Ist die Schätzfunktion dist(v,z), so werden die Knoten entlang der kürzesten Wege (zwischen v0 und z) aufgenommen. (Hierbei können alle Knoten und Kanten zu kürzesten Wegen gehören, z.B. bei einem Gitter.)

I.3.15 Beim A*-Algorithmus mit konsistenter Schätzfunktion werden die Knoten in aufsteigender Reihenfolge der Werte d()+ed() aufgenommen. Beweis: Übung!

I.3.16 Beispiel: Der A*-Algorithmus mit zulässiger aber nicht konsistenter Schätzfunktion ist ohne Änderung nicht korrekt: Die D()-Werte der Baumknoten müssen sich wieder verringern dürfen und so diese Knoten wieder in die Menge R der Knoten, deren ausgehende Kanten noch betrachtet werden müssen, aufgenommen werden können.

I.3.17 Wird der Zielknoten beim A*-Algorithmus erstmals aus der Menge R gewählt, so gilt D(z)=d(z), auch wenn die Schätzfunktion nur zulässig aber nicht konsistent ist: Dies ist eine wichtige Eigenschaft, da wir sonst gegenüber dem generischen Algorithmus keinen Vorteil hätten.

I.3.18 Beispiel: Der Worst-Case für den A*-Algorithmus mit zulässiger aber nicht konsistenter Schätzfunktion beträgt O(2n) Iterationen

I.4 Verwendung von Bucketstrukturen

Die in diesem Abschnitt vorgestellten Algorithmen basieren alle auf Dijkstras Algorithmus. Es wird dabei lediglich die Menge R mit anderen Datenstrukturen verwaltet. Die Kantengewichte müssen (zunächst) ganzzahlig sein.
Die hier verwendeten Bucketarrays werden als Array aus doppelt verketteten Listen implementiert.

I.4.1 Der Algorithmus von Dial: Speichere v mit D(v) im Bucket mit Index D(v). Insert/Decrease_Key benötigen je O(1), Delete_Min je Element O(1) und zusätzlich (summiert über alle Delete_Min-Aufrufe) max{d(v)|v∈V} → Gesamtlaufzeit O( m+n·γmax ).

02.06.06

I.4.2 Intervalleigenschaft des Dijkstra-Algorithmus: Aufgrund der Invariante I.3.2 gilt max{D(v)|v∈R} ≤ min{D(v)|v∈R}+γmax.

I.4.3 Korollar: Dials Algorithmus lässt sich mit γmax+1 Buckets implementieren.

I.4.4 Weiter verringerter Platzbedarf bei Dials Algorithmus: Der Platzbedarf kann auf jede beliebige Konstante gedrückt werden, die Laufzeit erhöht sich dadurch asymptotisch nicht.

I.4.5 Eine √γmax-Bucketstruktur: → Gesamtlaufzeit O( m+√n·γmax ).

I.4.6 Goldbergs Caliberlemma:

I.4.7 D(v)=d(v) nach Dinitz

23.06.06

I.5 k-kürzeste Wege

Wir beschränken uns in diesem Abschnitt auf Graphen mit nicht-negativen Kantengewichten (insbesondere haben die Graphen keine negativen Zyklen).

I.5.1 Klassifizierung der k-kürzeste-Wege-Probleme

I.5.2 Darstellung k-kürzester Wege: Der k-kürzeste-Wege-Baum

I.5.3 Der k-kürzeste Weg hat O(k·n) Kanten

I.5.4 Ein einfacher k-kürzeste-Wege-Algorithmus (Azevedo et.al.)

I.5.5 Eine Eigenschaft des (k+1)-kürzesten Weges: Der (k+1)-kürzeste Weg setzt sich stets aus einem (nicht verlängerbarem) Teil im k-kürzeste-Wege-Baum, einer von dort abzweigenden Kante und einem kürzesten Weg zum Zielknoten zusammen

30.06.06

I.5.6 Laufzeitverbesserung nach Martins et.al. und Lewandowski (verwendet I.5.5)

I.5.7 Das eingeschränkte k-kürzeste-Wege-Problem (Algorithmus von Yen)

30.06.06+07.07.06

II Berechnung kürzester Wege in Graphen mit verbotenen Strukturen (mit special Guest Dr. Wolfgang Schmid)

Folien

II.1 Der Hauptsatz der Abbiegeverbotstheorie
II.2 Kürzeste Wege in Graphen mit Abbiegeverboten (dynamische Verfahren)
II.3 Kürzeste Wege in Graphen mit Abbiegeverboten (statische Verfahren)
II.4 Der Beweis des Hauptsatzes
II.5 k-kürzeste Wege mit dem Algorithmus von Azevedo
II.6 Kürzeste Wege in Graphen mit Wegeverboten
II.7 Eine Beweisskizze des Algorithmus

14.07.06

III Ausgewählte Kapitel

III.1 Potentialfunktionenen

III.1.1: Definition: Potentialfunktion und reduzierte Kantengewichte

III.1.2: Invarianz bzgl. Zyklen negativer Länge

III.1.3: Invarianz bzgl. der Ordnung der Weglängen

III.1.4: Potentialfunktionen und Kürzeste-Wege-Bäume

III.1.5: Reduzierte Kantengewichte konsistenter Kanten

III.1.6: Ein Linearzeittest für D(·)=d(·) vgl. I.1.6 und I.1.7

III.1.7: Existenz konsistenter Potentialfunktionen

III.1.8: Ein einfacher Algorithmus für das APSP-Problem (Floyd)

III.1.9: Potentialfunktionen und das APSP-Problem

III.1.10: Dijkstra vs. A* vs. Potentialfunktionen

21.07.06

III.2 Beidseitige Algorithmen

III.2.1: Ein Schema zur Lösung des SPSP-Problems durch beidseitige Suche

III.2.2: Ein Abbruchkriterium bei Verwendung von Dijkstras Algorithmus

III.2.3: Ein Abbruchkriterium bei Verwendung des A*-Algorithmus

III.2.4: Beschleunigung durch Potentialfunktionen (nach Ikeda et.al.)

28.07.06

III.4 Skalierungstechniken (Algorithmus von Gabow)


Stefan Lewandowski
Last modified: Fri Apr 20 11:45:16 CEST 2012