Guten Tag, ich darf Sie herzlich willkommen heißen zur heutigen
Vorlesung Algorithmen 1.
Letzte Woche hatten Sie am Montag die Probeklausur und am Mittwoch
nochmal Übungen hier im Saal.
Ich hoffe, die Klausur war für Sie eine ganz gute Erfahrung, um schon
mal zu sehen, was bei der eigentlichen Klausur im September dann auf
Sie zukommen wird.
Aber wir wollen heute im Stoff weitermachen und erinnern uns nochmal
kurz, woran wir in der vorletzten Woche gearbeitet hatten.
Wir hatten das Thema kürzeste Wege in Grafen und hatten uns dazu
bereits den Dijkstra-Algorithmus angeschaut und auch festgestellt,
dass der Algorithmus noch nicht direkt anwendbar ist, wenn wir mit
negativen Kantengewichten zu tun haben.
Und das, was wir uns deshalb heute anschauen wollen, ist noch etwas
mehr zu kürzesten Wege oder kürzesten Pfade-Algorithmen.
Insbesondere wollen wir einen Algorithmus noch betrachten, der es
erlaubt, auch mit negativen Kantengewichten und dort speziell auch
Zyklen mit negativen Kantengewichten umzugehen.
Aber versuchen wir uns nochmal zu vergegenwärtigen, warum es bei dem
kürzesten Wege-Problem überhaupt geht.
Also, wir haben zur Erinnerung nochmal einen Graph gegeben, bestehend
aus Knoten- und Kantenmenge.
Wir gehen von einem gerichteten Graph aus und in diesem gerichteten
Graph sind die Kanten mit einer Kostenfunktion versehen.
Außerdem haben wir jetzt in diesem Graph einen Startknoten gegeben und
wir sind daran interessiert, ausgehend von dem Startknoten, die
kürzesten Pfade zu allen anderen Knoten zu finden.
Also, wir wollen für alle Knoten hier diese Ausgabe berechnen und zwar
die Länge des kürzesten Pfades von dem Startknoten aus zu einem der
Knoten V oder zu allen Knoten V.
Und die Länge eines solchen kürzesten Pfades ist eben dadurch
bestimmt, dass wir einfach die Kantengewichte aufsummieren und da
suchen wir eben jetzt einen Pfad geringsten Gewichts.
Und dazu hatten wir uns den Dijkstra-Algorithmus angeschaut.
Hat jemand von Ihnen noch so grob im Kopf, was so die Bausteine und
die Grundideen von Dijkstras Algorithmus waren?
Zur Erinnerung ist hier auch nochmal der Algorithmus im Pseudocode
angegeben.
Aber wenn von Ihnen vielleicht nochmal kurz jemand so die wichtigsten
Punkte nochmal in Erinnerung rufen kann.
Also was hat man an Begriffen dazu?
Also irgendwie taucht hier so ein Begriff Relax auf.
Das können Sie natürlich auf sich beziehen.
Versuchen Sie ein bisschen hier zu entspannen.
Aber trotzdem vielleicht die Frage zu beantworten.
Also was hat es mit...
Wir hatten den Begriff Relaxation hier und vielleicht versuchen Sie
sich nochmal zu erinnern.
Wir hatten uns auch ganz am Anfang so ein physikalisches Modell
angeschaut gehabt, wo wir gesagt haben, ja wir haben unsere Knoten
einfach als Kugeln und verbinden dann diese Kugeln mit Fäden
entsprechender Länge und heben dann einfach den Graph an unserer
Startkugel auf.
Und dann gibt es eben solche gespannten Fäden, die uns die kürzesten
Pfade angeben.
Und es gibt solche, die eben nicht gespannt sind, die dann auch keine
kürzesten Pfade sind.
Und was während dem Algorithmus eben passieren kann, ist, dass wir für
einen gegebenen neuen Knoten, der zu einem Pfad dazukommt,
herausfinden, dass der jetzt mit einem geringeren Gewicht erreichbar
ist, als das, was bisher für diesen Knoten an erreichbarem Pfad mit
dem geringsten Gewicht geplant war.
Und dieser Schritt, das wir schauen, gibt es eben von einem...
Wir haben bereits einen Knoten U erreicht und haben für den eine
Distanz berechnet, eine minimale Distanz und haben einen weiteren
Knoten V, für den wir eventuell auch schon eine Distanz berechnet
haben vom Startknoten.
Und jetzt finden wir heraus, wenn wir eben über diese Kante von U nach
V gehen,
also dieses Kantengewicht von genau dieser Kante dazukommt, dass das
uns für den Knoten V eine kleinere Distanz ermöglicht, um vom
Startknoten zum Knoten V zu kommen.
Dann wählen wir jetzt eben für diese Distanz zu Knoten V einen neuen
Pfad und dieses Wählen eines neuen Pfades, wenn es eben über eine neu
ausgewählte Kante einen kürzeren Pfad gibt, das nennt sich dann
Relaxation.
Also wir haben über eine neue Kante, die wir bisher noch nicht
untersucht hatten, einen kürzeren Pfad gefunden und den merken wir uns
dann, dass wir darüber den Knoten V eben noch besser erreichen können.
Und dieser Schritt, dieses Ändern des Pfades, nennt sich eben
Relaxation.
Also gut, wir haben diese Relaxation, die uns eben erlaubt, wenn wir
einen kürzeren Pfad gefunden haben, den entsprechend zu registrieren.
Und wie sehen diese Verkürzungen aus, wenn wir einen kurzen Pfad
finden?
Der Anfangsteil bleibt immer gleich, nur der letzte Schritt ist immer
so, dass der eben noch zu einer Verbesserung führen kann.
Okay, also wir wissen, der Pfad zu U ist bereits optimal und um dann
zu V zu kommen, können wir eben dann über diese Kante E noch zu einem
besseren Ergebnis kommen.
Jetzt ist noch die Frage, wie können wir sicherstellen, dass der
Knoten U bereits die optimale Distanz hat?
Das können wir damit durch erreichen, dass wir eben vom Startknoten
aus in einer bestimmten Reihenfolge die Knoten betrachten, die wir als
nächstes relaxieren.
Und da möchte ich Sie auch noch mal fragen, in welcher Reihenfolge
gehen wir die Knoten jetzt durch?
Also was ist der Knoten, den wir als nächstes betrachten, wenn wir
schon bestimmte Knoten untersucht haben?
Sie erinnern sich vielleicht hier an diese, wir haben diese Q.
In der Q ist am Anfang nur unser Startknoten drin.
Ja, bitte.
Ja, jetzt habe ich es akustisch nicht verstanden.
Können Sie es vielleicht nochmal?
Genau, wir nehmen aus den Knoten, die jetzt eben als Kandidaten für
eine Verlängerung der Pfade in Frage kämen, wählen wir den mit
geringstem Gewicht aus.
Also deshalb verwenden wir eben auch diese Priority-Q, die es uns
erlaubt, auf den Knoten mit aktuell geringster Distanz zuzugreifen.
Also wir haben auch den Begriff, dass ein Knoten gescannt ist,
verwendet.
Gescannt waren Knoten dann, wenn wir eben ausgehend von dem Knoten
diese Relaxationsschritte durchgeführt hatten.
Das heißt, wir hatten ausgehend von diesem Knoten geprüft, wenn wir
jetzt einen Schritt noch weiter gehen in dem Graph, gibt es dann
kürzere Wege zu diesen Zielknoten.
Und wenn ja, haben wir diesen Relaxationsschritt durchgeführt und wenn
das für alle ausgehenden Kanten von dem Knoten U gemacht wurde, war
dieser Knoten als gescannt bezeichnet.
Und hier ist es eben so, dass für alle gescannten Knoten bereits die
kürzeste Distanz berechnet ist.
Also gut, wir haben diese Priority-Q, die am Anfang nur den
Startknoten erhält und dann eben im Laufe des Algorithmus eben diese
relaxierten Knoten wieder zubekommt.
Gut, und was wir berechnen, ist eben einerseits die Distanz für alle
Knoten, die anfangs mit unendlich initialisiert ist, weil wir noch
nicht wissen, wie groß sie ist.
Bis auf den Startknoten, für den wir die Distanz auf Null setzen.
Das ist auch klar.
Und dann wollen wir auch natürlich die Möglichkeit haben, zu wissen,
was denn jetzt die kürzesten Pfade sind.
Und das speichern wir in so einem Parent Array ab.
Das heißt, den Pfad fahre ich wieder rückwärts, der wird in diesem
Parent Array abgespeichert.
Okay, also das war unser Dijkstra-Algorithmus, der es eben erlaubt,
kürzeste Pfade für alle Knoten zu berechnen.
Und der verwendet eben diese Priority-Q.
Jetzt schauen wir uns nochmal an, was passiert, wenn in dem Graph auch
negative Kanten auftauchen.
Das hatten wir uns ja schon ein klein bisschen angeschaut und
festgestellt, dass es dann in dem Sonderfall, dass wir auch negative
Kreise oder negative Zyklen haben, wir auf ein Problem stoßen.
Das heißt, wenn wir jetzt einen Zyklus haben, auf dem die über diesen
Zyklus aufsummierten Kantengewichte negativ sind, dann können wir
einfach so einen Zyklus immer wieder durchlaufen und mit jedem
Durchlaufen wird das Kantengewicht, das Gewicht für den kürzesten Pfad
wird verringert.
Und nachdem wir das unendlich oft machen können, können wir damit auch
beliebig tiefe Kantengewichte erreichen.
Das heißt, das ist noch ein bisschen ein Problem.
Und was wir jetzt machen wollen, ist, wir wollen mal anschauen, was
passiert denn jetzt bei dem Dijkstra-Algorithmus, wie wir den auf der
letzten Folie gesehen hatten, wenn wir den auf Graphen anwenden mit
negativen Kantengewichten.
Also wir wissen bereits, Dijkstra-Algorithmus, der löst das kürzeste
Pfadproblem für Graphen mit nicht negativen Kantengewichten.
Also da bekommen wir wirklich immer die korrekte Information raus.
Und was passiert jetzt bei negativen Kantengewichten?
Dazu wollen wir uns das an einem kleinen Beispiel mal anschauen, was
hier passiert.
Also hier ein Graph mit vier Knoten und vier Kanten.
Wir nehmen an, dass eins der Startknoten ist und schauen jetzt mal an,
was macht jetzt unser Dijkstra-Algorithmus, wie im Pseudokod vorher
dargestellt, auf diesem Graph.
Also in dem ersten Schritt wird unser Startknoten, ist der eins, wird
der in die Queue gelegt, dann auch direkt wieder aus der Queue
rausgenommen und ist unser Knoten, von dem aus wir dann die Relaxation
aus durchführen.
Das heißt, wir schauen jetzt vom Knoten eins aus uns an, was sind die
von dort aus als Nachfolgeknoten erreichbaren Knoten.
Das wären hier jetzt die Knoten zwei und vier.
Und das heißt, für diese Knoten können wir jetzt auch dann die
minimale Distanz berechnen.
Das wäre dann eben für den Knoten zwei wäre das die Distanz eins, für
Knoten vier wäre das Distanz vier.
Und diese beiden Knoten würden wir jetzt in unserer Queue wieder
ablegen, als Knoten, die jetzt eben schon gescannt sind, die wir aber
jetzt noch weiter bearbeiten müssen.
Okay, dann geht es also weiter.
Im nächsten Schritt haben wir jetzt in unserer Queue die beiden Knoten
zwei und vier drin.
Wir wählen den Knoten mit geringstem Gewicht oder mit geringster
Distanz aus.
Das wäre jetzt der Knoten zwei, der hätte Distanz eins, führen von
dort aus diese Expansion durch, dann kommt der Knoten drei dazu.
Der von hier aus in einem richtigen Schritt erreichbar ist.
Das heißt, danach haben wir dann drei und vier in unserer Priority
Queue.
Wenn wir nochmal schauen von drei, Knoten drei, die Distanz ist zwei
von Knoten vier.
Die Distanz ist vier, also würden wir drei als nächstes auswählen.
Und es kommt kein weiterer Knoten dazu, weil es eben keine ausgehenden
Kanten von drei ausgibt.
Das heißt, wir haben dann nur noch vier in unserer Queue drin.
Wir erarbeiten vier, stellen fest, ja, von vier aus, wenn wir den
expandieren, ist drei erreichbar, wird dann in die Queue dazugefügt
und bekommt auch eine neue minimale Distanz, weil eben die neue
Distanz vier plus minus drei, also eins geringer ist als die bisherige
Distanz zwei.
Und das heißt, damit müssen wir auch dann unseren Knoten drei wieder
in diese Queue reinnehmen.
Und was wir jetzt sehen, ist, dass was hier passieren kann, ist, dass
ein Knoten eben mehrfach in der Queue landen kann.
Nicht nur einmal, wie das bei positiven Kantengewichten der Fall ist,
sondern kann hier eben mehrfach auftreten als Knoten, der wieder in
die Queue mit dazu genommen wird.
Und das war jetzt noch ein einfacher Fall, in dem wir keinen negativen
Zyklus hatten.
Was bei einem negativen Zyklus hier passieren würde, ist, dass dieser
Knoten drei unendlich oft in diese Queue mit reingenommen würde und
man eben wieder über den Relaxationsschritt eine niedrige Distanz von
den Knoten berechnet hätte.
Und das passiert eben unendlich lange, weil wir mit jedem Durchlaufen
eines negativen Zykluses wieder neues, geringeres Kantengewicht
bekommen.
Also das heißt, dieser Dijkstra-Algorithmus, wie wir ihn auf der
letzten Folie hatte, würde in dem Fall nicht terminieren.
Okay, also das ist schon mal schlecht, weil wir dann haben einen
Algorithmus, der eben nicht anhält.
Also das ist nicht so schön.
Da würden wir eigentlich lieber was anderes haben, wo wir eben
sinnvoll mit negativen Zyklen umgehen könnten.
Also das ist noch keine Lösung, was wir jetzt haben soweit.
Okay, bevor wir uns da jetzt noch ein bisschen näher damit
beschäftigen, wie so ein Algorithmus aussieht, der auch mit negativen
Kantengewichten umgehen kann, möchte ich noch ganz kurz darauf
hinweisen, dass der ursprüngliche Algorithmus, wie ihn Dijkstra
formuliert hatte, etwas anders aussieht, wie das, was ich Ihnen jetzt
auf den letzten Folien präsentiert hatte.
Und Sie müssen jetzt gar nicht alles durchlesen, das ist viel zu viel.
Das können Sie vielleicht zu Hause mal machen, dass Sie mal
draufschauen.
Was vielleicht interessant ist, dass das damals in den 50er, 60er
Jahren, also in den Anfangsjahren der Informatik, noch nicht wirklich
üblich war, Pseudocode zu verwenden.
Also das sind sehr viele Algorithmen wirklich in so einer Prosaform,
also als durchgängiger Text formuliert gewesen, wie wir das hier eben
auch sehen.
Das ist dann auch etwas komplizierter zu lesen aus meiner Sicht, wie
eben das, was man heutzutage im Pseudocode formulieren würde.
Aber das war zu der damaligen Zeit eben so die übliche Art, wie
Algorithmen dargestellt wurden.
Okay, also das können Sie sich gerne zu Hause anschauen.
Wenn man das jetzt ein bisschen in eine modernisierte Form bringen
möchte, können wir denselben Algorithmus auch in Pseudocode wieder
aufschreiben.
Und der Algorithmus von Dijkstra, der ursprüngliche Algorithmus, sieht
dann ungefähr so aus.
Und jetzt können wir mal schauen, was haben wir hier.
Also wir haben hier auch irgendwie diese so eine Menge Q für Vertices.
Wir haben genauso die Distanz und unser Parent Array, das hier pref
heißt, was eben dann diesen kürzesten Faden abspeichert.
Und ja, hier unten haben wir eigentlich auch diesen Relaxationsschritt
in einer ähnlichen Form.
Trotzdem unterscheidet sich der Algorithmus etwas von dem, was wir
bisher eben gesehen hatten.
Jetzt würde ich Sie mal bitten, nehmen Sie sich eine oder zwei Minuten
Zeit und vergleichen Sie mal diesen Algorithmus mit dem Algorithmus,
den wir auf den letzten Folien hatten und versuchen Sie
herauszufinden, was hier der Unterschied war.
Also es sieht sehr ähnlich aus, aber unterscheidet sich doch eben an
einer relevanten Stelle mindestens.
Falls Sie Fragen haben, wenn irgendwas unverständlich ist, können Sie
gerne mir auch eine Frage dazu stellen.
Also vielleicht noch ein Hinweis vielleicht, wo sich der Unterschied
der Algorithmen zeigt.
Es werden ja festgestellt bei dem Algorithmus, wie bisher präsentiert,
mit negativen Kanten, kann es sein, dass der Algorithmus nicht
terminiert.
Wie sieht denn das hier aus mit Termination?
Also das wäre ein Aspekt, den Sie sich speziell anschauen könnten.
Hat schon jemand einen Unterschied festgestellt?
Ja, das ist eigentlich schon der Hauptunterschied.
Also wenn Sie noch etwas anderes finden, können Sie es nachher noch
dazu sagen.
Aber genau wie Sie es angemerkt hatten, ist es hier so, dass diese
Priority Queue einmal am Anfang initialisiert wird mit allen Knoten
des Graphen und dann in jedem Streifendurchlauf einfach nur noch ein
Knoten derjenige mit der minimalen Distanz entfernt wird.
Und hier bei dem Relaxationsschritt keine neuen Knoten zu der Queue
mehr hinzugefügt werden.
Also das heißt, wir wissen garantiert, dass diese Schleife hier, die
über die Queue läuft, nur n Mal, wenn wir n Knoten in unserem Graph
haben, durchlaufen wird.
Das heißt, der Algorithmus terminiert.
Aber da kann man sich jetzt natürlich auch die Frage stellen, also für
positive Kanten funktioniert dieser Algorithmus und liefert ein
korrektes Ergebnis.
Also da geht es auch mit dieser Reihenfolge, dass man am Anfang
erstmal alle Knoten reinsetzt.
Aber für negative Kantengewichte liefert er eben dann keine korrekten
Ergebnisse.
Also wir haben hier den Unterschied, der Algorithmus terminiert zwar,
aber liefert eben keine korrekten Ergebnisse.
Was man vielleicht auch noch hier anmerken kann, ist, dass diese
Variante des Dijkstra-Algorithmus, dass die Prioritätslisten hier mit
einer besonderen Art von Daten zu tun haben.
Und zwar ist es so, dass das Minimum, das in der Prioritätsliste
auftaucht, immer monoton ansteigt.
Also jedes Mal, wenn wir ein Element rausnehmen, dann steigt es eben
an.
Also es ist nicht nur bei der Original Dijkstra-Version so, sondern
auch bei der, wie wir sie davor definiert hatten.
Und das lässt sich noch ausnutzen, um zu schnelleren Algorithmen zu
kommen.
Also die Komplexität von Dijkstra hatten wir letztes Mal uns überlegt,
was die ist mit dem Algorithmus, den wir uns bisher angeschaut hatten.
Das war O von M plus N mal Log N.
Und diesen Faktor Log N können wir noch wegbekommen, wenn wir eben
eine spezialisierte Datenstruktur für die Prioritätsliste hier
verwenden.
Dann können wir auch auf eine Laufzeit von O von M plus N kommen, also
ohne den logarithmischen Faktor noch.
Wie das geht, dazu erfahren Sie dann mehr in der späteren Vorlesung
Algorithmen 2.
Aber kommen wir wieder zu dem Problem der negativen Zügenden zurück.
Wir können uns mal überlegen, was könnte denn die gewünschte Lösung
sein oder wie wollen wir die überhaupt darstellen?
Also wie wollen wir die Kanten oder die minimalen Pfadlingen
darstellen, wenn wir eben negative Zügenden oder negative Kanten
haben?
Und was wir machen können, ist, dass wir einfach die Definition der
Distanz von einem Knoten zum Startknoten erweitern.
Was wir bisher schon hatten, ist, wir hatten die Distanz plus
unendlich und wir hatten eine Distanz, dass sie einfach einem
bestimmten Zahlenwert, einer Konstanten C entspricht, plus unendlich.
Das war das, mit was wir unsere Distanz initialisiert hatten.
Das heißt, wenn ein Knoten nicht erreichbar war im Graph, wurde die
Distanz von dem Knoten vom Algorithmus nie verändert, blieb er
unendlich.
Also unendlich zeigt uns an, dass es keinen Pfad von S zu dem Knoten V
gibt.
Also wenn dieses V unendlich ist, dann gibt es keinen Pfad nach V.
C sagt eben aus, es gibt einen Pfad mit dem, ja, mit dem Gesamtgewicht
C.
Und was wir jetzt machen, wir fügen jetzt noch zusätzlich als mögliche
Distanz für einen Knoten das Minus unendlich ein.
Und Minus unendlich steht eben dafür, dass es eigentlich einen
negativen Zyklus gibt.
Also das heißt, es gibt keinen kürzesten Pfad von S nach V.
Weil es eben durch so einen Zyklus immer möglich ist, den Pfad, die
Länge des Pfades weiter abzukürzen.
Okay, also eine relativ einfache Erweiterung.
Wir wollen einfach in unsere Distanzen noch den Wert Minus unendlich
mit dazunehmen.
Und das heißt, wie sieht dann das Ergebnis aus, wenn wir hier unten
jetzt so einen Beispielgraf betrachten?
Da sehen Sie, es gibt einige Knoten.
Das ist jetzt schon das Ergebnis von so einer kürzesten
Pfadberechnung, die eben auch mit negativen Kanten und Kreisen umgehen
kann.
Sie sehen, wir haben hier bei unter den grauen Knoten haben wir hier
einen Kreis, nämlich diesen hier, auf dem wir ein negatives
Gesamtkantengewicht haben.
Eben Minus eins, wie es hier auch dran steht.
Und das heißt, wir können über diesen Zyklus hier beliebig unser
Kantengewicht absenken.
Und deshalb sind auch diese Kanten alle mit Minus unendlich markiert.
Was dann auch relativ offensichtlich ist, ist alles, was dann aus so
einem Kreis mit Minus unendlich erreichbar ist, bekommt natürlich auch
das Kantengewicht Minus unendlich.
Also um zum Beispiel zu dem Knoten A zu kommen, wäre es ja möglich,
beliebig oft durch diesen Zyklus zu laufen und dann irgendwann mal
eben die Abzweigung von B nach A zu nehmen.
Aber davor können wir auch das Kantengewicht eben beliebig absenken.
Also bekommt auch der Knoten A, also alles, was von so einem negativen
Zyklus aus erreichbar ist, bekommt das als Distanz Minus unendlich
zugewiesen.
Links unten sehen wir auch noch einen Knoten mit Distanz Plus
unendlich.
Der ist eben nicht erreichbar vom Schnappknoten aus.
Deshalb bleibt er bei Plus unendlich und alles auf der rechten Seite
ist eben erreichbar.
Und es gibt keine Zyklen mit negativen Gesamtgewicht über die Kanten.
Sie sehen, es gibt hier zwar negative Gewichte, aber hier über diesen
Zyklus ist es so, dass wir da, wenn wir aufsummieren über den Zyklus,
haben wir Minus 2, Plus 5, Plus 2.
Also insgesamt ein positives Kantengewicht, sodass wir, dass diese
Knoten auf der rechten Seite alle einen vernünftigen Wert der Distanz
zugewiesen bekommen können.
Okay, also so würde ein Ergebnis aussehen, wie wir es gerne hätten für
die negativen Kantengewichte.
Und die Frage ist, wie wir jetzt zu einem Algorithmus kommen, der uns
sowas liefern kann.
Okay, und dazu wollen wir nochmal ein bisschen uns das Problem nochmal
anschauen und ein paar einfache Eigenschaften dieses Problems auf der
kürzesten Pfade mit negativen Kanten.
Und die erste Beobachtung hier ist, die hier in diesem Lemma
formuliert ist, wenn es einen kürzesten Pfad P gibt von S nach V, also
vom Startknoten zum Knoten V, dann ist es so, dass dieser Pfad einfach
ist.
Und was bedeutet, dass ein Pfad einfach ist?
Das bedeutet, dass keine Kanten auf diesem Pfad mehrfach vorkommen.
Also jede Kante darf maximal einmal vorkommen.
Das ist schon mal eine Feststellung.
Also das heißt, wenn so ein kürzester Pfad existiert, dann ist es so,
dass der nie durch einen Zyklus durchläuft.
Okay, und das können wir uns überlegen.
Das sind eigentlich zwei Fälle, die jetzt hierbei auftreten können.
Entweder haben wir einen Zyklus mit negativen Gewicht über diesen
Zyklus oder wir haben einen Zyklus mit positiven Gewicht über den
Zyklus.
Und diese beiden Fälle, die wollen wir jetzt unterscheiden.
Also der erste Fall.
Wir haben negatives Gewicht über diesen Zyklus aufsummiert.
Also wir wissen, V ist über einen negativen Kreis erreichbar.
Und was folgt dann daraus?
Das folgt daraus, dass es keinen kürzesten Pfad von S nach V gibt.
Warum ist es der Fall?
Weil es eben über diesen negativen Kreis die Möglichkeit gibt, den
unendlich oft zu durchlaufen, das Kantengewicht immer weiter
abzusenken.
Also in dem Fall gilt dann unser Lemma.
Das heißt, das ist praktisch jetzt von rechts nach links.
Wenn wir annehmen, dass der Pfad nicht einfach ist, weil es eben über
so einen negativen Kreis läuft, dann existiert auch kein kürzester
Pfad von S nach V.
Also haben wir damit praktisch per Widerspruch dieses Lemma für diesen
Fall bewiesen.
Und im anderen Fall ist es so, dass der Kreis ein positives
Kantengewicht hat.
Also das heißt, wenn wir aufsummieren die Kanten über so einen Zyklus
hinweg, dann ist die Summe positiv.
Und was passiert dann?
Dann ist es natürlich so, bei jedem Durchlaufen eines Zyklus wird das
Kantengewicht natürlich größer.
Und wenn wir nach einem kürzesten Pfad suchen, ist es natürlich am
besten, diesen Zyklus gar nicht zu durchlaufen, weil mit jeder
weiteren Runde, die wir durchgehen, wird das Gewicht größer.
Also lassen wir es einfach sein, den mehrfach zu durchlaufen.
Das heißt, wir können deshalb einfach einen beliebigen Pfad hernehmen,
alle Kreise streichen, weil die ja sowieso nur das Kantengewicht
erhöhen würden oder die Distanz erhöhen würden.
Und dann, nachdem wir diese Kreise entfernt haben, haben wir einen
einfachen Pfad, der auf jeden Fall nicht länger ist als unser
ursprünglicher.
Das heißt, auch dann ist es so, dass eben ein kürzester Pfad immer ein
einfacher Pfad ist.
Okay, also das können wir schon mal merken.
Wir müssen die Zyklen, in denen wir zum Graf vorkommen, nicht mehrfach
durchlaufen, sondern es reicht uns die einmal anzuschauen und das
Mehrfache bringt uns eigentlich keine weiteren Informationen.
Das ist schon mal gut, weil das hilft uns zum Beispiel auch, diese
Nichttermination zu vermeiden.
Also wir wissen dann, dass da eben keine unendlich langen Berechnungen
über solche Zyklen erforderlich sind.
Okay, dann schauen wir mal noch zu weiteren Beobachtungen, die man
noch machen kann, wenn man sich das kürzeste Pfadeproblem anschaut.
Das hat man, glaube ich, auch letztes Mal ganz kurz schon
angesprochen.
Wenn wir einen kürzesten Pfad haben, sind auch die Teilpfade in diesem
Pfad kürzeste Pfade.
Also wir haben zum Beispiel herausgefunden, von A nach D, A können wir
zum Beispiel auch annehmen, dass es ein Startnoten wäre, wäre ein
kürzester Pfad.
Dann ist natürlich auch von A nach C ein kürzester Pfad oder von A
nach B.
Oder auch, wenn wir den Teilpfad von B nach D uns anschauen.
Warum ist das der Fall?
Wenn ein Teilpfad nicht der kürzeste wäre, könnte man natürlich auch
für diesen Gesamtpfad statt dem gegebenen Teilpfad den kürzeren nehmen
und hätten dann einen mit geringerem Krankengewicht.
Okay, also Teilpfade sind immer auch selber kürzeste Pfade.
Die andere Eigenschaft, die man noch feststellen kann, ist, wenn man
sich den Algorithmen anschaut, dass die kürzesten Pfade, wenn man die
markiert in dem Graph, also alle Kanten, die zu einem kürzesten Pfad
gehören, dann bilden diese Kanten einen Baum, wenn es keine negativen
Kreise oder Zyklen gibt.
Also so wie hier unten dargestellt, möchte ich jetzt einfach ohne
Beweis sie angeben, ist es so, dass man eben diese kürzesten Pfade in
Form eines Baumes im Graph darstellen kann.
Gut, was wir uns jetzt noch überlegen wollen, ist, wie kann man denn
ein bisschen verallgemeinert solche kürzesten Pfade berechnen anhand
von diesen Beobachtungen.
Und ja, was wir bei dem Zeigstein-Algorithmus bisher haben, ist, dass
wir eine gewisse Restriktion haben, in welche Reihenfolge wir Kanten
betrachten.
Wir haben einerseits, dass wir vom Startknoten eben ausgehen und von
da aus diesen Relaxationsschritt ausführen und eben ansonsten immer in
unsere Queue den Knoten mit... oder aus unserer Priority Queue den
Knoten mit kleinster Distanz auswählen und von dem aus dann
weiterarbeiten.
Und das ist praktisch eine gewisse Einschränkung, in welche
Reihenfolge wir bei dem Algorithmus vorgehen.
Und wir können uns überlegen, inwiefern wir vielleicht von diesen
Einschränkungen der Reihenfolge her zu einer abgeschwächten Form oder
zu anderen Reihenfolgen kommen können, die auch zulässig sind und die
uns ein Ergebnis liefern, das dann vielleicht auch für negative Kreise
funktioniert.
Okay.
Und dazu wollen wir betrachten, einfach eine Folge von
Relaxationsoperationen, die wir der Reihe nach ausführen.
Also wir haben unseren Graph gegeben mit einer Menge von Kanten und
wir nehmen jetzt an, wir führen einfach beliebige
Relaxationsoperationen auf den Kanten durch.
Also was bedeutet das?
Wir nehmen eben uns eine Kante her, haben für den Knoten U, also den
Startnoten der Kante, unter Umständen bereits eine Distanz berechnet
und schauen dann eben uns an, ob wir für V, also den Zielknoten dieser
Kante, ob wir damit eine neue, kleinere Distanz bekommen.
Das heißt, wir lassen jetzt einfach erstmal eine beliebige Reihenfolge
zu, in der wir diese Relaxationsoperationen ausführen.
Okay.
Und wenn wir jetzt annehmen, dass wir einen Pfad P haben, der eben
über Kanten E1 bis EK geht und der soll so sein, dass wir eben auf
diesem Pfad für jede Kante einen Relaxationsschritt einmal
durchgeführt haben.
Genau.
Dann haben wir durch diesen Pfad auch so eine Knotenfolge gegeben.
Ausgehend vom Startknoten kommen wir eben über diese Kanten zu den
entsprechenden weiteren Knoten, bis wir bei VK angekommen sind.
Und da nehmen wir an, dass das jetzt ein kürzester Weg sein soll.
Und jetzt überlegen wir uns, was gilt für diesen kürzesten Weg hier,
wenn wir jetzt diese Relaxationsoperationen in irgendeiner Reihenfolge
durchführen, sodass eben irgendwann mal hier auf E1 relaxiert wird,
irgendwann mal auf E2 und so weiter.
Oder auch in beliebiger Reihenfolge.
Dann stehen wir fest, dass dann irgendwann mal oder nach dieser
Ausführung von Relaxationsoperationen auf jedem Knoten gilt, dass die
Distanz von dem Knoten VK, also diesem letzten Knoten hier, dass das
wirklich die minimale Distanz zu VK ist.
Und wenn wir eben bestimmte Relaxationsoperationen durchgeführt haben
und das schauen wir uns mal schrittweise an, also für den Startknoten
gilt es bereits bei der Initialisierung und für den Knoten 1, also
derjenige, der eben vom Startknoten in einem Schritt erreichbar ist,
gilt es nach dem Zeitpunkt T1, wobei T1 der Zeitpunkt ist, wo wir
diese Kante E1, also die vom Startknoten nach V1 geführt hat, zum
ersten Mal relaxiert haben.
Okay, also hier gilt an dieser Stelle nach der Relaxation an der
Stelle der Kante E1, gilt die kürzeste Pfadeigenschaft für V1.
Wenn wir dann nach dem Relaxationsschritt für E2 durchgeführt haben,
gilt es auch für V2 und so weiter bis zum Schluss eben das für VK
gilt.
Also das heißt, was müssen wir sicherstellen, um einen kürzesten Pfad
zu erreichen?
Wir müssen sicherstellen, dass eben diese Relaxation auf der Kante E1
durchgeführt wurde, dass danach die Relaxation auf Kante E2
durchgeführt wurde und so weiter eben bis zur Kante EK.
Und nachdem wir am Anfang eben nicht wissen, wie so ein kürzester Pfad
aussieht, muss es für alle Pfade eben so der Fall sein, dass diese
Relaxationsschritte durchgeführt wurden.
Aber ansonsten haben wir keine bestimmte Reihenfolge mehr, die wir
jetzt vorgehen.
Also eben muss nur sichergestellt sein, dass genügend
Relaxationsschritte durchgeführt wurden.
Damit können wir uns auch schon einen Algorithmus überlegen.
Und das ist ein Algorithmus, den sich die Herren Bellman und Ford so
ausgedacht hatten.
Und deshalb ist er eben auch Bellman-Ford-Algorithmus genannt.
Und wie funktioniert der?
Wir relaxieren einfach alle Kanten in einer beliebigen Reihenfolge.
Also wir nehmen alle Kanten in unserem Graph her, relaxieren die.
Das ist dann unsere erste Runde.
Und nach dieser ersten Relaxationsrunde über alle Kanten wissen wir,
dass auf einem beliebigen Pfad, den wir uns jetzt hier anschauen, nach
der ersten Runde auf jeden Fall gilt, dass wir für den in einem
Schritt erreichbaren Knoten die minimale Distanz gefunden haben.
Danach wiederholen wir das einfach nochmal.
Das heißt, wir schauen uns wieder alle Kanten an und berechnen für
alle Kanten die Relaxation und haben dann damit garantiert für alle
Knoten mit der Distanz 2 von unserem Startknoten aus eine minimale
Pfad gefunden.
Nach drei Iterationen eben bis zu Knoten mit Distanz 3 und nach der K
minus ersten Runde sind wir so, dass wir Pfade bis zur Länge n
abgedeckt haben.
Also das heißt, wir können einfach dieses Verfahren, alle Kanten zu
relaxieren, n mal wiederholen, wobei n eben die Anzahl der Knoten oder
n minus 1 mal, wenn n die Anzahl der Knoten in unserem Graph ist und
haben damit dann garantiert kürzeste Pfade erreicht.
Und das ist dann auch schon der Bellman-Ford-Algorithmus.
Und wie wir sehen werden, funktioniert dieser Algorithmus eben auch
für negative Kanten und für negative Zyklen.
Also, das schauen wir uns zuerst nochmal an, wie dieser Algorithmus
jetzt im Detail aussieht.
Also die ersten Schritte sind ähnlich wie beim Dijkstra-Algorithmus.
Wir initialisieren oder haben dieselben Daten, die wir auch genauso
initialisieren wieder.
Also wir haben ein Distanz-Array für jeden Knoten, das uns eben die
gesuchte Distanz angibt, wobei wir eben jetzt auch noch minus und plus
und endlich haben, um anzuzeigen, dass es eben mit plus und endlich
nicht erreichbar ist, mit minus und endlich, dass es keinen kürzesten
Pfad gibt.
Und dann haben wir auch wieder das Parent-Array, wie gehabt, um uns
eben die kürzesten Pfade zu registrieren.
Initialisierung von den Startknoten auch wie bisher.
Und jetzt kommt der neue Teil, der uns diese kürzesten Pfade
-Berechnungen durchführt.
Und zwar, was haben wir hier?
Wir haben eben, wie genannt, diese verschachtelte Schleife hier.
Also in der äußeren Schleife gehen wir einfach N minus einmal das
Ganze durch.
Und was berechnen wir in jeder Schleife?
Wir gehen alle Kanten in unserem Graph der Reihe nach durch, in
irgendeiner beliebigen Reihenfolge und relaxieren diese Kante.
Alle Kanten relaxieren in der inneren Schleife.
Und das Ganze einmal wiederholt.
Wir können uns auch noch mal kurz überlegen, was bedeutet das
Relaxieren in dieser inneren Schleife?
Am Anfang ist es so, dass die meisten Knoten immer ein Gewicht von
unendlich haben, bis auf den Startknoten.
Das heißt, wenn ich jetzt natürlich so einen Knoten mit Gewicht
unendlich mir rausnehme und eine von dort aus ausgehende Kante
relaxiere, dann erinnert sich damit eigentlich noch nichts dran, weil
der Zielknoten auch wieder Distanz unendlich hat.
Das heißt, da bleibt erstmal alles bei unendlich.
Aber diejenigen Knoten, die schon ein Gewicht ungleich unendlich haben
und die von dort aus ausgehenden Kanten, die werden eben in diesem
inneren Schritt modifiziert.
Und letztendlich, wenn wir das Ganze einmal durchgeführt haben, haben
wir eben das für alle Kanten gemacht.
Okay, also damit haben wir dann eigentlich schon mal alle kürzesten
Pfade soweit gefunden, bis auf die Sache, dass wir mit negativen
Zyklen jetzt noch keine korrekten Werte gesetzt haben.
Also das heißt, wir haben jetzt bei negativen Zyklen noch nicht das
Minus unendlich dran stehen.
Und das ist jetzt das, was hier in einem weiteren
Nachverarbeitungsschritt hier abläuft, dass man sich anschaut, welche
Knoten sind denn jetzt auf negativen Zyklen enthalten und für diese
Knoten setze ich dann die Distanz auf unendlich.
Also das ist hier dieser Nachverarbeitungsschritt, der hier jetzt
abläuft.
Was macht man?
Man schaut sich sämtliche Kanten an und prüft, ob das eine Kante ist,
die dieser minimalen Pfadeigenschaft noch widerspricht.
Also eigentlich müssten ja im vorhergehenden Schritt die kürzesten
Pfade berechnet sein.
Das heißt, wenn ich hier mal anschaue, die Distanz nach u plus die
Kosten von e ausgehen, müssten eigentlich dv ergeben für die kürzeste
Kante.
Wenn es aber nicht der Fall ist, wenn es kleiner als dv ist, dann
kann, wenn der Algorithmus bis dorthin korrekt ist, das nur passieren,
wenn wir einen negativen Zyklus haben.
Also diese Bedingung hier, dass du plus ce kleiner dv ist, zeigt uns
an, dass wir einen Knoten u unter dem Knoten v haben, die sich auf
einem negativen Zyklus befinden.
Oder zumindest der Knoten v hier.
Und was wir dann machen, ist, dass wir eben diesen Knoten v als
innerhalb eines negativen Zyklus markieren.
Und das passiert hier mithilfe dieser Infect-Funktion.
Also das heißt, diese Infect-Funktion soll den Knoten als nicht mit
einem kürzesten Pfad erreichbar markieren, weil er auf einem negativen
Zyklus liegt.
Und eben nicht nur den einen Knoten, sondern alle anderen von dort aus
erreichbaren Knoten auch, weil die ja eben auch über den negativen
Zyklus erreichbar sind.
Also was macht diese Infect-Prozedur?
Falls der Knoten noch nicht auf minus und endlich gesetzt wurde, den
Knoten v, dann wird er eben auf minus und endlich gesetzt, was uns
anzeigt, dass der eben innerhalb einem negativen Kreis liegt.
Dann schaut man sich jetzt an, alles, was von v aus erreichbar ist.
Also wir schauen uns alle von v aus ausgehenden Kanten an und die
entsprechenden Zielknoten v von diesen ausgehenden Kanten werden auch
infiziert, also über dieses Infect markiert, als nur mit Distanz minus
und endlich erreichbar.
Okay.
Und damit haben wir einen Algorithmus jetzt, der es uns erlaubt, auch
kürzestem Pfade mit negativen Kanten und mit Zyklen mit negativen
Gewicht zu berechnen.
Genau.
Und eben hier, wie gesagt, dieser v, der Hauptalgorithmus, der eben
die Kanten in einer beliebigen Reihenfolge relaxiert, so oft, bis es
eben garantiert ausreicht.
Das ist jetzt eben hier auch der Hauptunterschied, dass wir bei diesem
Algorithmus wissen, dass nach n oder n minus 1 Iterationen die alle
kürzesten Pfade vollständig berechnet sind.
Das heißt, der Algorithmus jetzt terminiert eben auch wirklich im
Gegensatz zu unserem Ursprüngchen oder im Vergleich zu dem
Ursprüngchen.
Dijkstra liefert eben auch die korrekten Ergebnisse bei negativen
Kanten.
Also das hatte ich schon dazu gesagt.
Also was gilt nach diesem Ausführen des Hauptteils des Algorithmus,
dieser doppelten Schleife vor der Nachverarbeitung?
Da gilt eben, dass für alle negativen Kreise gibt es eine solche Kante
uv auf dem Kreis, sodass diese Bedingung hier, dass die eben nicht
gleich sind, sondern dass die Distanz von u plus die Kosten der Kante
e kleiner als dv sind, dass diese Bedingung hier gilt und die eben
damit übereinstimmt, dass es einen negativen Zyklus hier gibt.
Und genau den Beweis, den möchte ich ja auch mal weglassen.
Aber die Aussage ist eben, dass von v aus und alle erreichbaren Knoten
eben eine Distanz von minus unendlich haben.
Gut, dann schauen wir uns das vielleicht nochmal hier an einem
Beispiel an, wie dieser Algorithmus arbeitet.
Also Bellman-Ford-Algorithmus jetzt hier.
Wir starten links oben, haben unseren Graph initialisiert.
Alle Knoten haben eine Distanz von unendlich.
Und was wir jetzt machen, wir schauen uns jetzt einfach an, was
passiert nach jeder Runde in diesem Algorithmus.
Wir haben ja diese n minus 1 Runden.
Und in jeder Runde werden alle Kanten einmal relaxiert.
Wenn man sich jetzt anschaut, also wenn ich zum Beispiel hier diese
Kante hier relaxieren würde, da passiert natürlich nichts, weil der
Startknoten eine Distanz von unendlich hat, hat der Zielknoten danach
auch eine Distanz von unendlich.
Das Einzige, was passiert, ist eben ausgehen von einem Knoten, der
eine Distanz unendlich hat.
Also hier relaxieren wir die ausgehenden Kanten, bekommen dann diese
Knoten hier dazu, die jetzt hier in der Mitte mit weiß markiert sind.
Wir haben da auch dann eben die aktuell kürzeste Distanz, 0 und minus
1 für diese Knoten jetzt, sind damit mit der ersten Runde schon
fertig, können dann weiter vorgehen.
Jetzt eben auch wieder alle Kanten relaxieren in diesem Graph.
Das betrifft auch wieder nur die weißen Knoten.
Also da kommen jetzt dann diese Knoten dazu und hier rechts diese
beiden Knoten, die jetzt eben eine neue aktuelle minimale Distanz
bekommen von rechts minus 3 und links 0.
Dann geht es hier rechts weiter mit der nächsten Runde.
Wieder ein Relaxationsschritt, wo weitere weiße Knoten dazukommen, bis
wir dann hier an dieser Stelle angekommen sind, wo wir jetzt noch
nicht alle N-Iterationen oder N-minus-1-Iterationen durchgeführt
haben, aber wo wir schon so weit sind, dass sich jetzt auch im
weiteren Verlauf nichts mehr ändern wird.
Das heißt, das ist dann praktisch das Endergebnis unserer
Hauptschleife, wo Sie sehen, dass auf der rechten Seite zum Beispiel
schon alles korrekt markiert wurde.
Und was wir jetzt machen müssen, ist eben dann nur noch diesen
Nachverarbeitungsschritt und zu prüfen, gibt es einen negativen Zyklus
oder gibt es negative Zyklen.
Und wie gesagt, die erkennen wir daran, dass eben das dU plus c von E
kleiner als dV ist.
Also wir müssen irgendwie so ein Knotenpaar finden, die mit der Kante
verbunden sind, so dass, wie es zum Beispiel jetzt hier eins gibt,
wenn wir hier von minus 1 nach 0 schauen, eigentlich, wenn wir sagen,
der rechte Knoten hier hat eine Distanz von minus 1.
Wir haben auf der Kante von minus 1 nach 0 haben wir ein Kantengewicht
von 0.
Dann müsste ja der linke Knoten auch ein Gewicht von minus 1 bekommen.
Oder eine Distanz von minus 1.
Aber das ist hier nicht erfüllt.
Das heißt, hier hat der Algorithmus dann praktisch abgebrochen und hat
es nicht weiter fortgesetzt, diese Relaxation zu machen, weil sie eben
schon ausreichend war.
Aber das ist diese Kante, die uns jetzt anzeigt, dass hier ein
negativer Zyklus vorhanden ist.
Und das heißt, wir können damit dann diesen Knoten hier markieren, als
innerhalb eines solchen negativen Zykluses.
Und wir gehen jetzt eben von diesem Knoten aus vor und machen diesen
Infekt -Schritt.
Das heißt, der hier wird als minus- und endlich gekennzeichnet und
alle von dort aus ausgehenden oder alle von dort aus erreichbaren
Knoten, also dieser hier und dieser hier und dieser hier.
Und die bekommen eben das Gewicht minus- und endlich dann zugewiesen.
Und damit haben wir dann hier rechts oben unser Endergebnis des
Bellman -Ford-Algorithmus.
Also, damit haben wir jetzt einen Algorithmus, einen weiteren aus der
Dijkstra, der uns eben auch erlaubt, mit negativen Kantengewichten und
mit negativen Zyklen umzugehen.
Gut, also jetzt haben wir zwei Verfahren.
Eines, das etwas mehr Fälle beherrscht als das erste Verfahren, was
wir hatten.
Jetzt können wir uns natürlich auch nochmal die Laufzeit anschauen,
die dieses Bellman-Ford-Verfahren hat.
Man kann sich vielleicht schon so grob überlegen, was wird denn
voraussichtlich die Laufzeit dieses Verfahrens sein.
Also hauptsächlich wird es wohl durch diese Schleife hier unsere
Laufzeit bestimmt sein, also diese verschachtelte Schleife.
Wir haben außen eine Schleife, die O von N Durchläufe macht und hier
innen eine Schleife, die über die Kanten geht, also O von M.
Also haben wir hier eine Laufzeit, die O von N mal M sein wird.
Schauen wir nochmal kurz.
Also die Laufzeit durch diese zwei Schleifen, eben die äußere, die die
Anzahl Knoten durchlaufen wird, die innere, die die Anzahl Kanten
durchlaufen wird, ergibt uns eben eine Laufzeit O von N mal M.
Also wenn man sagt, N und M sind vielleicht von der selben
Größenordnung, praktisch eine quadratische Laufzeit.
Aber verglichen mit Dijkstra, da haben wir M plus N mal Log N, also
nur die Summe, ist es natürlich viel langsamer.
Okay, das heißt, wir kaufen uns dieses vollständige Verhalten des
Algorithmus, des Behm-und-Ford-Algorithmus, dass er eben auch mit
negativen Zyklen umgehen kann, mit einer höheren Laufzeit.
Okay, also das heißt, Sie können dann eben auch jetzt je nach
Anwendung dann eben auswählen, welcher Algorithmus da der passendere
ist.
Wenn Sie keine negativen Kantengewichte haben, ist der Dijkstra
-Algorithmus, wie wir gesehen hatten, der zu bevorzugende Algorithmus.
Wenn Sie negative Kanten und Zyklen haben, ist der Behm-und-Ford
-Algorithmus derjenige, den Sie benötigen.
Genau, wobei man sich den natürlich auch noch genauer anschauen kann,
Behm -und-Ford und es gibt noch eine ganze Reihe von Stellen, wo man
den weiter optimieren kann.
Und wenn man sich das genauer anschaut, sieht man auch, dass es noch
Varianten gibt, die einen deutlich besseren Best-Case zumindest
führen.
Also im besten Fall ist es so, dass der Algorithmus nicht von N mal N
benötigt, sondern weniger Laufzeit.
Gut, jetzt haben wir gesehen, dass ein Großteil der Probleme ja durch
die Zyklen zustande kommt.
Also wenn wir negative Zyklen haben, dann ist es schlecht für den
Algorithmus.
Dann brauchen wir eben so etwas wie den Behm-und-Ford-Algorithmus mit
größerer Laufzeit.
Also schauen wir uns doch mal an, wie sieht das aus, wenn wir jetzt
zwar negative Kantengewichte haben, aber keine Zyklen.
Das heißt, wenn wir garantieren können, dass unser Graph a-zyklisch
ist, vielleicht gibt es ja noch etwas Besseres, was wir machen können.
Und dann natürlich, wenn es keine Zyklen gibt in unserem Graph, gibt
es natürlich auch keine negativen Zyklen oder keine negativen Kreise.
Und das heißt, wir haben dieses Problem zumindest schon mal vermieden,
dass wir irgendwelche Knoten haben, die mit Minus und Endlich markiert
werden müssten, sondern jedem Knoten können wir, wenn er erreichbar
ist, eine reale Zahl als Distanz zuordnen.
Okay, und dann ist es so, dass in dem Fall sogar es ausreicht, die
Kanten in einer bestimmten Reihenfolge zu betrachten.
Das heißt, man kann, wenn man feststellt, erstmal die Knoten
topologisch sortieren und dann die Kanten in der dadurch induzierten
Reihenfolge durchlaufen.
Also, was würde man machen?
Man würde eben auch wieder bei den Startknoten anfangen, die
entsprechende Initialisierung durchführen, wie bisher von allen
Knoten.
Und dann eben jetzt unsere Hauptschleife, würde dann einfach in einer
bestimmten Reihenfolge diesen Relaxationsschritt durchführen oder den
Scan -Schritt, der alle ausgehenden Kanten relaxiert.
Und zwar macht er das in topologischer Reihenfolge.
Und das heißt, in topologischer Reihenfolge, auch jetzt ohne Beweis
ist es so, dass dieses Verfahren auch wieder kürzeste Pfade berechnen
kann.
Überlegen wir uns nochmal kurz, was war topologische Reihenfolge?
Topologische Reihenfolge bedeutet, dass wir, wenn wir eine Kante
betrachten, also zum Beispiel diese hier, dass der Startknoten der
Kante in der Ordnung vor dem Zielknoten der Kante kommt.
Und so eine topologische Sortierung können wir natürlich vornehmen,
sobald ein Knoten zyklusfrei ist.
Also hier können wir sagen, das ist unser Knoten 1, in der Reihenfolge
das wäre Knoten 2, das hier wäre Knoten 3, das hier wäre Knoten 4 und
so weiter.
Damit garantiert das immer der Startknoten von jeder Kante eine
geringere Ordnung, eine geringere Zahl hier zugeordnet bekommt als der
Zielknoten.
Und in dieser Reihenfolge können wir dann eben auch die Kanten uns
anschauen.
Also wenn wir jetzt hier bei dem Startknoten wären, würden wir eben 5,
6, 7, 8, 9.
Das wäre zum Beispiel so eine topologische Sortierung.
Können wir sich eben zuerst diese Kante 1 nach 4 anschauen, dann vom
Startknoten nach 4, dann nach 5, dann nach 6 und so weiter.
Und eben in dieser topologischen Reihenfolge die kürzeste
Pfadberechnung vornehmen.
Das ist ein Algorithmus, der auch für atyklische Graphen ein korrektes
Ergebnis liefert.
Und der hat auch eine gute Laufzeit, der ist eben, wenn man sich
relativ einfach auch überlegen kann, wenn man sich das hier nochmal
anschaut, ist das in Laufzeit O von M plus N möglich.
Okay, also hier hatten wir noch eine Variante der Algorithmen.
Der funktioniert, wie gesagt, auch bei negativen Kantengewicht.
Und wenn die Graphen eben atyklisch sind, also keinen Zyklus
aufweisen.
Also da haben wir jetzt auch nochmal einen Spezialfall, in dem der
Algorithmus besser funktioniert.
Und das ist eigentlich auch wieder so eine typische Erscheinung bei
Algorithmen, dass wenn sie jetzt einen allgemeinen Algorithmus haben,
dass sie dann häufig irgendwelche Teilklassen von Problemen haben mit
bestimmten schönen Eigenschaften, die es erlauben, noch optimiertere
Algorithmen zu entwickeln für diese Teilklassen.
Also so, wie man jetzt hier eben für diese atyklischen Graphen einen
relativ einfachen, besseren Algorithmus noch gefunden hat.
Dann können wir uns auch noch ein paar Varianten des Algorithmus
anschauen.
Also was hatten wir bisher?
Wir hatten bisher uns überlegt, kürzester Weg von einem Startknoten
aus zu allen anderen Knoten.
Jetzt gibt es natürlich eine Reihe von Problemen, in denen man nicht
jetzt genau an dieser Fragestellung interessiert ist.
Und also eine Variante wäre zum Beispiel, ich möchte nur von einem
Startknoten zu einem Zielknoten wissen, was da die kürzeste Distanz
ist.
Das ist vielleicht die typischste Anwendung, die auch in der
Routenplanung eben auftritt.
Sie möchten von einem Ort zu einem anderen Ort kommen und sie
interessiert nicht die kürzeste Pfade irgendwo ganz anders hin.
Aber es gibt auch Anwendungen, wo das andere extrem interessant ist.
Das heißt, wenn Sie von jedem Startknoten zu jedem Zielknoten die
minimale Distanz berechnen wollen.
Da sehen wir nachher auch noch Beispiele, wo das sinnvoll sein kann,
auch in der Routenplanung zum Beispiel.
Und wie kann man das machen?
Man kann natürlich sagen, ja, ich lasse einfach den einen der
Algorithmen, zum Beispiel den Dijkstra-Algorithmus oder den Bam und
Ford -Algorithmus, einmal laufen für jeden Startknoten einmal und dann
bekomme ich darüber die kürzesten Pfade von jedem Knoten zu jedem
Knoten geliefert.
Wenn wir das mit nicht negativen Kantengewichten haben, also wir
nehmen jetzt wieder an, dass Typen auch möglich sind, dann hat dieser
Algorithmus eben nochmal einen Faktor N zusätzlich in der
asymptotischen Laufzeit.
Also dieses N hier vorne kommt noch dazu.
Wenn wir negative Kanten haben, dann den Bam und Ford-Algorithmus
anwenden müssen, dann kommt natürlich auch ein Faktor N dazu.
Das heißt, statt N mal M haben wir jetzt hier eben eine Laufzeit von N
Quadrat mal M.
Okay, genau.
Also das ist relativ naheliegend, eine Variante um damit oder eine
relativ triviale oder naive Variante, um von jedem Start zu jedem
Zielknoten ein kurzes Gesamt zu berechnen.
Aber wie gesagt, eben zum Beispiel im Fall von Bam und Ford jetzt
nicht mit besonders guter Laufzeit, wobei Sie noch sehen werden in der
Algorithmen -II-Vorlesung, dass sich das noch deutlich verbessern
lässt.
Also statt diesem O von N Quadrat mal M lässt sich das auf O von N mal
M plus N log N reduzieren, indem man einmal oder geschickt diese
Algorithmen Bam und Ford und Dijkstra kombiniert und mit einem
Durchlauf des Bam und Ford-Algorithmus bereits alle Informationen über
negative Zyklen einsammelt und danach eben dann den Dijkstra
-Algorithmus nur noch anwenden muss mit einer besseren Laufzeit.
Okay, also diese Variante gibt es auch noch.
Und wenn wir das jetzt soweit mal zusammenfassen wollen, was haben wir
gesehen für die kürzesten Wege-Algorithmen?
Erstmal ja, es gibt relativ gute Algorithmen für Spezialfälle, eben
für den Fall der nicht negativen Kantengewichte oder für den
Spezialfall, dass es sich um asyklische Graphen handelt.
Da kann man eben den Dijkstra-Algorithmus anwenden mit guter
asymptotischer Laufzeit.
In anderen Fällen braucht man eben einen Algorithmus, der nicht ganz
so schnell läuft wie den Bam und Ford.
Und der Beweis, dass diese Algorithmen optimale Lösungen liefern, ist
zum Teil auch nicht so ganz trivial, aber immer noch ganz gut machbar.
Wobei wir auch gesehen haben, dass wir hier so ein erstes schönes
Einsatzgebiet auch hatten für unsere Prioritätslisten.
Eben bei Dijkstra-Algorithmus, wenn wir immer den Knoten mit der
aktuell geringsten Distanz finden wollen, da war die Prioritätslisten
-Datenstruktur genau die richtige.
Gut, also soweit bis dahin erstmal.
Und noch ein paar weitere Varianten, die man noch betrachten kann.
Also man kann versuchen, auch statt den Prioritätslisten andere
Datenstrukturen zu verwenden.
Also eine andere Variante der Prioritätslisten liefert dann hier eine
Laufzeit von M plus N log log N.
Also was ist der Unterschied?
Statt N log N haben wir N log log N drin stehen.
Also das ist schon mal wieder ein Stück besser.
Aber man muss sagen, in der Praxis spielt das häufig keine so große
Rolle.
Also wenn Sie sich auch nochmal überlegen, wie unterscheiden sich log
N und log log N?
Also selbst auf sehr großen Eingaben ist es so, dass log N häufig
klein genug ist, dass log log N dann nicht mehr einen großen
Unterschied macht.
Ja, ich glaube, die haben wir so grob schon mal abgeschätzt.
Also wenn Sie jetzt zum Beispiel N jetzt eine Milliarde ungefähr
hätten, also ein Graph mit einer Milliarde Knoten, das wäre dann der
Zweierlogarhythmus von einer Milliarde ist so ungefähr 30.
Und genau das heißt, wenn Sie haben dann N mal 30 hätten Sie als
Komplexität, wenn Sie es begrenzen, auf eine Milliarde Operationen.
Das heißt, es ist eigentlich noch in vernünftiger Zeit machbar.
Und log log N wäre dann eben nur das fünfte oder vier Komma irgendwas
statt 30 und auch kein so großer Unterschied.
Also in der Praxis ist es häufig so, dass diese Algorithmen nicht mehr
oder nur auf sehr, sehr großen Problemen noch einen Unterschied machen
und eher von theoretischem Interesse sind.
Gut, was vielleicht in der Praxis relevanter ist, ist, dass man
mehrere Zielfunktionen hat.
Also das kennen Sie auch von Ihrer Routenplanung.
Sie interessiert da unter Umständen eben nicht nur der Weg mit der
geringsten Distanz, wenn Sie eben über irgendwelche kleinen Straßen
führt, die Sie nur langsam fahren können oder falls irgendwelche Staus
auf diesen Strecken auftreten.
Das heißt, Sie haben da als zweite Zielgröße häufig auch noch die Zeit
mit dabei.
Und das liefert dann natürlich wieder andere Algorithmen, wenn Sie
eben nicht nur einen Distanzbegriff haben, sondern mehrere
Distanzbegriffe und die irgendwie gewichten wollen, welche Eigenschaft
Ihnen eben wichtiger ist.
Gut, andere Varianten sind dann noch mehrere Ziele in beliebiger
Reihenfolge anfahren.
Das spielt vielleicht in der Logistik oder Transportwesen eine gewisse
Rolle.
Wenn Sie als Paketauslieferer bestimmte Stationen anfahren müssen oder
als Spedition, dann interessiert sich, was ist der kürzeste Weg, um
mehrere Ziele gleichzeitig anzufahren.
Oder es gibt dann auch Varianten, z.B.
mehrere disjunkte Wege, also wo Sie nicht dieselben Straßen wieder
befahren.
Und überraschenderweise ist es so, dass diese Probleme alle eine sehr
schlechte Laufzeitkomplexität haben oder überraschend schwierig sind.
Also dieses Problem, mehrere Ziele in beliebiger Reihenfolge
anzufahren und dann den kürzesten Weg noch zu finden, das ist ja im
Grunde das Problem des Handlungsreisenden oder Travelling Salesman
oder Travelling Salesperson Problem.
Und das ist eben NP schwer und damit eigentlich nach aktuellem Wissen
nur in exponentieller Zeit zu lösen.
Okay, Sie sehen, es gibt auch in der Praxis noch interessante
Varianten dieses kürzesten Wege Problems, die zum Teil nochmal
erweiterte Algorithmen erfordern.
Wenn wir schon bei der Praxis sind, möchte ich noch auf die
naheliegendste Anwendung dieser kürzesten Pfade Algorithmen eingehen,
und zwar die Berechnung von Routen in Straßennetzwerken.
Das ist etwas, woran hier am KIT auch sehr stark geforscht wurde in
den letzten 10, 15 Jahren und wo auch eine Reihe von guten Algorithmen
entwickelt wurden, die es erlauben, eben wirklich in der Praxis gute
Verkehrs - oder Navigationssysteme zu entwickeln.
Und dazu möchte ich jetzt noch ein bisschen was sagen.
Einer der Karlsruher Forscher aus den Algorithmengruppen, der ist in
Zwischenzeit auch bei Apple für die Apple Maps zuständig.
Und wenn ich richtig informiert bin, in Zwischenzeit sogar Leiter von
Apple Maps.
Das heißt, der ist jetzt hier über die Algorithmenentwicklung am KIT
zu der Entwicklung von Praxisverfahren gekommen, die auch wirklich
einen sehr, sehr großen Einsatzbereich haben.
Also genau, das ist vielleicht auch etwas, was auf Sie in Zukunft
zukommt.
Vielleicht nicht mit Verkehrsplanungsalgorithmen, aber über
Algorithmen, sehen Sie, haben Sie die Möglichkeit, auch ganz
interessante Stellen in der Industrie zu bekommen.
Wenn man sich jetzt also anschaut, Straßenroutenplanung, dann erstmal
versuchen wir ein bisschen zu orientieren, was ist denn so die
Größenordnung von dem Grafen, den man hier zu tun hat.
Und so grob kann man sagen, also wenn man sagt, innerhalb von
Westeuropa möchte ich navigieren, dann sind es ungefähr 18 Millionen
Knoten, mit denen man zu tun hat.
Also 18 Millionen Ortspunkte, zwischen denen eben die Entfernungen
berechnet werden können.
Was man auch feststellt, ist, dass der Graf sehr dünn besetzt ist.
Das heißt, Sie haben eben wenige Straßen von allen möglichen
Kombinationen, die eben gehen.
Also wenn Sie sich jetzt eben jeden Ortspunkt anschauen, sind eben nur
wenige dieser Ortspunkte direkt mit einer Straße verbunden.
Also Sie haben ja nicht eine Straße jetzt hier vom KIT aus direkt nach
Berlin, sondern das geht eben nur zu anderen naheliegenden
Ortspunkten.
Das heißt, die Anzahl der Kanten ist ungefähr in der Größenordnung von
N.
Außerdem sind die Grafen beinahe planar.
Zum Teil gibt es Algorithmen, die auf planaren Grafen besser arbeiten.
Was bedeutet planar?
Planarer Graf ist einer, der sich im Zweidimensionalen ohne Kreuzungen
von Kanten darstellen lässt.
Also den Sie auf dem Blatt Papier zeichnen können, ohne dass sich die
Linien von den Kanten überkreuzen.
Das ist eigentlich auch einfach ersichtlich.
Also man hat eben relativ wenige Kreuzungen, die nicht durch einen
Ortspunkt wieder markiert sind.
Das ist zum Beispiel Brücken, wo sie eben nicht von einer Richtung
jetzt direkt in die andere kommen können.
Und was wir auch sehr deutlich sehen bei Straßennetzwerken ist, dass
es eine gewisse Hierarchie gibt.
Das heißt, Sie haben irgendwelche kleineren Straßen, die für kürzere
Verbindungen relevant sind.
Und Sie haben eben zum Beispiel Autobahnabschnitte, die für längere
Strecken relevant sind.
Aber es gibt eben diese Ordnung von wichtigen zu weniger wichtigen
Straßen.
Gut, die Anwendung kennen Sie natürlich.
Routenplanung im Internet, Google Maps und was es sonst noch so gibt.
Fahrzeugnavigationssysteme, die eben eingebaut sind und von den
Fahrzeugherstellern ausgeliefert werden.
In der Logistik spielt es eine gewisse Rolle, eben wie gesagt bei
Speditionen oder Paketauslieferdiensten.
Oder auch in der Verkehrssimulation, wenn Sie eben Stausimulationen
zum Beispiel betreiben wollen und irgendwelche Annahmen machen, wie
sich die Leute verhalten, wenn sie eine bestimmte Strecke abfahren.
Dann können Sie da auch solche kürzesten Straßennetzwerkverbindungen
dazu benötigen.
Okay, dann hatten wir vorhin auch schon ganz kurz besprochen.
Im Normalfall ist man jetzt hier im Gegensatz zu Dijkstra nur an einem
Ziel interessiert.
Das heißt, ich möchte nur von einem Startknoten und zu einem
Zielknoten im Normalfall wissen, was da die Distanz ist.
Was man machen kann, ist man kann einfach den Dijkstra-Algorithmus so
lang laufen lassen, bis eben der Knoten, der gerade Ziel sein soll,
bis der bearbeitet wurde.
Dann kann man sozusagen so im Groben fällt dadurch die Hälfte weg.
Die Frage, die sparen wir uns mal kurz.
Und dann gibt es eben jetzt von diesen Praxisanwendungen, wie gesagt,
eine ganze Reihe von Möglichkeiten, wie man diese Algorithmen jetzt
noch weiter optimieren kann.
Also das eine hatten wir schon angesprochen, das ist die Hierarchie
von Straßen, dass es eben weniger wichtige oder für große Entfernungen
gibt und wichtiger für große Entfernungen.
Was man auch machen kann, ist man kann so eine Vorwärts- und
Rückwärtssuche kombinieren.
Also statt jetzt, wie es hier rechts oben angedeutet ist, jetzt
einfach von S direkten Pfad nach T zu berechnen, kann ich versuchen,
von beiden Seiten aus zu arbeiten und eben zu versuchen, irgendwie
Punkte zu finden, wo sich das eben verbindet.
Also ähnlich, wie es in einem Tunnel, im Normalfall auch eben von
beiden Seiten gebohrt wird, ist es hier so, dass man eben diese
kürzeste Pfadberechnung von beiden Seiten aus vornehmen kann.
Das liefert dann unter Umständen auch bessere Algorithmen.
Was anderes, was man auch noch hat, ist die Graphen, wie wir sie
bisher betrachtet hatten, die waren ja mit keinen geometrischen
Informationen bezeichnet.
Das kann man natürlich auch noch hier versuchen mit zu
berücksichtigen.
Also wenn ich jetzt von hier aus nach Stuttgart fahren möchte, dann
ist es vielleicht wenig gewinnbringend, erstmal in die
entgegengesetzte Richtung zu fahren, sondern dann kann man diese
geometrische Information einfach noch versuchen auch noch mit
einzubeziehen, um dann eben so eine zielgerichtete Suche zu
ermöglichen.
Und ein relativ wichtiges Verfahren dazu, um solche Berechnungen noch
zu beschleunigen, ist, dass man für Teilabschnitte versucht, schon
vorab zu berechnen, was die optimalen Routen sind.
Also ich versuche für wichtige Teilstrecken, die immer wieder
auftauchen, schon mal im Vorab zu berechnen, was denn da die kürzeste
Entfernung ist.
Und darauf möchte ich jetzt noch ein bisschen näher eingehen.
Dieses Verfahren, dass man versucht, für wichtige Teilabschnitte schon
im Vorab Teilrouten zu berechnen, das nennt sich auch Transit Node
Routing und ist auch ein Verfahren, das hier am KIT mitentwickelt
worden ist.
Und das sehen Sie schon hier, also Sie haben hier einen Startknoten
und einen Zielknoten und zwischendrin eben dieses Netzwerk, wo Sie für
eine Teilmenge der Knoten möglicherweise alle Verbindungen schon
berechnet haben, was da die kürzesten Wege sind.
Aber wie das genau funktioniert, das möchte ich Ihnen an einem
Beispiel noch zeigen.
Und zwar, wir schauen uns einfach mal verschiedene solche Routenplaner
-Anfragen an und wie sie sich dann auswirken.
Also nehmen wir an, Sie wollen jetzt von Karlsruhe, vielleicht hier
vom vordersten Gebäude aus, nach Kopenhagen fahren, dann könnte ein
kürzester Weg dorthin so aussehen.
Wenn Sie nach Berlin fahren wollen, dann sehen Sie, der läuft ein
bisschen weiter südlich.
Wenn Sie nach Wien fahren wollen, dann hat der unten vielleicht sogar
ein ähnliches Stadtstück wie der Weg nach Berlin, aber verläuft dann
doch irgendwo anders.
Also Sie sehen schon, die Wege, die Sie fahren müssen, unterscheiden
sich natürlich relativ deutlich.
Aber wenn wir jetzt mal einfach nur uns die Anfangsstücke anschauen,
also wie beginnt Ihre Fahrt von Karlsruhe nach Kopenhagen?
Dann sehen Sie ja, das sieht so aus, dass Sie hier relativ schnell
über die Durlacher Allee auf die Autobahn fahren und das ist eben der
Start Ihres kürzesten Weges nach Kopenhagen.
Wenn man jetzt mal schaut, wie sieht es aus, wenn ich nach Berlin
fahren möchte, sieht der Start genauso aus.
Also ich nehme da genau den gleichen Startweg, um auf die
Autobahnauffahrt zu kommen und von da aus geht es dann eben
unterschiedlich weiter.
Nach Wien genau das gleiche Anfangsstück.
Auch da ist es so, dass man erstmal auf diesen Autobahnzugang fährt.
Nach München hat es jetzt einen anderen Startknoten berechnet, da
würde es die einstwählter südlich liegende Auffahrt verwenden.
Genau, das heißt über die Osttangente fährt er dann auf die Autobahn.
Wenn wir weiter schauen, nach Rom würde er auch diesen Punkt wählen.
Nach London geht es in die andere Richtung und man erreicht dann auch
einen Knotenpunkt auf der linken Seite.
Nach Brüssel genauso.
Aber was Sie sehen ist jetzt, dass alle diese verschiedenen Anfragen
doch immer über eine relativ geringe Anzahl von Knotenpunkten laufen,
nämlich diejenigen, die hier blau markiert sind.
Und das heißt, diese blau markierten Punkte, die spielen jetzt wohl
irgendwie eine zentrale Rolle in der Routenplanung.
Dass man die eben verwenden kann, um so eine Trennung zu machen, in
erstmal kürzere Strecken lokal zu fahren, die eben über solche
Knotenpunkte gehen und von dort ausgehend werden dann eben größere
Strecken verwendet.
Und für diese größeren Strecken können wir eben versuchen, dann schon
eine Vorabberechnung vorzunehmen, was die kürzesten Wege von diesen
blauen Knotenpunkten aus sind zu irgendwelchen anderen blauen
Zielpunkten.
Also hier nochmal die Beobachtung.
Lange Strecken benutzen nur wenige wichtige Zugänge zum
Fernverkehrsnetzwerk.
Diese blauen Punkte, die wir gerade gesehen haben.
Und die kann man auch als Access Points bezeichnen, also als
Zugangspunkte zu diesem Fernverkehrsnetzwerk.
Und was man eben jetzt machen kann, ist, dass man versucht, diese
wichtigen Punkte im ersten Schritt rauszufinden und zwischen den
wichtigen Zugangspunkten, zwischen diesen blauen Punkten, schon mal
kürzeste Wege zu berechnen.
Und hier noch kurz, um auch so ein Gefühl für die Größenordnung zu
kriegen.
In Europa ist es so, dass man im Schnitt ungefähr 10 Zugangspunkte für
beliebige Knoten im Mittel halt.
Also wenn ich hier irgendeinen ganz beliebigen Startpunkt vorgebe,
dann sind für diesen Knoten 10 Zugangspunkte in das Fernverkehrsnetz
im Schnitt relevant.
Okay.
Genau, also hat man gesehen, von Karlsruhe nach Berlin führt dann eben
über so einen bestimmten blauen Punkt dann.
Genau,
das heißt, man kann jetzt diese Berechnung, wenn man jetzt innerhalb
von Karlsruhe von verschiedenen Startpunkten ausgeht, eben berechnen
als erstmal in Entfernung zu einem blauen Zugangspunkt.
Also wenn ich hier, was ist das so, in der Südweststadt irgendwo
starte, dann geht es eben über den rechten unteren blauen
Zugangspunkt.
Wenn ich weiter nördlich starte, geht es über den Adenauering und dann
über den oberen blauen Zugangspunkt.
Aber oder hier auch ein weiterer Start innerhalb von Karlsruhe führt
auch wieder den blauen oberen Zugangspunkt.
Also man sieht innerhalb von dieser Region Karlsruhe ist es so, dass
diese ganzen beliebigen Startwerte alle über so einen Access-Point
führen.
Also jeder solcher Access-Punkt ist für mehrere Startknoten relevant.
Und die Gesamtmenge von diesen Access-Points ist relativ gering.
Die kann man auch als Transit-Knotenmenge bezeichnen und dann kann man
eben versuchen, in einem Vorverarbeitungsschritt die Entfernungen
zwischen allen diesen Transit-Knoten zu berechnen.
Und das sind in Europa ungefähr 10.000 Transit-Knoten.
Das heißt, man könnte jetzt für so einen Routenplanungsalgorithmus in
einem ersten Schritt alle kürzesten Pfade berechnen zwischen allen
diesen 10.000 Punkten.
Und damit hat man dann das Problem schon mal so ein bisschen zerlegt.
Also wie sieht diese Vorverarbeitung aus?
Man versucht erst mal, diese Transit-Knoten irgendwie rauszufinden,
welche das sind, also was die wichtigen Punkte sind, die für dieses
Fernverkehrsnetz relevant sind.
Dann berechnet man die kürzeste Pfade zwischen allen diesen Punkten
hier.
Da ist dann eben auch so ein Algorithmus wichtig, wie wir noch vorher
kurz angedeutet hatten, von jedem Startpunkt zu jedem Zielpunkt zu
kommen.
Und was man dann auch noch macht, ist, dass man für jeden Knoten, also
für jeden beliebigen Punkt in dem Routenplanungsnetzwerk, die
Zugangsknoten dem zuordnet, die für diesen Knoten relevant sind.
Also zum Beispiel jetzt hier für die Adresse von dem Hörsaal, wird man
jetzt eben zuordnen, was sind die relevanten Transit-Knoten.
Das sind wahrscheinlich eben diese fünf bis zehn blauen Punkte, die
wir vorher gesehen haben, die für eigentlich alle größeren
Verbindungen benötigt werden.
Und das heißt, so eine Abfrage, um von einem Startknoten zum
Zielknoten zu kommen, die wird dann eben berechnet.
Also die beste Entfernung zwischen S und T mit diesem Transit
-Knotenrouting, indem man eben minimiert eine Streckenplanung, die aus
drei Teilen zusammengesetzt ist.
Einmal eben vom Startknoten zu einem ersten Transitknoten.
Dann von diesem Starttransitknoten U zu einem Transitknoten, der dem
Ziel nahe liegt.
Das wäre der Knoten V dann.
Und dann noch ein dritter Abschnitt der Strecke, der von diesem
zielnahen Transitknoten dann zum eigentlichen Ziel führt.
Und diese Berechnung macht man eben über sämtliche Transitknoten, die
für den Startknoten relevant sind.
Also für den Startknoten ist das die Menge AS, die wir oben ja
angegeben hatten, die uns die möglichen Transitknoten dafür angibt.
Genauso für den Zielknoten.
Und über die berechnen wir dann eben die...
können wir diese dreigeteilte kürzeste Streckenberechnung machen.
Dann, was man auch noch berücksichtigen sollte, ist, wenn Sie jetzt
innerhalb von Karlsruhe Ihren Start- und Zielknoten haben, dann ist es
wahrscheinlich so, dass es sich nicht lohnt, über Transitknoten zu
fahren.
Also wenn Sie innerhalb von Karlsruhe jetzt ein Ziel erreichen wollen,
mögen Sie vielleicht nur ein paar Häuser weiter.
Macht natürlich wenig Sinn, erstmal zu einer Autobahnauffahrt zu
fahren und dann wieder zurück.
Also man möchte irgendwie die lokalen Fälle noch ausfiltern können und
für die eine Spezialbehandlung machen, für die eben nicht die Strecke
über so einen Transitknoten führt.
Aber wenn es sich nicht um einen Lokalfall handelt, also wenn Sie eine
längere Strecke fahren, dann soll eben diese Distanzberechnung über
diese Transitknoten gehen.
Also hier kann man sich das auch nochmal anschauen.
Wir haben jetzt eben für so einen Startknoten mit dieser roten Fahne
markiert, bestimmte Transitknoten mit diesen roten Rauten markiert,
die man versuchen würde als erstes anzufahren und von da aus eben zu
einer blauen Raute zu kommen, die nahe am Ziel ist und von dort aus
dann den blauen Zielknoten zu erreichen.
Wenn man sich das jetzt mal anschaut, was kommt dabei raus, wenn man
das jetzt für das Europäische Straßennetzwerk so implementiert?
Also wenn man diese Transitknoten umsetzt, dann sieht man, die
Anfragen, um einen kürzeren Weg zu finden, sind extrem schnell
möglich.
Also man kann innerhalb von 4 Mikrosekunden eine Berechnung von einem
Start - zu einem Zielpunkt hinbekommen.
Das ist im Vergleich zu einem Standard-Dijkstra-Algorithmus, den Sie
ja jetzt schon kennen, der aber eben viele Informationen dann noch
nicht berücksichtigt, um bis zu eine Million Mal schneller oder mehr
als eine Million Mal schneller.
Dieses Verfahren, das hat auch an einem akademischen Wettbewerb
teilgenommen, zur schnellsten Routenplanung und hat das damals auch
gewonnen.
Die Vorberechnungszeit, um eben diese Matrix zwischen den Access
-Points zu berechnen, hält sich einigermaßen in Grenzen, muss ja auch
nur einmal gemacht werden.
Die war jetzt in dem Fall ca.
75 Minuten, also etwas mehr wie eine Stunde.
Und auch der Speicherplatzbedarf ist relativ überschaubar für das
Verfahren.
Und das ist in der Zwischenzeit auch noch weiter verbessert worden
hier.
Also in der Zwischenzeit ist es so, dass es unter 2 Mikrosekunden
geht, die Anfrage.
Dann diese Präprozessorzeit braucht auch in der Zwischenzeit nur noch
5 Minuten und nicht mehr 75 Minuten.
Und auch der Speicherplatzbedarf konnte noch weiter gesenkt werden.
Ok.
Und wenn man sich das in der Praxis jetzt anschaut, ist es eigentlich
so, dass die Routenplanungszeit, eine Sekunde noch, dass die
eigentlich nicht mehr wirklich das Limitierende ist.
Also Berechnungszeiten von 2 Mikrosekunden oder 4 Mikrosekunden, das
ist so, dass da selbst die Übertragungswege im Netzwerk, wenn Sie
einen Online-Routenplaner verwenden, deutlich länger sind oder auch
die grafische Darstellung bereits auf dem Bildschirm deutlich mehr
Zeit benötigt, als dieses Routenplanungsproblem zu berechnen.
Also in dem Fall ist es so, dass es wirklich ein sehr überzeugendes
Feld ist, in dem die Algorithmentechnik sehr gut funktioniert hat, wo
man eben wirklich sehr schöne Algorithmen in der Zwischenzeit hat, um
schnell die Routenplanung durchzuführen.
Sie hatten noch eine Frage.
Ja, sagen Sie nochmal, dass die 75 Minuten haben sich auf 5 Minuten
reduziert.
Genau, ich bin mir nicht ganz sicher, was da die Algorithmen waren,
die hinter dieser Reduktion stecken.
Also ich hatte ja ein paar Namen hier auf den Folien zum Teil auch
stehen von Autoren.
Da würde ich Ihnen einfach mal empfehlen, wenn Sie da mal, ja, jetzt
finde ich es gerade nicht, einfach mal reinschauen in die
Publikationen.
Da finden Sie bestimmt dann weiteres noch, wie diese
Vorberechnungsverfahren genau aussehen.
Also letztendlich geht es eben darum, das, was wir hier in der Mitte
sehen, diese Matrix mit den schwarzen Punkten, die eben einmal zu
berechnen.
Und ich vermute mal, dass das eben am Anfang mit 1.15 eben einfach
kein besonders optimiertes Verfahren war, sondern dass man gesagt hat,
ja, wenn das nur einmal durchgeführt werden muss für das gesamte
Netzwerk, dann macht es eigentlich nichts aus, wenn es eine Stunde
dauert.
Im Grunde muss es ja nur neu berechnet werden, wenn sich irgendwas an
der Straßenführung verändert.
Also wenn eine neue Autobahn dazukommt, wenn irgendeine gesperrt ist
vielleicht.
Aber 5 Minuten ist natürlich auch besser.
Und man kann auch dazu sagen, heutzutage geht es ja auch sehr stark
darum, um eben aktuelle Verkehrsdaten mit einbeziehen zu können.
Also wenn Sie Staumeldungen mit einbeziehen möchten oder sehr schnell
auf Änderungen reagieren, wenn ein Unfall passiert oder wenn eine
Streckensperrung passiert, dann spielt es natürlich wieder eine Rolle,
wie man sehr schnell auch Updates an diesem Graph vornehmen kann, um
auf solche Situationen reagieren zu können.
Okay, gut.
Also das sind so die Techniken, die in realen Routenplanern in Ihrem
Fahrzeug oder bei Google Maps oder sonstigen Online-Routenplanern
verwendet werden.
Bei dem Verfahren, was ich Ihnen hier gerade gezeigt habe, habe ich
ein paar Fragen noch nicht beantwortet.
Zum Beispiel die Frage, wie bestimmen wir denn, was ein Transitknoten
ist?
Und da gibt es auch eben Verfahren, wie man das machen kann.
Dann, wie kann man die Zugangsknoten effizient bestimmen?
Also für einen bestimmten Ort?
Was sind denn die relevanten Transitknoten?
Dann, wie implementiert man so einen Lokalitätsfilter?
Der einem eben angibt, wann es sich nicht lohnt, über die
Transitknoten zu gehen.
Und damit zusammenhängend eben auch die Frage, wie geht man mit
lokalen Anfragen um, die eben nur in einem relativ kleinen Bereich
sind, die auch anders behandelt werden müssen.
Okay, gut.
Man kann allgemein sagen, andere Routenplanungstechnik verwenden oder
sich die Algorithmen etwas genauer anschauen.
Gut, damit sind wir dann mit dem Kapitel der kürzesten Wege auch am
Ende.
Gibt es von Ihrer Seite gerade noch Fragen dazu?
Gut, das scheint nicht der Fall zu sein.
Dann würden wir uns noch die letzten fünf Minuten noch mit dem
nächsten Thema, das ist noch von heute, beschäftigen, mit dem wir dann
am Mittwoch fortsetzen wollen.
Und zwar geht es hier um ein Problem, das etwas verwandt ist, den
kürzesten Wegen, was aber nochmal einen bisschen anderen Aspekt
aufweist, aber auch in einigen Praxisanwendungen eine Rolle spielt.
Und das ist das Problem der sogenannten minimalen Spannbäume.
Also nehmen Sie an, hier, Sie haben zum Beispiel diese Inseln, die mit
Booten untereinander erreichbar sind.
Und die Frage ist jetzt zum Beispiel, wie können Sie es schaffen, dass
diese Inseln alle untereinander erreichbar sind mit minimalen
Verbindungszeiten zwischen den Inseln?
Also Sie wollen, dass Sie von jeder Insel aus jede andere erreichen
können, können wollen und die Zeiten sollen minimal sein.
Schauen wir uns vielleicht mal die formale Definition an von diesem
Problem.
Also wir haben jetzt hier im Gegensatz zu bisher keinen gerichteten
Graph mehr, sondern wir haben jetzt einen ungerichteten Graph.
Das heißt, es geht nur noch nicht mehr um die Richtungen, mit denen
zwei Knoten verbunden sind, sondern nur, ob eine Verbindung besteht
oder nicht.
Dann haben wir natürlich wieder die Knoten und Kanten wie bisher.
N Knoten, M Kanten.
Wir haben auch wieder Kantengewichte wie bei unseren kürzesten
Pfadproblemen.
Und worum es jetzt geht, ist, wir wollen einen Baum finden mit
minimalem Gewicht, der alle Knoten miteinander verbindet.
Also minimales Gewicht bedeutet jetzt hier, dass die Summe über die
Kanten minimal sein soll.
Also wenn wir hier nochmal schauen, wir haben hier die Inseln.
Wir wollen, dass jede Insel mit jeder verbunden ist.
Und wir können jetzt annehmen, dass das vielleicht jetzt hier diese
Zahlen die Kosten angeben, um eine bestimmte Verbindung zu
realisieren.
Und wir wollen eben die Summe dieser Kosten möglichst gering halten
und trotzdem alle Inseln erreichen können.
Und jetzt kann man sich überlegen, also wie können wir das machen?
Also wir könnten zum Beispiel diese Kante hier auswählen.
Dann wäre die Insel B und D mit Gewicht 2 verbunden.
Wir können hier vielleicht diese Verbindung hier auswählen.
Dann wären B und C verbunden und dann auch diese Verbindung hier.
Und die Gesamtkosten für dieses Verbindungsnetzwerk wären dann eben
für diese, diese und diese Verbindung.
Also 6 plus 3 plus 2.
Also mit Kosten von 11 könnten wir das erreichen, dass diese Inseln
alle miteinander verbunden sind.
Und Sie sehen auch, hiermit wäre es jetzt möglich, eben von jeder
Insel auf jede zu kommen, indem man eben einen bestimmten Pfad hier
abläuft.
Und die Frage ist eben, jetzt ist das hier das Netzwerk, wird es uns
die günstigste oder mit geringster Gesamtsumme der Gewichte eine
solche Verbindung erlaubt zwischen allen Knoten im Graf?
Das könnte jetzt hier der Fall sein.
Also wenn man auf diese Verbindung hier verzichten würde, könnte man
natürlich auch die untere hier nehmen.
Dann hätte dann diese Kante 4 drin.
Das wäre natürlich ein etwas höheres Gewicht.
Also wäre nicht die optimale Lösung, also kein minimaler Spannbaum,
sondern minimaler Spannbaum.
Also würde zwar alle Knoten erreichen, aber eben nicht mit minimalen
Kosten.
Und diese Fragestellung spielt eine Rolle, wenn Sie Netzwerke aufbauen
wollen, die alle innerhalb von einem Graf vorhandene Knoten erreicht.
Also zum Beispiel, wenn Sie ein Stromnetz aufbauen wollen oder wenn
Sie im Internet Routing betreiben und also IP-Pakete hin- und
herschicken wollen und Sie auch sicherstellen wollen, dass eben alle
Knoten von allen anderen aus erreichbar sind und das Ganze eben mit
minimalen Kosten oder es könnte jetzt auch wieder Übertragungszeit im
Internet sein, eben erreichen können, dann spielen da solche minimalen
Spannbaumfragen eine Rolle.
Okay, und die Algorithmen zu minimalen Spannbäumen, die werden wir uns
nächstes Mal anschauen.
Also vielleicht nochmal ganz kurz hier die Definition.
Also wir suchen einen Baum, also einen Subgraf unseres Grafs, eine
Teilmenge der Kanten, die es erlauben, mit minimalem Gewicht alle
Knoten zu erreichen und zu verbinden.
Also erstmal kann man sich fragen, warum soll das ein Baum sein?
Also man steht eben dabei fest, wenn man so eine minimale Verbindung
zwischen allen Knoten versucht herzustellen, ist es immer ein Baum.
Sobald ich da irgendwie weitere Kanten einfügen würde und ich einen
Zyklus drin hätte, dann ist eine Kante redundant und kann wieder
entschärmt werden.
Also diese minimalen aufspannenden Grafen sind immer Bäume
automatisch.
Und das heißt, es geht jetzt eben darum, so einen Baum zu finden und
das Gewicht dabei zu minimieren.
Was natürlich auch noch passieren kann, ist, dass ein Graf nicht
zusammenhängend ist, wie jetzt hier der Fall.
Also da sehen Sie, das sind drei nicht zusammenhängende Komponenten.
Und da gibt es dann analog dazu einen Begriff der minimal
aufspannenden Wälder.
Das heißt, sie suchen dann eine Menge von Bäumen, wobei der Baum für
jeden Teilgraf eben immer ein minimal aufspannender Baum sein soll.
Und wenn sie eben das dann zusammensetzen für mehrere solche
Zusammenhangskomponenten, dann spricht man dann von einem minimal
aufspannenden Wald.
Also das heißt, diese minimal aufspannenden Baum-Algorithmen, diese
MST -Algorithmen, Minimal Spanning Tree, die lassen sich eigentlich
alle immer ganz direkt auf minimal aufspannende Wälder erweitern.
Und deshalb werden wir uns auch dann in der nächsten Vorlesung nur
Algorithmen für das MST-Problem anschauen, also nur für einen
zusammenhängenden Graf.
Wenn es nicht zusammenhängt, muss man es einfach den Algorithmen
mehrfach auf die Teilgrafen anwenden.
Gut, und wie die Algorithmen dann aussehen, das sehen wir dann
übermorgen am Mittwoch in der Vorlesung.
Dankeschön.