So, hallo.
Willkommen zur Algorithmen-Vorlesung.
Ganz kurze Erinnerung heute, was wir letztes Mal gemacht haben.
Wir haben uns den Dijkstra-Algorithmus angeguckt, zum Finden kürzester
Wege in einem Graphen.
Und eine Sache im Hinblick auf heute, die da wichtig ist, dass der
Dijkstra -Algorithmus zum einen diese schöne Anschauung hat.
Also wir heben quasi einen Graphen, den wir geknüpft haben, mit Fäden
hoch, und zum anderen, dass er eine Einschränkung hatte, und zwar auf
nicht negative Kantengewichte.
Wir hatten uns eine Implementierung konkret davon angeguckt, von dem
Dijkstra -Algorithmus, und dann die Laufzeit abgeschätzt.
So, die Laufzeit hing dann vor allem ab von den verwendeten
Prioritätslisten oder von der verwendeten Implementierung der
Prioritätsliste.
Also Dijkstra braucht eine Prioritätsliste zum Verwalten der Knoten,
die als nächstes gescannt werden.
Und da kommt es darauf an, welche Prioritätslisten-Implementierung man
da verwendet.
Okay, was machen wir heute?
Heute gucken wir uns einen allgemeineren Fall an.
Also zunächst den Fall, also vielmehr, ja, wir gucken uns direkt den
Fall an, dass die Kantengewichte auch negativ sein können.
Und dafür gibt es einen etwas brutaleren Algorithmus, Bellman-Ford.
Und wir werden sehen, dass das in gewisser Weise so eine Art Brute
-Force -Suche ist.
Und dass man das überraschenderweise aber gar nicht besser hinkriegt.
Zumindest im Augenblick nicht.
Und wir gucken uns noch ein paar Variationen von dem kürzeste Wege
-Problem an.
Dann werde ich einen kurzen Ausblick geben, was tatsächlich in der
Routenplanung quasi an der Front passiert.
Insbesondere gibt es da ein aktuelles Ergebnis, das ich vorstellen
möchte, zu Routenplanung in Straßennetzwerken.
Also da wird es viele Bilder und viele Beispiele geben und gar nicht
so viele Beweise.
Also gar keinen.
Und danach gucken wir uns die Motivation von minimalen Spannbäumen an,
dem nächsten Thema.
Okay, dann steigen wir auch direkt ein.
Also wie gesagt, Dijkstra, letztes Mal hatten wir gesagt, braucht,
damit die ganze Anschauung funktioniert und damit die Beweise
funktionieren, dass es keine negativen Kanten gibt.
Das Problem ist, wir wollen immer noch kürzeste Pfade finden, aber
jetzt lassen wir diese Einschränkungen mal fallen.
Also Kanten mit negativen Kantengewicht können da sein.
Und da gibt es ein paar grundsätzliche Probleme.
Die grundsätzlichen Probleme sind, wenn ich von S nach V will, dann
könnte auf dem Weg dazwischen in dem Graphen ein negativer Zyklus
sein.
Also ein Kreis, dessen summierte Kantengewichte kleiner 0 sind.
Das bedeutet, das hatten wir ja letztes Mal schon gesehen, es gibt im
Prinzip die Möglichkeit, beliebig oft durch so einen negativen Kreis
zu gehen, also einmal, zweimal, beliebig oft.
Und dadurch kann man die Distanz, also die Wegstrecke, die man von S
nach V zurücklegt, beliebig klein kriegen.
Und das können wir so notieren, dass wir schreiben d von V, also die
Distanz von V vom Startknoten S, dass die minusunendlich ist, also
beliebig klein.
Und unsere Aufgabe wird sein, oder unser Problem wird sein, dass wir
das selbst in solchen Graphen rausfinden, dass d von V gleich
minusunendlich ist.
Also um zu beschreiben, was wir uns quasi ideal wünschen würden, auch
in einem Graphen mit negativen Kantengewichten, ist, dass wir eine
Ansage kriegen von dem Startpunkt hier unten, ausgesehen, was die
jeweiligen Distanzen sind, und das kann dann minusunendlich sein.
Das bedeutet, es gibt keinen kürzesten Weg von S zu d zum Beispiel,
sondern es gibt halt immer nur eine Reihe von Wegen oder eine Folge
von Wegen, die immer kürzere Distanzen haben.
Und hier, wie wäre das?
Wir könnten zum Beispiel nach d gehen.
Da wäre die Distanz 0.
Wir könnten aber auch zu d gehen und dann erst noch mal zu b und dann
zu j und dann zu d und dann wäre die Distanz auf einmal minus 1.
Und das können wir beliebig oft machen.
Also wir kriegen da beliebig kurze Pfade hin.
Dasselbe könnte, also genauso könnte man argumentieren, um nach a zu
kommen, kann ich beliebig oft diesen Kreis erstmal, diesen negativen
Kreis durchlaufen.
Und selbst wenn die Kosten nach a dann 42 sind, also hoch, kann ich
vorher halt beliebig negative oder beliebig kleine Kosten für den
Vorweg sozusagen hinkriegen.
Das heißt, auch für a wäre die Distanz, an der ich eigentlich
interessiert wäre, minus unendlich.
Das mir sagt, es gibt keinen kürzesten Pfad.
Es gibt keinen kürzesten Pfad, sondern es gibt immer nur eine Folge
von immer kürzeren Pfaden.
Okay, und umgekehrt, es gibt auch Dinge, die sind nicht erreichbar in
dem Graphen.
Also zu k hin, zu diesem Knoten k, hier links kommen sie gar nicht.
Das heißt, da hätte man gern die Aussage von dem Algorithmus, der
Knoten ist nicht erreichbar, also da ist die Distanz plus unendlich.
Also das sind so die Bedeutungen von minus unendlich und plus
unendlich.
Und dann gibt es natürlich noch Knoten, da kommt man vielleicht hin
und da gibt es auch einen kürzesten Weg mit einer gewissen Distanz.
Das wäre dann zum Beispiel i oder f.
Und dann würden wir gerne die Distanz haben und außerdem den Pfad.
In dem Sinne, wie wir das schon mal beschrieben haben.
Wir würden gerne wissen, wo muss ich von s aus hingehen, um auf
kürzestem Wege zu i zu kommen oder zu g zu kommen oder zu f zu kommen.
Und das können wir dann auch in so einer Parent-Datenstruktur
speichern, wo wir uns einfach immer nur den Knoten merken müssen, der
Vorgänger ist auf dem kürzesten Weg zu f.
Also Parent von f wäre dann zum Beispiel g. Das sind diese
fettgedruckten Kanten.
Und die Knoten, die nicht fettgedruckt sind, die sind dann nicht Teil
von kürzestem Pfad.
Also das ist das, was wir uns eigentlich wünschen würden.
Dijkstra gibt uns das nicht, weil Dijkstra immer nur auf nicht
-negativen Kantengewichten funktioniert.
Oder auf Graphen mit nicht-negativen Kantengewichten.
Okay, also man könnte auch, also man kann auch Szenarien finden, wo es
dann tatsächlich günstig ist, negativ, also wo es tatsächlich günstig
ist, von einer bestimmten Kante zu nehmen, wo die Kosten dann
tatsächlich negativ sind.
Also denken Sie daran, Sie fahren mit einem Elektroauto bergab, dann
wird tatsächlich die Batterie aufgeladen und dann könnte es sein, dass
es günstiger ist, einen bestimmten Weg zu gehen.
Und dass Sie dadurch was wiederkriegen.
Okay, also was wollen wir da tun?
Wir wollen das rausfinden und zwar so, dass wir möglichst nicht in so
eine Endlosschleife gehen.
Jetzt könnte man natürlich hier gucken, man findet einen kurzen Weg
nach A und dann findet man vielleicht noch einen kürzeren und noch
einen kürzeren.
Und der Algorithmus, den man sich da vorstellt, der muss natürlich
irgendwann merken, es gibt halt immer kürzere Wege.
Und da gibt es tatsächlich halt einen Kreis, der dazu führt, dass es
beliebig kurze Wege zu A gibt.
Also da muss man natürlich irgendwann eine Abbruchbedingung sozusagen
haben in dem Algorithmus.
Das ist unser Wunsch.
Okay, um da hinzukommen und einen Algorithmus vorzustellen, mit dem
das funktioniert, müssen wir zunächst nochmal zwei, drei Basiskonzepte
wiederholen.
Also einfach nur ein paar Beobachtungen, das sind einfache
Beobachtungen über kürzeste Wege in Graphen und zwar jetzt auch solche
kürzesten Wege, die halt über negative Kanten führen können.
Und eine Beobachtung, die wichtig ist, ist, dass wenn überhaupt ein
kürzester Pfad existiert, und das ist insofern eine nicht-triviale
Bedingung, weil wir sagen, vielleicht gibt es keinen kürzesten Pfad.
In dem Beispiel von S zu A zum Beispiel gibt es da einfach keinen
kürzesten Pfad.
Damit ist wirklich gemeint, es gibt einen Pfad, sodass keine andere
Pfad kürzer ist als dieser Pfad.
Also wenn ein kürzester Pfad von S nach V existiert, dann ist der ohne
Beschränkung der Allgemeinheit einfach.
Was heißt einfach?
Einfach heißt, der enthält keine Kreise.
Also mit anderen Worten, der besucht jeden Knoten nur einmal.
Also höchstens einmal.
Okay, wie kann man zeigen, dass das gilt?
Ist eigentlich nicht weiter kompliziert.
Wir können uns mal vorstellen, es gibt einen Pfad, einen kürzesten
Pfad von S nach V, und der ist über einen Kreis erreichbar.
Dann können wir die Fallunterscheidung machen, wenn das ein negativer
Kreis ist, das heißt, wenn dieser Kreis zusammengenommen ein negatives
Kantengewicht hat, dann kann ich den nicht nur einmal gehen, sondern
dann kann ich den ganz oft gehen.
Und das widerspricht dann tatsächlich der Annahme, dass das ein
kürzester Pfad von S nach V war.
Denn dann kann ich noch kürzere Pfade bauen, indem ich den Kreis
einfach öfter dran hänge.
Okay, also wenn der Pfad aber nicht einen negativen Kreis enthält,
sondern wenn der einen anderen Kreis enthält, dann kann man sagen, wir
können den kreisfrei machen, dadurch, dass wir diesen Kreis einfach
weglassen.
Das heißt, wir gehen einmal im Kreis und das können wir auch einfach
weglassen.
Und da wir gesagt haben, der Kreis kann nicht negativ sein, wird
dadurch der Pfad von S nach V nicht länger.
Also er wird höchstens kürzer.
Und also wenn wir schon angenommen haben, dass es ein kürzester Pfad
von S nach V ist, dann muss das Gewicht also dieses Kreises schon null
sein.
Okay, gibt es zu der Aussage oder zu der Beobachtung, zu den
Beweisfragen?
Gut, dann haben wir noch eine andere Beobachtung.
Und zwar die Teilpfade von einem kürzesten Pfad.
Die sind selbst wieder kürzeste Pfade.
Also wenn ich einen Pfad von A nach D habe und ich weiß, das ist der
kürzeste Pfad von A nach D, dann müssen auch schon alle Teilpfade,
also A nach B, B nach C, B nach D, C nach D, alle die müssen alle
schon kürzeste Wege sein.
Also warum, kann man als Übung zeigen, aber die Idee ist auch dann
wieder so ein Widerspruchsargument zu führen.
Also was, wenn das nicht so wäre?
Und tatsächlich, ein bisschen komplexer kann man einsehen, die
kürzesten Wege, die kürzesten Pfade, die bilden jeweils einen Baum.
Also ähnlich so, wie wir das schon bei Dijkstra gesehen haben.
Die bilden jeweils einen Baum, wenn ich jeweils einen Pfad nehme, von
dem Startknoten zu jedem Zielknoten.
Also wenn ich für jeden Zielknoten einen kürzesten Weg vom Startknoten
zu diesem Zielknoten nehme und die alle zusammensetze, dann bilden die
insgesamt einen Baum, sofern es keine negativen Kreise gibt.
Also klar, wenn es negative Kreise gibt, dann gibt es auch halt
Kreise, natürlich, und dann ist es kein Baum mehr.
Aber ansonsten kann man diese ganzen kürzesten Pfade zusammensetzen zu
einem Baum.
Also wie gesagt, wie bei Dijkstra.
Die Aussage gilt aber jetzt auch für negative Kantengewichte.
Okay, hier ist ein Beispiel und da sieht man auch, das Ganze ist dann
wieder ein Baum mit S als Wurzel und die fettgedruckten
Kantenübergänge oder die fettgedruckten Kanten sind Teile des Baumes.
Also das Fette ist der Baum und der Rest sind andere Teile vom
Graphen.
Okay, wie gesagt, genauer Beweis wäre dann Übung, aber wie gesagt, der
erste Teil kann man sich auch einfach überlegen, das ist ein
Widerspruch, Widerspruchsbeweis.
Okay, und jetzt, das ist vielleicht für einen Augenblick die
interessanteste Aussage, die werden wir auch gleich noch brauchen,
auch einfach nur eine Beobachtung, aber die ist schon der Schlüssel zu
dem nächsten Algorithmus, also zu Bellman-Ford.
Und deshalb beweisen wir das auch.
Also die Aussage ist, wenn ich als Ausgangspunkt eine Folge von
Relaxationsoperationen habe, also zur Erinnerung, eine
Relaxationsoperation, die betrachtet eine Kante, also hier die erste
zum Beispiel, oder die, die als erstes hier steht, das wäre die, die
die Kante E1 betrachtet, und wir sagen, dass die Kante relaxiert wird.
Und was bedeutet das?
Wir nehmen an, wir haben schon so ein Feld, so ein Array von momentan
bekannten kürzesten Distanzen, oder von momentan kürzesten, also D
gibt die Distanzen jeweils an vom Startknoten aus, zu Vk in dem Fall.
Also das sind die kürzesten bekannten Distanzen, und µ sind die
tatsächlich kürzesten Distanzen.
Also das ist die Notation von den letzten Vorlesungen.
In der Situation sagen wir, dass wir eine Kante relaxieren, wenn wir
folgendes machen, wir gucken uns die Kante an, gucken uns dieses
Distanzfeld an, von vorläufigen Distanzen D, und gucken, ob diese
Kante zu einem neuen, kürzeren Weg von Startknoten zu dem Ziel dieser
Kante E1 führt, oder in dem Fall E1.
Das heißt, wir gucken uns an, ob diese Kante, die wir jetzt angucken,
ob die uns eine Abkürzung bietet, ob die einen neuen, kürzesten Pfad
bietet.
Also wir haben die Gleichung dann auch nochmal auf den nächsten
Folien.
Die Gleichung ist dann einfach, guckt ihr die Distanz von, also wenn
die Kante von U nach V geht, gucken wir mal, guckt ihr die Distanz
nach U an, guckt ihr die Kosten der Kante, also das Gewicht der Kante
UV an, und guckt ihr an, wie lange die Distanz nach V ist.
Und wenn über U zu gehen einen kürzeren Weg bietet, dann aktualisiere
ich einfach die Zielknotendistanz, also D von V.
Okay, also das ist Relaxation, zur Erinnerung.
Und jetzt nehmen Sie an, Sie haben so eine Folge von
Relaxationsoperationen, mit denen Sie dann so ein Abstandsfeld
aktualisieren.
Und wir nehmen auch an, dass in dieser Folge von
Relaxationsoperationen die Kanten auf dem kürzesten Pfad von S nach V,
also von S nach VK in dem Fall, alle abgegangen werden.
Das heißt, es gibt einen kürzesten Pfad von S nach VK über V1, V2 und
so weiter, und die jeweiligen Kanten sind von S nach V1, das ist Kante
E1, von V1 nach V2, das ist Kante E2 und so weiter.
Das heißt, wir relaxieren vielleicht irgendwelche Kanten, aber
insbesondere zwischendrin relaxieren wir die Kanten auf dem kürzesten
Weg von S nach V oder von S nach VK.
Okay?
Also das Wichtige ist hier, wir relaxieren die Kanten in der richtigen
Reihenfolge.
Also zuerst die Kante von S aus, dann die von dem Knoten, zu dem wir
von S aus kommen und so weiter.
Und das sind mal die Voraussetzungen.
Dann gilt anschließend, dass die Distanz in dem Distanzfeld, das ich
mir so zwischendrin gemerkt habe, nach VK, also da, wo ich eigentlich
hin will, dass die schon die optimale Distanz ist, die kürzeste
Distanz.
Also wenn ich nur in der richtigen Reihenfolge alle Kanten von Start
zu Ziel relaxiere, der Reihe nach, und zwischendrin irgendwelche
andere Sachen mache, das ist völlig egal.
Ich kann auch noch andere Sachen relaxieren.
Wenn ich das auf jeden Fall, wenn alles in der richtigen Reihenfolge
als Unterfolge mal vorkommt, dann kriege ich auch am Ende die kürzeste
Distanz raus.
Das ist dann V von VK.
Okay, das ist insofern eine gute Nachricht.
Es sagt mir, ich kann irgendeinen Quatsch drumrum machen, Hauptsache
ich relaxiere hinreichend, viele Kanten hinreichend häufig, sodass die
richtige Unterfolge, die ich am Anfang noch nicht kenne, von
Kantenübergängen, also von dem kürzesten Weg der Reihe nach vorkommt.
Und dann kriege ich halt raus, dass die Distanz zum Zielknoten hin die
richtige ist.
Und wenn ich dann mir merke, wie ich zu dieser Distanz komme, über so
ein Parent Feld, dann habe ich auch gleich den kürzesten Weg nach VK.
Okay, wie zeigt man das?
Formal müsste es eigentlich eine Induktion über K sein, also über die
Anzahl der Knoten.
Wir machen das hier ein kleines bisschen einfacher.
Wir gucken uns einfach die Aussagen an oder die Teilpfade zu den
Zustand des Arrays, zu den Zeitpunkten, wo die erste, zweite, dritte
und so weiter dieser Kanten relaxiert wird.
Was wir sagen können ist, die Distanz zu dem Startknoten, die ist am
Anfang, wenn wir uns überlegen, was wir bei irgendeinem Dijkstra
-artigen Algorithmus machen, am Anfang immer schon gleich auf 0
gesetzt.
Das können wir initialisieren, die Distanz ist 0.
Also zu S komme ich ohne irgendwas zu tun, mit Kosten 0.
So, und die Distanz zu dem nächsten Knoten, die wird schon zu dem
ersten Zeitpunkt, also nach dem ersten Zeitpunkt, genauer gesagt, nach
dieser Relaxation von E1 wird die auch optimal sein.
Warum ist das so?
In dem Moment, wo ich die Kante relaxiere, also wo ich die Kante E1
relaxiere, da werde ich schon den Pfad von S nach V1 betrachten.
Und ich werde die richtige Kante angucken.
Also ich stelle mir insbesondere die Frage, bringt mir diese Kante E1
eine Abkürzung von S nach V1?
Egal, was vorher der Wert von E von V1 war, danach ist es der kürzeste
Wert.
Also danach gibt es den kürzesten Weg an.
Also es kann, diese Distanz kann vielleicht schon vorher auf dem
richtigen Wert stehen, aber sie kann vorher nicht niedriger sein, weil
sie ein kürzester Weg ist, der Weg von S nach V1, und es kann auch
nicht höher sein, weil wir gerade relaxiert haben und einen kürzeren
Weg in Betracht ziehen.
Okay, und jetzt kann man analog argumentieren, in der Situation zu
einem späteren Zeitpunkt, wenn ich die zweite Kante relaxiere, E2,
dann wird V1 schon den richtigen Wert haben, also die kürzeste
Distanz.
Und dann gucke ich mir in dem Moment, dann relaxiere ich die Kante E2,
dann gucke ich mir also die nächste Kante an von V1 nach V2.
Okay, und dabei analoges Argument, werde ich wieder den kürzesten Weg
zumindest in Betracht ziehen, oder die kürzeste Distanz.
Vielleicht stand die schon vorher drin, vielleicht stand noch was ganz
anderes drin, was niedrigeres kann nicht drinstehen, dann hätten wir
einen neuen kürzesten Pfad, dann wäre der, den wir hier betrachten,
nicht der kürzeste Pfad.
Und einen höheren haben wir nachher auch nicht drin, weil wir ja
gerade den richtigen Weg in Betracht ziehen über V1.
Okay, und so geht das halt weiter.
Und am Ende haben wir die Aussage, nachdem die Kantenrelaxationen halt
in dieser Reihenfolge passiert sind, habe ich einen kürzesten Weg nach
Vk.
Es ist halt nicht wichtig, das ist das Entscheidende, es ist nicht
wichtig, was wir vorher machen, was wir mittendrin machen und was wir
nachher machen.
Wichtig ist nur, dass diese Kantenrelaxationen in der Reihenfolge als
Teil Operationen passieren.
Okay, Fragen soweit?
So, das ist jetzt, also diese Beobachtung ist jetzt eigentlich schon
der Schlüssel für den nächsten Algorithmus, nämlich Bellman-Ford.
So, und was tut der?
Also in gewisser Weise tut der vielleicht das, was man so tun würde,
um einfach das Problem auf jeden Fall zu lösen.
Was er tut ist, es werden alle Kanten relaxiert und das Ganze passiert
n -1 mal.
Und zwar alle Kanten von dem Graphen.
Das heißt also, wir haben insgesamt n oder n-1 mal m Operationen.
Also m ist die Anzahl der Kanten.
Jede Kantenrelaxation kostet halt, naja, o von 1 Operationen und das
Ganze machen wir o von n mal.
So, und was passiert dann?
Die Idee von dem Algorithmus ist, naja, in der ersten Runde, wenn also
zum ersten Mal alle Kanten relaxiert werden, also ich sollte
vielleicht noch sagen, zuerst werden alle Kanten relaxiert, der Reihe
nach, in irgendeiner Reihenfolge, ist egal, dann wird neu angefangen,
dann werden wieder alle Kanten relaxiert.
Also insbesondere, es wird nicht erst irgendwie n mal oder n-1 mal die
erste Kante relaxiert, dann n-1 mal die zweite, das wäre nicht so
hilfreich, sondern die Kanten werden schon der Reihe nach relaxiert,
aber in verschiedenen Runden.
Also die zweite Relaxation von irgendeiner Kante passiert auf jeden
Fall nach der ersten Relaxation von jeder anderen Kante.
Okay, und was ist die Idee?
Die Idee ist, wenn ich einen kürzesten Pfad von s zu einem bestimmten
Knoten habe, zu v, wenn so ein Pfad überhaupt existiert, ein kürzester
Pfad, dann hat er höchstens die Länge n-1 Kanten.
Warum?
Wir haben ja gerade gesagt, wenn ein kürzester Pfad existiert, dann
enthält er keine Kreise.
Wenn er keine Kreise enthält, dann kann er jeden Knoten höchstens
einmal besuchen.
Und dann muss man da auch schon mit n-1 Kanten klarkommen, denn es
gibt halt nur n Knoten und mit mehr als n-1 Kanten würde ich
irgendwann zwangsläufig mal einen Knoten wiedersehen, also zum zweiten
Mal besuchen.
Okay, also daher kommt dieser n-1 mal.
Wenn es einen Pfad gibt, wenn es einen kürzesten Pfad von s nach v
gibt, dann wird er in jedem Fall mit höchstens n-1 Kanten erreichbar
sein.
Okay, dann hypothetisch können wir uns so einen Pfad überlegen.
Der sei mal dann von s gleich v1 nach v2, nach v3 und so weiter bis vk
gleich v.
Also das sind die Zwischenstationen in einem angenommenen, den wir am
Anfang noch nicht kennen, in einem angenommenen kürzesten Pfad
zwischen s und v.
Und die Idee ist, in der ersten Runde, wo alle Kanten relaxiert
werden, dieses Grafen, da wird die Distanz von s nach v2, also von v1
nach v2, da wird insbesondere die in Anführungszeichen richtige Kante,
also die von v1 nach v2, die wird relaxiert werden.
Das heißt, nach der ersten Runde hat die Distanz von v2 schon mal den
richtigen Wert.
Also da nutzen wir jetzt aus, wenn zwischen s und v ein kürzester
Pfad, also wenn das hier ein kürzester Pfad ist, sind doch alle
Teilpfade die kürzesten Pfade.
Das heißt, insbesondere hat dann v2 schon den richtigen Wert.
Das ist dann der kürzeste Pfad von v1 nach v2.
So, in der zweiten Runde wissen wir, am Anfang der zweiten Runde hat
v2 den richtigen Wert und danach gucken wir uns in der zweiten Runde
die richtige Kante von v2 nach v3 an.
Das heißt, wir relaxieren die zweite Kante spätestens in der zweiten
Runde sozusagen auf den richtigen, da wird v3 auf den richtigen Wert
gesetzt.
In der ersten Runde ziehe ich vielleicht viel in Betracht, aber
insbesondere die Kante von v1 nach v2.
In der zweiten Runde ziehe ich wieder viel in Betracht, aber
insbesondere danach die Kante von v2 nach v3.
Und damit ist die Distanz am Ende der zweiten Runde nach v3 schon die
richtige.
Vorher war die Distanz nach v2 die richtige, jetzt nach v3.
Und so geht das weiter.
Und am Ende steht die Aussage, nach der k-ersten Runde ist die Distanz
zu vk die richtige.
Und wenn ich mir dann halt merke, wo ich jeweils hergekommen bin, wie
die Distanz erreicht wird, dann habe ich auch den kürzesten Pfad von s
nach vk.
Okay.
In gewisser Weise, man könnte denken, dass wir ziemlich viel unnötig
tun.
Also wir relaxieren hier in der ersten Runde natürlich sehr viel, aber
das entscheidende Argument in der Betrachtung oder im Beweis ist ja,
wir relaxieren eine Kante, die uns interessiert, von diesen ganzen m
-Kanten.
Und in der zweiten Runde passiert auch ganz viel, aber uns
interessiert eigentlich nur eine Kantenrelaxation.
Also man tut ja ziemlich viel.
Insofern kann man sagen, in gewisser Weise ist das so eine Art brute
force Algorithmus.
Also mit hoher Gewalt, deshalb auch Algorithmen brutal.
Gibt es zu dem Algorithmus selbst noch Fragen, warum der funktioniert?
Gut.
Dann können wir uns angucken, zum einen die Laufzeit und zum anderen,
wie man damit negative Kreise findet.
Unser Ziel war ja, dass wir zum einen kürzeste Pfade finden, also die
Distanzen von Knoten, die irgendwo zwischen Minus und Plus und Endlich
liegen, also ohne Minus und Endlich und ohne Plus und Endlich.
Wir wollten nicht erreichbare Knoten finden und wir wollten solche
Knoten finden, die halt in einem Kreis liegen oder die halt keinen
kürzesten Pfad haben von S zu diesem Knoten.
Wie kann ich mit Bellman-Ford Kreise finden, negative Kreise?
Naja, wir haben uns überlegt, was Bellman-Ford bei einem negativen
Kreis macht.
Er wird halt diese Kanten immer weiter relaxieren und entlang eines
Pfades, der auf einmal negative Kreise enthält, wird er immer weiter
die Distanzen relaxieren, also immer weiter die Distanzen verkürzen.
Das heißt, es gibt, es breitet sich dann wie in Wellen sozusagen aus,
diese Updates, diese Aktualisierung der kürzesten Distanzen.
Und was passiert ist halt, dass die Distanzen von Knoten in einem
negativen Kreis, die werden immer kleiner.
Weil es halt auf einmal jetzt immer mehr Möglichkeiten gibt, das noch
weiter zu verbessern und zu verkürzen.
Und das heißt, was man tun kann ist, man kann sagen, ich weiß, dass
nach N-1 Durchläufen von Bellman-Ford, dass da, wenn es keine
negativen Kreise gäbe, alle Knoten schon ihre endgültige Distanz
haben.
Und die einzige Möglichkeit, wie sich da jetzt noch was verändern
kann, ist, dass Knoten in einem negativen Kreis liegen und jetzt
sozusagen immer weiter aktualisiert werden.
Das heißt, man guckt sich jetzt einfach noch an, nach N-1 Ausführung
von Bellman-Ford, also nach N-1 von diesen Relaxationsrunden, was
verändert sich noch?
Und was verändert sich noch?
Da kann man sich einfach angucken, wo würde denn eine Relaxation noch
was bringen?
Also man guckt sich diese Gleichung hier an, das ist diese
Relaxationsgleichung, von der ich eben gesprochen habe.
Man guckt sich an, ob die Kante E, also C von E, das sind die Kosten
von E, ob die Kante E einem irgendwas bringen würde.
Und man guckt sich an, wo sich da was verändert und alle Kanten, die
in so einem negativen Kreis liegen, die würden noch was bringen, da
würde sich noch was tun und man kann dann die entsprechenden Knoten
anpassen.
Auf Minus und Endlich.
Das heißt, man macht so weit, wie es eigentlich reichen müsste und
sagt dann, wenn sich jetzt noch was ändert, dann muss da, wo sich was
ändert, dann würde das kein Ende finden.
Okay?
Okay, Beispiel.
Also nicht erschrecken lassen, der Graph ist gar nicht so groß, das
ist, links oben fängt es an, also insgesamt sechs Bilder.
Die erste Beobachtung ist, in jedem Bild ändert sich mal nicht so viel
und das kann man auch, also was sich tatsächlich ändert, das sind
immer diese roten oder rötlichen Pfeile.
Das sind also Kanten, die so rötlich gefärbt sind, da ändert sich was.
Und ändert sich was bedeutet, das sind Kanten, die gerade relaxiert
werden und die dann irgendeine Auswirkung haben.
Also wenn Sie ganz links oben gucken, da waren diese beiden Kanten,
diese vom Startknoten ausgehend, von diesem eckigen Startknoten, die
waren relaxiert und natürlich jetzt auf einmal die Zielknoten, die
waren standen vorher oft nicht erreichbar, oft bloß unendlich, die
kriegen dann jetzt auf einmal einen echten Wert.
Und was Sie hier sehen ist, beim Startknoten ändert sich jetzt nichts
mehr und die einzigen Änderungen sind jetzt von den Knoten, die gerade
eben verändert wurden, wieder die ausgehenden Kanten.
Das heißt, wenn man Bellman-Ford implementiert, wäre so eine
naheliegende Optimierung, dass man sagt, du brauchst eigentlich nur
die Kanten zu berücksichtigen oder zu relaxieren in der nächsten
Runde, die von Knoten ausgehen, die gerade eben aktualisiert wurden,
die also Zielknoten von wieder relaxierten Kanten wurden, wo sich was
geändert hat.
Das heißt also, in dem zweiten Bild, links in der Mitte, da braucht
man jetzt nur noch die Kanten anzugucken, die von den Knoten ausgehen,
die gerade aktualisiert wurden.
Das sind die Knoten über dem Startknoten und rechts von dem
Startknoten.
Damit erreicht man dann natürlich jetzt wieder neue Knoten, die werden
aktualisiert mit den jeweiligen akkumulierten Kosten und so hangelt
man sich dann durch den Graphen.
Also Sie sehen dann rechts zum Beispiel, das waren die Teile, wo alle
Knoten tatsächlich einen Wert zwischen Plus und Minus und Endlich
haben, also das was rechts steht, rechts vom Startknoten, das werden
dann nachher irgendwelche Werte sein.
Und hier gibt es auch rechts vom Startknoten, hier gibt es einen
Kreis, also den Sie vom Startknoten nach rechts, dann noch schräg
oben, nach links und dann wieder nach unten erreichen.
Der ist aber nicht negativ, da gibt es keine negativen Kantengewichte.
Also deshalb ist der nicht problematisch und führt nicht dazu, dass
irgendwas minus-unendlich wird auf einmal.
Und das rechnet Bellman-Ford dann so aus und im linken Teil von dem
Graphen passieren jetzt interessante Dinge, denn da passieren immer
weitere Relaxationen und immer weitere...
es geht von links oben nach unten, dann nach rechts und dann wieder
nach oben.
Also da passieren dann immer weitere Relaxationen und irgendwann, also
hier ganz oben, wenn wir eigentlich fertig sein müssten, können wir
sagen, okay, wenn sich jetzt immer noch was ändert, da wo sich was
ändert, schreibt eine Minus-unendlich hin.
Und dann sind wir mit dem Algorithmus fertig und haben alles
zugeteilt, also eigentlich genauso wie gewünscht.
Wir haben markiert, welche Knoten nicht erreichbar sind, das wäre K.
Wir haben markiert, welche Knoten im negativen Kreis liegen oder über
einen negativen Kreis erreichbar sind.
Und wir haben die Knoten markiert mit der Distanz, die erreichbar sind
und keine minus-unendlich, also nicht in einem negativen Kreis liegen.
Okay, gibt es zu dem Beispiel noch Fragen?
Nee, gut.
Okay, jetzt zur Laufzeit endlich.
Also offensichtlich, wie lange dauert das?
Naja, ich habe N wie Norbert Durchläufe und M wie Martha viele
Operationen pro Durchlauf, weil ich mir alle Kanten angucke und das
Anzahl von Knoten oft, also O von Anzahl von Knoten oft.
Und wenn ich dann, also tatsächlich am Ende muss ich dann noch einmal
durchgehen, um diese negativen Kreise zu finden.
Das heißt, insgesamt sind es auch sowas wie N mal N vieler
Operationen.
Also O von N mal M wäre es in jedem Fall.
Das ist viel langsamer als Dijkstra, wenn Sie sich erinnern.
Da ging die Anzahl der Kanten nur fast, also je nachdem wie man das
mit der Prioritätsliste implementiert, nur fast linear ein.
Und wenn Sie sich vorstellen, dieses M, das ist eigentlich der Wert,
der weh tut.
Da möchte man das möglichst klein haben.
Also besser als linear geht wohl nicht.
Man muss sich ja alle Kanten mal angucken.
Aber N mal M ist schon ziemlich heftig.
Und vielleicht das Interessanteste an dem Algorithmus ist, man würde
denken, da sind ganz viele Optimierungen möglich, aber asymptotisch
bringt das eigentlich alles nichts.
Das heißt, es gibt immer noch Graphen, es gibt also sozusagen Worst
Case, bei dem es keinen besseren Algorithmus gibt, also keinen
asymptotisch besseren Algorithmus als Bellman-Ford.
Es gibt aber sehr wohl Algorithmenvarianten, wo man dann auch ein
bisschen heuristisch optimieren kann.
Also wie gesagt, die allereinfachste Optimierung ist, Sie gucken sich
nur die Kanten an, die jetzt sich auch gerade, also wo sich gerade was
verändert hat bei den Knoten.
Da können Sie natürlich im Best Case oder im Average Case, was immer
das dann konkret bedeutet, je nachdem was für eine Eingabenverteilung
Sie haben, können Sie da deutlich besser werden.
Aber asymptotisch ist es halt immer noch ein offenes Problem, was
besseres zu finden als dieses O von N mal M.
Also insofern ist es auch eigentlich eine spannende Frage, ob es da
was besseres gibt.
Okay, noch weitere, also das war schon alles zu Bellman-Ford.
Der zweite Algorithmus für das Finden von kürzesten Wegen oder
Distanzen, kürzesten Distanzen nach dem Dijkstra-Algorithmus und jetzt
gucken wir uns noch zwei Spezialfälle an von diesen kürzesten Wege
-Problemen und zwar das eine Mal bei a-zyklischen Graphen, also bei
speziellen Graphen, die halt eine spezielle Eingabeform darstellen.
Und was sich herausstellen wird, ist, dass bei a-zyklischen Graphen
das Problem auf einmal ein sehr einfaches wird.
Also das ist jetzt einfach ein Spezialfall von der Eingabe, wir sind
immer noch interessiert an kürzesten Wegen, also wir haben einen
Startknoten S und wir wollen rausfinden, wie man von diesem
Startknoten S zu anderen Knoten kommt und zwar möglichst schnell
natürlich, also mit möglichst geringen Gewichten oder mit möglichst
geringen Kosten.
So und wir gehen davon aus, der Graph ist a-zyklisch.
Das heißt, es gibt überhaupt keine Kreise.
Insbesondere keine negativen Kreise, aber tatsächlich, es gibt
überhaupt keine Kreise.
Also je nach Anwendung, wenn Sie an Routenplanung denken, ist das
vielleicht nicht realistisch, aber es könnte schon Szenarien geben, wo
das vorkommt.
Okay.
Und die interessante Beobachtung, also es ist eigentlich eine
Beobachtung und ab dann ist alles trivial.
Die Beobachtung ist, für jeden kürzesten Pfad gilt, dass die Kanten,
also wir nehmen mal an, wir haben einen kürzesten Pfad von V1 nach Vn,
also vom Startknoten zu irgendeinem Zielknoten und für jeden kürzesten
Pfad gilt, dass wir, wenn wir die Knoten topologisch sortieren, dass
dann alle Kanten von links nach rechts zeigen.
Das heißt, dass in der topologischen Sortierung V1 vor V2 kommt und V2
vor V3 und so weiter.
Was bedeutet das?
Also diese topologische Sortierung, zur Erinnerung, topologische
Sortierung bedeutet, das kann man mit Tiefensuche zum Beispiel machen,
topologische Sortierung bedeutet, dass wir die Knoten so sortieren,
dass alle Kanten immer von links nach rechts zeigen in der Sortierung
oder das von einem kleineren zu einem größeren Knoten.
Okay, und das gilt natürlich insbesondere für den kürzesten Pfad, weil
da gibt es ja Kanten zwischen jeweils zwei Knoten und das heißt auch
diese Knoten hier sind sortiert bezüglich dieser topologischen
Sortierung.
Okay, aber das ist eine gute Nachricht, weil uns das sagt, in welcher
Reihenfolge wir die Knoten angucken müssen, um die Kanten in der
richtigen Reihenfolge zu relaxieren.
Also wir hatten ja eben diese Beobachtung gehabt, wenn man die Kanten
von dem kürzesten Pfad in der richtigen Reihenfolge relaxiert.
Von den Kanten, die von dem ersten zum zweiten Knoten ausgehen, danach
vom zweiten zum dritten und so weiter.
Wenn man das in der richtigen Reihenfolge tut, dann wird man die
Distanzen tatsächlich direkt auf Anhieb anpassen.
Und genau das tun wir.
Wir scannen im Sinne von Dijkstra, also wir gucken uns alle Kanten aus
und relaxieren alle Kanten, die von V1 ausgehen.
Wir scannen alle Knoten, beginnend mit V1, in einer topologischen
Sortierung.
Okay.
Also wir sortieren einmal topologisch mit Tiefensuche und anschließend
scannen wir die Knoten, wie bei Dijkstra, jetzt aber in Reihenfolge
dieser Ordnung.
Also insbesondere haben wir da gar keine Prioritätswarteschlangen oder
so mehr.
Wir haben nur einmal diese Sortier-Operation und dann diese Scan
-Operation.
Okay, und damit finden wir auch den kürzesten Pfad von V1 nach Vn,
einfach weil wir in der richtigen Reihenfolge relaxieren.
Gut, wie lange dauert das O von m plus n?
Das ist ziemlich gut, allein schon weil m nur linear drin vorkommt.
Und das ist auch das, was man selbst bei Dijkstra, da kommt man selbst
bei Dijkstra mit ganzzahligen kleinen Kantengewichten nicht besser
hin.
Gut, das ist das eine, der eine Spezialfall, das eine Beispiel, was
ich nennen wollte und jetzt kann man das Problem noch ein bisschen
verändern und sagen, wir wollen nicht von einem Startknoten zu vielen
Zielknoten, das ist das, was diese Bellman-Ford und Dijkstra
-Algorithmen uns natürlich geben, sondern vielleicht möchte man ja die
kürzesten Wege in einem ganzen Netzwerk finden.
Das könnte man zum Beispiel so als eine Vorberechnung zur
Routenplanung benutzen und da habe ich gleich noch ein konkreteres
Beispiel, wo genau das Problem als Vorberechnung ziemlich nützlich ist
oder die Lösung des Problems als Vorberechnungsschritt ziemlich
nützlich ist.
Also wir stellen unsere Frage anders, wir fragen nicht mehr, wie kommt
man von einem Startpunkt überall sonst wohin, also zu allen anderen
Knoten, sondern wir fragen, wie sind die kürzesten Pfade von jedem
Knoten zu jedem anderen Knoten und die Distanzen.
Da gibt es jetzt so zwei Möglichkeiten, was man so als naheliegende
Implementierung da machen könnte, so die Haut-rauf-Möglichkeiten und
die wären, naja, ich mache entweder n mal Dijkstra oder n mal Bellman
-Ford.
Also für jeden Startknoten berechne ich einfach die komplette Tabelle
oder die komplette, dieses kürzeste Wegefeld und dieses Distanzfeld
mit dem Dijkstra oder mit dem Bellman-Ford-Algorithmus.
Welchen ich nehme, kommt natürlich auch ein bisschen drauf an, da
kommt es drauf an, ob ich negative Kantengewichte habe oder ob ich nur
nicht negative Kantengewichte habe.
Und wenn man das macht, also Dijkstra ist da natürlich schneller
braucht, aber hat aber mehr Anforderungen.
Wenn man das macht, dann kriegt man natürlich einfach n mal die Zeit
für einen Durchlauf von Dijkstra oder von Bellman-Ford.
Da ist also die Laufzeit, da kommt so ein n mal m drin vor, das ist
nicht so hübsch.
Und hier kommt halt die Zeit bei Bellman-Ford von n Quadrat mal m drin
vor.
Das ist halt richtig übel.
Also das ist nicht so schön.
Was in Algorithmen 2 dann behandelt wird, ist einfach ein etwas
clevererer Algorithmus, wo man einmal Bellman-Ford macht und
anschließend n mal Dijkstra.
Und zwar auch bei negativen Kantengewichten.
Also da ist Bellman-Ford im Prinzip so eine Art Detektor von negativen
oder von den Effekten von negativen Kanten und danach kann man halt n
mal Dijkstra machen.
Aber das wird dann in Algorithmen 2 behandelt.
Also es gibt durchaus bessere Ideen als einfach nur n mal oder von
allen Knoten aus die kürzesten Wege alle zu suchen mit den
Algorithmen, die wir schon hatten, wenn man wirklich an allen
interessiert ist.
Ok, das ist auch nur auf einer Folie, so eine Art Ausblick.
Und jetzt kommen wir schon von dem Kapitel zur Zusammenfassung.
Wir sind aber mit dem Kapitel dann insofern noch nicht ganz fertig.
Danach kommt noch ein paar, n Blick über den Tellerrand und n kleiner
Exkurs.
Also aber zunächst mal zu der Zusammenfassung.
Was haben wir gelernt?
Also wir haben einfache Algorithmen gesehen und vor allem in
Spezialfällen sehr effiziente Algorithmen.
Also das eine wird Dijkstra mit nicht negativen Kantengewichten und
das andere wird der Algorithmus mit der topologischen Sortierung, wenn
der Graph a-zyklisch ist.
Und wir haben da gesehen, wie man kürzeste Wege berechnet.
Elmenford ist halt eher sowas, was man nicht unbedingt als effizient
vielleicht einsortieren würde, aber interessant ist halt gerade, dass
man nichts Besseres kennt asymptotisch.
Wie gesagt, asymptotisch halt, das ist natürlich auch, also praktisch
kann man da noch viel verbessern.
Was haben wir gesehen?
Die Korrektheitsbeweise, also insbesondere bei Dijkstra, war nicht
ganz trivial, aber man kriegt gute Lösungen.
Also man muss insbesondere dann bei einer Lösung von O von N plus M,
bei den a-zyklischen Graphen, da geht es halt natürlich auch nicht
besser, man muss ja alles mal angucken.
Und wir haben gesehen, Prioritätslisten können auch in anderen
Algorithmen, in dem Fall in dem Dijkstra Algorithmus, ein wichtiger
Baustein sein.
Bei Prioritätslisten ist es auch so, die kann man weiter verbessern
und kann sich dann insbesondere Prioritätslisten überlegen, die
besonders geeignet sind für die Verwendung im Dijkstra-Algorithmus.
Und da kriegt man das dann, also bei beliebigen Kantengewichten auch
von O von, also da kriegt man es sogar zu O von M plus N mal log log
N, da war vorher halt ein N log N.
Wenn man bessere Prioritätslisten nimmt.
Also je nachdem, was man da für Heaps nimmt, binäre oder Fibonacci
Heaps, haben wir dann halt hier sogar einen Faktor vor M oder bei
diesem N log N haben wir dann noch was anderes.
Was gibt es sonst noch für Varianten?
Wie gesagt, ein kleiner Blick über den Tellerrand.
Was würde man denn in der Realität antreffen?
Denken Sie an Routenplanung.
Da haben Sie vielleicht als Zielfunktion nicht unbedingt kürzester
Weg, sondern da haben Sie vielleicht auch noch Spritverbrauch.
Da haben Sie vielleicht noch sowas wie kürzeste Strecke versus dauert
am kürzesten oder dauert nicht lange und vielleicht gibt es so
verschiedene Abwägungen, wo Sie im Vorhinein noch gar nicht wissen,
was Sie denn eigentlich bevorzugen.
Und da kriegen Sie dann vielleicht die Möglichkeit oder dann, wenn Sie
mehrere Zielfunktionen betrachten, dann kann man halt mehrere
Möglichkeiten anbieten, die ein Nutzer wählen kann und da kann man
sich dann halt auch andere Algorithmen angucken, die halt von
vornherein mehrere Zielfunktionen auf einmal optimieren.
Dann gibt es vielleicht noch das Problem, dass Sie Ziele nicht in
einer bestimmten Reihenfolge anfahren wollen, sondern in beliebiger
Reihenfolge.
Also Beispiel, Sie möchten von der Uni nach Hause fahren, aber vorher
noch einkaufen und an verschiedenen Orten, beim Lebensmittelgeschäft,
beim Bäcker und außerdem wollten Sie vielleicht noch kurz in die
Kneipe gehen.
Also dann sollten Sie vielleicht das nicht als erstes machen und
danach noch einkaufen, das könnte dann spät werden.
Okay, aber vielleicht haben Sie auch Ziele, die Sie in beliebiger
Reihenfolge anfahren möchten und in dem Fall ist es gar nicht mehr so
klar, wie man das mit unseren Algorithmen löst.
Wenn Sie eine feste Reihenfolge der Ziele haben, können Sie einfach
den kürzesten Weg von A zum ersten Zwischenziel berechnen, vom ersten
Zwischenziel zum zweiten und so weiter.
Wenn Sie die in der beliebigen Reihenfolge anfahren, dann ist gar
nicht klar, was hier überhaupt Ihr erstes Zwischenziel ist.
Also Sie geben da quasi so Randbedingungen vor und mit Randbedingungen
beschäftigen wir uns dann im Optimierungskapitel.
Aber generell sind es Probleme, die schwer zu lösen sind.
NP-schwer heißt, wenn man das Problem, also zum Beispiel diese Ziele
in beliebiger Reihenfolge anfahren, wenn man das allgemein lösen
könnte, dann könnte man auch große Zahlen faktorisieren, dann könnte
man auch ganz andere Probleme lösen, von denen man im Augenblick nicht
glaubt, dass sie effizient lösbar sind.
Okay, ja, dann gibt es noch das Problem, disjunkte Wege zu haben, wenn
Sie halt Alternativen wollen, die garantiert stauresistent sind, also
wo Sie keinen Schnitt haben zwischen den angebotenen Alternativen,
auch das ist dann wieder ein schwieriges Problem.
Okay, jetzt noch ein kleiner Exkurs.
Wobei Exkurs bedeutet, dass wir uns ein Ergebnis, was ein paar Jahre
alt ist, also relativ aktuell, dass wir uns das angucken, also ein
wissenschaftliches Ergebnis, das auf einer Konferenz publiziert wurde,
und da vielleicht einen Eindruck gewinnen, was so die aktuellen
Probleme und die aktuellen Lösungen sind.
Okay, also was ist das Thema?
Es geht um Routing in Straßennetzwerken, also natürlich denkt man da
als allererstes an so ein Navigationssystem, aber es kann auch andere
Anwendungen haben.
Was sind da die Randbedingungen?
Die Anzahl der Knoten sind sowas wie, naja, also eine mehrstellige
Millionenzahl.
Also ziemlich viele Knoten.
Und interessant ist, diese Graphen, die man da hat, die sind dünn
besetzt.
Was heißt dünn besetzt?
Das heißt, dass der Ausgangsgrad von jedem Knoten zumindest im Schnitt
nicht sehr groß ist.
Also wie kann man sich das überlegen?
Naja, es gibt halt keine Straßen von Karlsruhe nach, sagen wir mal,
Rom direkt, sondern da müssen sie halt über verschiedene direkte
Nachbarn gehen.
Also mit anderen Worten, jeder einzelne Punkt in diesem, oder jeder
einzelne Knoten, jeder einzelne Punkt in so einer Karte ist halt nur
verbunden mit den Nachbarpunkten und das sind gar nicht so viele.
Also das sind dann konstant viele und dann kommen sie auf m gleich
Theta von m Kanten.
Okay, und außerdem eine Sache, die man ausnutzen kann in so
Betrachtungen, ist, dass die Graphen fast planar sind.
Planar heißt, sie können das zeichnen, ohne zu überkreuzen.
Also ohne, dass sie beim Zeichnen halt Kanten oder Linien sich kreuzen
würden und die Graphen, mit denen was zu tun haben, die sind halt fast
planar.
Also sie haben manchmal sowas wie Brücken oder Unterführungen.
Das kommt aber nicht so häufig vor.
Also meistens kreuzen sich die Kanten nicht.
Und mit der inhärenten Hierarchie, da sage ich gleich noch was zu.
Die Idee ist, wenn sie von Karlsruhe nach Rom fahren wollen, dann
benutzen sie wahrscheinlich nicht ausschließlich Landstraßen.
Es sei denn, sie haben wirklich was übrig für Landstraßen, aber
wahrscheinlich werden sie dann auf die Autobahn fahren.
Und das heißt, es gibt so eine gewisse Hierarchie, wo sie schnelle
Straßen, also sie gucken erstmal, dass sie auf eine schnelle Straße
kommen und von da aus halt in die Nähe von Rom und dann sieht man
weiter.
Okay, ich hatte schon gesagt, offensichtliche Anwendungen sind
natürlich Navigationssysteme, entweder bei ihnen im Auto oder im
Internet, aber auch vielleicht für Logistik, wenn sie dran denken, wie
man vielleicht Güter möglichst effizient verschiebt, kann es eine
günstige Sache sein, Straßennetzwerke zu, also kürzeste Routen in
Straßennetzwerken sich anzugucken.
Okay, ein paar Beobachtungen.
Also fangen wir damit an, wenn wir halt nur von Karlsruhe nach Rom
wollen, dann werden wir uns halt nicht, also wir werden nicht den
kompletten Dijkstra-Algorithmus über den ganzen Graphen laufen lassen,
oder also wenn sie von Karlsruhe nach Pforzheim wollen, zumindest
nicht, einfach weil da würden halt viele Knoten gescannt werden, die
ihnen gar nichts weiter bringen würden.
Man kann sich so überlegen, der Dijkstra-Algorithmus, der hebt im
Prinzip ja dieses Geflecht von Knoten hoch, das bedeutet, also hier
ist es ein bisschen anders dargestellt, in gewisser Weise, der
Dijkstra -Algorithmus guckt sich zunächst vom Startpunkt ausgehend die
Knoten, na wie in so einem Luftballon an, der aufgeblasen wird.
Das heißt, zuerst gucken sie sich an, was liegt in der Nähe und dann
gucken sie sich an, was liegt weiter weg.
Und wenn sie dann irgendwann bei Pforzheim angekommen sind und dieser
Knoten, der dem Ziel dort entspricht, gescannt haben, dann wissen sie,
der hat schon die kürzeste Distanz.
Da brauchen sie jetzt eigentlich gar nicht weitermachen, denn in dem
Moment, wo er die kürzeste Distanz hat, da kennen sie auch einen Pfad,
der ist dann in dem Parent Array gespeichert.
Es wird ja immer ein Zeuge mitgespeichert für diese kürzeste Distanz.
Und dann haben sie auch schon einen kürzten Weg von Karlsruhe nach
Pforzheim gefunden.
Also da brauchen sie natürlich nicht jedes Mal ganz Europa scannen.
Also hier steht spart im Durchschnitt die Hälfte des Scans, das heißt
natürlich im Durchschnitt, wenn sie wirklich einen zufälligen Knoten
suchen.
Noch ein paar andere Tricks.
Wenn sie dieses Luftballon aufblasen Bild von Dijkstra haben, dann ist
es auch ganz nützlich, sich zu überlegen, diesen Luftballon
aufzublasen.
Je weiter sie das tun, desto mehr Knoten sind natürlich am jeweiligen
Rand.
Also desto langsamer geht es, den Luftballon weiter aufzublasen.
Und da kann es manchmal günstiger sein, Knoten zu suchen, die halt
sowohl vom Ziel ausgehend zu suchen, als auch vom Startpunkt ausgehend
zu suchen.
Die Idee ist, sie sind schneller in einem Zustand, oder sie brauchen
weniger Luft, um S und T beide aufzublasen, so dass sie sich
irgendwann treffen.
Und die treffen sich dann halt an einem Punkt, der sozusagen der Punkt
ist, der auf halbem Weg liegt, zwischen, sagen wir mal, Karlsruhe und
Pforzheim.
Das geht dann also schneller, als S aufzublasen, bis T drin enthalten
ist.
Da gibt es noch so ein paar andere Tricks.
Zielgerichtete Suche, dass sie halt von vornherein eher in Richtung
Pforzheim suchen und nicht in die andere Richtung.
Oder dass sie halt direkt suchen, wo kommt und das ist jetzt
eigentlich das Thema dieses Resultats, dass sie halt gucken, wie komme
ich am schnellsten auf die Autobahn und wie komme ich auf der Autobahn
am schnellsten nach Pforzheim.
Ist jetzt vielleicht nicht ein gutes Beispiel, sondern diesmal Rom.
Also das sind diese verschiedenen Farbensäulen signalisieren.
Es gibt dann halt so eine Suche zum nächsten, zunächst höheren
Hierarchie, also zunächst schnelleren Verbindung, zunächst schnelleren
Verbindungsnetzwerk, dem Autobahnnetzwerk und ab da geht es dann halt
schneller.
Das ist dieser hellblaue oder hellrote Bereich.
Okay, und das gucken wir uns jetzt ein kleines bisschen genauer an.
So.
Also eigentlich habe ich das schon gesagt, es gibt da nützliche
Eigenschaften und auf die will ich hinaus, insbesondere auf diese
Autobahneigenschaft und natürlich ist es auch ein wichtiges Thema.
Also ansonsten habe ich eigentlich alles auch schon gesagt hier.
Und jetzt kommt es halt zu dieser konkreten Arbeit oder jetzt kommt es
zu einer Beschreibung von dieser konkreten Arbeit.
Die ist am Lehrstuhl von Sanders entstanden, von Peter Sanders und
auch noch in Zusammenarbeit mit anderen Leuten von anderen
Universitäten entstanden und die Idee ist, dass man versucht, die
Routenfindung halt genau so zu optimieren, dass man halt sich anguckt,
welche...
naja gut, ich sag gleich mehr dazu.
Also welche Knoten sind denn meine Einstiegsknoten für, sagen wir mal,
die A5?
Okay, und dann fangen wir vielleicht mit ein paar Beobachtungen an.
Also die Beobachtungen sind... und jetzt zeige ich einfach ein paar
Karten.
Die Karten sind auch leider der Grund dafür, dass die Folien dieses
Mal heute ein bisschen größer sind.
Beim runterladen sind siebeneinhalb Megabyte.
Aber es sind einfach ein paar Karten mit kürzesten Routen.
Also hier von Karlsruhe nach Kopenhagen oder von Kopenhagen nach
Karlsruhe und hier von Karlsruhe nach Berlin.
Das sind jetzt einfach nur mal so ein paar Beispiele, ja.
Von Karlsruhe nach Wien, hier sieht man vielleicht schon was
Interessantes und zwar...
also hier Karlsruhe nach Berlin und Karlsruhe nach Wien hat ein Stück,
das ziemlich gleich ist.
Also sie fahren erstmal nach Osten und dann biegen sie entweder nach
Norden oder nach Osten.
Also sie fahren halt nach Osten weiter.
Und Karlsruhe nach München, das sind jetzt lauter so Verbindungen im
Prinzip.
An der Stelle sehen sie vielleicht noch gar nicht so viel.
Was wesentlich interessanter ist, also hier nach Paris, hier nach
London mit Fähre oder durch den Tunnel, nach Brüssel, genau, was
jetzt, ich warte, genau, ich warte auf diese Folie.
Was jetzt interessanter ist, wenn sie sich angucken, wie sieht das
denn an, wenn ich reinzoome auf den ersten Abschnitt dieser Strecke.
Also was jetzt passiert ist, ist, wir gucken uns an, was wäre denn die
kürzeste Route von Karlsruhe nach irgendwo, nach Kopenhagen in dem
Fall und wie sehen die aus?
Also wie sehen die ersten, keine Ahnung, 30 Minuten aus von dieser
Route?
Okay, sie starten hier natürlich beim Informatikgebäude und biegen
dann hier oder gehen dann hier rechts, Nuller Allee könnte das sein
und dann biegen sie auf die A5, oder sie fahren auf die A5 auf und
dann geht es nach Norden.
Okay, jetzt hat sich gerade was geändert, Karlsruhe Berlin sieht genau
so aus.
Also sie gehen auch irgendwie so grob nach Norden.
Karlsruhe nach Wien sieht genau so aus.
Karlsruhe nach München sieht ein bisschen anders aus, sie biegen halt
jetzt auf eine andere Autobahn, ich weiß nicht, ich glaube, das ist
die A8, müsste das sein, oder?
So, Karlsruhe nach Rom sieht wieder ein bisschen anders aus, aber auch
hier hat sich nicht viel geändert.
Also ich bin jetzt gerade am Hin- und Herschalten zwischen Karlsruhe
München und Karlsruhe Rom.
Also insbesondere ihr Zugangspunkt, gut, das ist jetzt ein kleines
bisschen verschoben, wahrscheinlich, weil die Auffahrt einfach die
andere ist, oder etwas andere, oder vielleicht ist es auch einfach
eine Zeichenungenauigkeit.
Aber im Prinzip, der erste Teil der Strecke sieht genau gleich aus.
Und diese Punkte, die sie hier sehen, diese blauen Punkte, das sind
das, was ich mal Transitknoten nennen möchte.
Das sind die Knoten, wo sie als erstes mal hinkommen, je nachdem, wo
sie hinwollen, wählen sie sich einen von diesen Transitknoten aus, der
günstig für dieses Ziel ist, und dann fahren sie als allererstes mal
zum Transitknoten.
Also wirklich der allererste Teil der Strecke sieht immer gleich aus.
Gut, wenn sie nach Westen wollen, dann sieht es natürlich anders aus,
aber auch da, naja gut, da habe ich jetzt, glaube ich, kein Beispiel
mehr.
Brüssel und London, okay, Brüssel und London ist dann beides mal nach
Westen, und dann fahren sie hier die B10, ich denke mal, es ist die
B10, einfach nach Westen.
Okay, aber was kann man daraus lernen?
Das Wichtigste ist, glaube ich, es gibt sowas wie Zugangspunkte oder
Transitknoten.
Das sind die Punkte, zu denen sie oder wo alle kürzesten Routen drüber
führen.
Das heißt, sie biegen erst mal auf so eine andere Hierarchie ein, auf
die Autobahn, und um das zu tun, besuchen sie den geeigneten
Zugangspunkt.
Was man jetzt also tun kann, ist, man kann sich so eine ganze Ebene
von diesen Zugangspunkten nehmen, also alle Zugangspunkte für alle
Knoten und die jeweiligen langen Strecken sich raussuchen,
rausrechnen, was diese Zugangspunkte sind, und dann nur noch die
Zugangspunkte betrachten bei den kürzesten Wegstrecken.
Also das heißt, sie müssen jetzt nicht mehr alle 18 Millionen Knoten
angucken von diesem ganzen Netzwerk, wenn sie von Karlsruhe nach Rom
den kürzesten Weg berechnen wollen, sondern sie gucken sich nur an, wo
sie in Rom genau hinwollen, wo da der nächste Zugangsknoten ist und wo
dann halt der Zugangsknoten von Karlsruhe aus ist.
Also sie gucken sich nur die Zugangsknoten selber an.
Genau, es gibt also zwei getrennte Phasen der Wegstreckenberechnung
und vom Zugangspunkt und die eigentliche lange Fahrt zwischen den
verschiedenen Zugangspunkten.
Genau, wichtig ist, es gibt nicht viele von diesen Zugangspunkten.
Also pro Knoten, also für jeden Knoten sind das vielleicht so was wie
10 Zugangspunkte.
Ja, ich weiß jetzt gar nicht, warum das nochmal da ist.
Bin ich gerade ein bisschen verwirrt.
Mit den vorhin habe ich gar nicht mehr gerechnet.
Also, das soll, glaube ich, auch nur sagen, das sind halt die
Zugangspunkte, die wir da schon mal hatten.
Und je nachdem, wo sie hinwollen, wählen sie sich halt einen aus,
fahren zum Zugangspunkt und fahren von da aus weiter.
Nee, das hatten wir doch schon mal.
Irgendwas stimmt mit den Folien, glaube ich nicht.
Da muss ich mal aussortieren.
Tut mir leid.
Okay, also erster Schritt, wir identifizieren diese Zugangsknoten,
diese Transitknoten und können als Vorberechnung, also natürlich
können wir nicht alle 18 Millionen Knoten von vornherein vorberechnen
mit ihren kürzesten Wegen und kurzen Abständen.
Wir tun das nur für die Zugangspunkte.
Das ist nämlich eine Information, die man immer wieder braucht.
Also je nachdem, wie die Anfrage ist, nimmt man dann halt einfach den
geeigneten Zugangsknoten und berechnet da halt die kürzesten Abstände.
Okay, und was sagt das über die Reisedauer oder über den kürzesten Weg
aus?
Es gibt einmal den Weg vom Startpunkt zum Zugangsknoten, zum nächsten
oder zum besten Zugangsknoten, dann den zwischen zwei Zugangsknoten
und den vom Zugangsknoten auf der anderen Seite zum eigentlichen Ziel.
Es muss nicht immer so sein.
Also es kann ja auch sein, Sie wollen von Karlsruhe Nord nach
Karlsruhe Süd oder sowas in die Südstadt, dann werden Sie natürlich
höchstwahrscheinlich jedenfalls nicht die A5 benutzen.
Also man muss sich dann erstmal entscheiden, möchte man eine lokale
Suche machen und dann machen Sie halt in der Karte halt das Übliche,
sowas wie ein Dijkstra auf den Knoten, die halt wirklich gerade in der
Nähe sind oder Sie machen halt diesen Spezialfall.
Und wie man das tut, man muss halt lokale Fälle ausfiltern.
Das heißt, man muss gucken, wann liegen Start und Ziel nah beisammen,
sodass es eigentlich nicht lohnt erst so einen Zugangsknoten zu
besuchen.
Okay.
Also das hier sind die Transitknoten von Start und Ziel jeweils als
Beispiel und dann muss man halt in der Suche vom Startpunkt und vom
Zielknoten eigentlich nur soweit suchen, mit den lokalen Berechnungen,
dass man halt die nächsten Zukunftsknoten hat und wie man da hinkommt.
So.
Was kriegt man dabei raus?
Man kriegt dabei raus, es geht halt viel, viel schneller als jedes Mal
über die 18 Millionen Knoten zu suchen, ist ja auch irgendwo klar.
Also bei einer Vorberechnungszeit von etwas über einer Stunde geht das
Ganze dann in 4 Mikrosekunden.
Das Ganze ist sogar verbessert worden auf weniger als 2 Mikrosekunden.
Das war eine, ich glaube, eine Bachelorarbeit, die auch am Lehrstuhl
Sanders geschrieben wurde.
Also ich mache gerade Werbung, merke ich.
Sie sollten auch Kryptographie machen.
Aber wenn Sie das interessiert, da am Lehrstuhl Sanders und auch am
Lehrstuhl Wagner gibt es halt Arbeiten, die sich sehr praktisch damit
beschäftigen.
Okay.
Letzte Folie zu dem Ausflug.
Was gibt es da für offene Fragen?
Also was ich jetzt überhaupt nicht besprochen habe.
Wie findet man gute Transitknoten?
Wie identifiziert man die?
Und wie findet man, wie kann man lokale Anfragen identifizieren?
Und wie vermeidet man die dann?
Da muss man andere Techniken benutzen.
Also das geht halt, da braucht man ein extra Algorithmen dafür.
Aber das wollte ich jetzt auch nicht vorstellen, sondern mir ging es
nur darum, einmal kurz zu skizzieren, was tatsächlich so geforscht
wird im Augenblick oder was so aktuelle Ergebnisse sind.
Und auch so Dinge, die für Sie vielleicht schon für Abschlussarbeiten
dann relevant sein könnten.
Okay.
Ja, vielleicht sollte ich noch sagen, wenn Sie hierzu Fragen haben,
kann ich die wahrscheinlich nicht beantworten, da das nicht mein
Forschungsgebiet ist.
Aber wenn Sie Fragen haben, können Sie mich auch gerne ansprechen.
Dann kann ich Sie vielleicht vermitteln oder dann kann ich vielleicht
jemanden finden, der wirklich Experte in genau dem Gebiet ist und Sie
dann und die Frage dann so beantworten.
Okay, deshalb frage ich jetzt gar nicht, ob es hierzu offene Fragen
gibt.
Ausnahmsweise.
Ich würde weitermachen im nächsten Kapitel und zwar zu minimalen
Spannenbäumen.
Und da würde ich es auch so machen, das Kapitel würde ich im
Augenblick heute nur motivieren, da wir mit der Zeit sehr gut dran
sind und deshalb wird es auch heute wahrscheinlich ein bisschen früher
Schluss werden.
Aber ich möchte es zumindest noch motivieren und Ihnen auch vielleicht
noch Gelegenheit geben, das schon mal in sich aufzunehmen, bevor wir
dann Mittwoch mit ein bisschen formaleren Sachen anfangen.
Okay, also worum geht es?
Es geht um minimale Spannenbäume.
Stellen Sie sich folgendes Pseudo-Beispiel vor.
Das ist ein Beispiel, was in der Realität so wahrscheinlich nicht
vorkommen würde, was aber zumindest schon mal das Gefühl gibt, dass da
ein Problem ist, das realistisch ist.
Also stellen Sie sich vor, es gibt hier diese vier Inseln und die
Aufgabe, Ihre Aufgabe ist es, die zu verbinden mit einem Fair
-Netzwerk.
Und diese jeweiligen Zahlen an den Kanten hier zwischen den Inseln A,
B, C, D, die geben an, wie teuer die Kosten, also entweder einmalig
oder die Unterhaltskosten von so einer Fair-Verbindung zwischen diesen
beiden Inseln jeweils wären.
Also Sie haben ja natürlich einen vollständigen Graphen und zwischen A
und D wäre es dann halt besonders teuer, so eine Fair-Verbindung zu
machen und zwischen D und B wäre es halt besonders billig.
So, und was ist Ihr Ziel?
Sie könnten natürlich das alles aufbauen, das wäre sehr teuer und sehr
bequem, also dann könnte jeder ganz schnell in einem Schritt von jeder
Insel zur anderen.
Wenn jetzt aber Ihr Ziel nur ist, okay, es ist egal, wenn die Leute
halt so eine Zwischenstation machen oder womöglich auch zwei
Zwischenstationen.
Sie möchten halt nur, dass der Graph zusammenhängend ist, also der
Graph der Verbindung, die Sie dann am Ende bauen.
Dann können Sie fragen, welche Verbindung muss ich denn hier
etablieren, sodass A, die Kosten möglichst niedrig sind und B, dass
Sie von jeder Insel zu jeder anderen Insel kommen können, auch
indirekt.
Und genau das ist die Frage nach einem minimalen Spannbaum.
Also ein bisschen formaler, ein minimaler Spannbaum kriegt, oder die
Frage ist eigentlich, Sie kriegen als Eingabe gegeben so einen Graphen
mit Gewichten dran, der muss nicht vollständig sein und die Gewichte
sind jetzt für das, was wir machen, sind ja einfach mal nicht negativ
oder sogar hier steht sogar positiv.
Und Sie kriegen dann also diesen Graphen mit Kanten und die Frage ist,
einen Baum zu finden, sodass dieser Baum alle Knoten verbindet.
Und klar, die Randbedingung ist, er soll minimales Gewicht haben.
In dem Beispiel wäre das jetzt halt, der Baum würde bestehen aus genau
diesen Kanten, die rot eingezeichnet sind.
Okay?
Also die 9 wäre insbesondere nicht da.
Also Sie können sich überlegen, 3 Kanten braucht man auf jeden Fall,
mit 2 Kanten kommen Sie nicht klar.
Und Sie brauchen aber auch keine 4 Kanten, denn Sie können hier, ist
ein bisschen umständlich, aber Sie können von 1 nach 2 nach 3 nach 4
gehen und so kommen Sie auch von 1 nach 4.
Da brauchen Sie diese 9er Kante nicht.
Also 3 Kanten reichen und die Kante, die Sie dann, also beliebige 3
Kanten in dem Fall, und die Kante, die Sie weglassen, das sollte halt
die sein, die am meisten Kosten spart.
Also Sie lassen die 9er Kante weg.
Eine Verallgemeinerung ist der Fall, wo Sie gar keinen
zusammenhängenden Graphen haben.
Sondern, wo von vornherein halt schon so Teile von dem Graphen
isoliert sind.
Sie haben da mehrere Zusammenhangskomponenten.
Und dann fragen Sie, dann hätten Sie sehr gerne einen Wald.
Also das ist dann die natürliche Verallgemeinerung, also eine Anzahl
von Räumen.
Das ist die natürliche Verallgemeinerung für solche Graphen.
Okay, dann die Anwendung, genau die Anwendungsfolie würde ich dann
noch machen.
Und genau, als nächstes, ich gucke noch mal genau die Schnitt- und
Kreiseigenschaften, die machen wir nächstes Mal.
Vielleicht noch ein Wort zu den Anwendungen.
Beim Netzwerkentwurf, also Sie sollen ein Netzwerk entwerfen, was
immer das dann genau ist, ein Computernetzwerk oder vielleicht auch
ein anderes Netzwerk.
Da gibt es manchmal das Problem, dass Sie gar nicht interessiert.
Also da gibt es viele Probleme, Sie können direkt dieses
Spannbaumproblem stellen, diese Frage nach einem Spannbaum stellen.
Das ist eine sehr einfache Frage.
Sie können aber auch die Frage stellen, ich bin interessiert an einem
Pfad.
Ich hätte nicht sagen sollen, dass wir heute früh aufhören, fällt mir
gerade auf.
Also bleiben Sie noch drei Minuten ruhig, das wäre sehr nett, danke.
Also es gibt das Problem, dass Sie an einem Pfad interessiert sind,
bei dem das maximale Kantengewicht, also das Gewicht der größten oder
der schwersten Kante auf diesem Pfad möglichst klein ist.
Also Sie sind sozusagen interessiert an einem Pfad, wo meinetwegen das
Gewicht so etwas sein könnte, wie die Sprunghöhe und Sie können aber
nur eine bestimmte Höhe springen und dann sind Sie interessiert an,
oder irgendeine andere Form von Hindernis ist dazwischen, und dann
sind Sie an einem Pfad interessiert, der möglichst geringe, maximale
Sprunghöhe hat, weil dann vielleicht das, was Sie da langschicken
müssen, nur gewisse Eigenschaften erfüllen muss, also nur eine gewisse
Höhe springen muss.
Und interessanterweise, das kann man zeigen, ist genau der Pfad in so
einem minimalen Spannbaum.
Also in einem minimalen Spannbaum kommen Sie von jedem Knoten zu jedem
anderen Knoten.
Und der Pfad, der halt die geringste, ich nenne es mal flapsig,
Sprunghöhe hat, also der bottleneck shortest path ist, das ist gerade
derjenige, den Sie in einem Spannbaum gehen würden.
Also das ist vielleicht ganz interessant.
Also beispielsweise von 1 nach 4, oder von 4 nach 1 wäre halt der
Pfad, bei dem Sie das geringste maximale Kantengewicht haben, naja,
gerade der, der den minimalen Spannbaum entlang geht.
Insbesondere ist es nicht der direkte.
Und auch nicht der insgesamt kürzeste.
9 ist immer noch insgesamt kürzer als 5 plus 7 plus 2.
Clustering bedeutet, dass in bestimmten, also stellen Sie sich so ein
MST vor und jetzt nehmen Sie so eine Kante weg.
Und zwar nehmen Sie die schwerste Kante in dem MST weg.
Also die Kante, sodass die Distanz zwischen den beiden Knoten am
größten ist.
Was Sie dann getan haben ist, dass Sie den Graphen gerade in zwei
Teile, oder die Menge der Knoten, gerade in zwei Teile gebrochen
haben.
Sie haben es an einer Stelle halt durchgebrochen.
Vorher war noch alles zusammenhängend, jetzt ist es an einer Stelle
durchgebrochen.
Und zwar an der Stelle, wo die größte Distanz war.
Und das ist eine Form von Clusterung, also in Cluster aufteilen.
Sie haben jetzt zwei Cluster geschaffen.
Also zwei Teile des Graphen.
Das kann wichtig sein, zum Beispiel bei Bildsegmentierung, wenn Sie
Objekte in einem Bild voneinander unterscheiden möchten, da wäre die
Kantengewichte wären da ein bisschen kreativer.
Das wäre sowas wie ein Kontrastunterschied zum Beispiel.
Und dann kann allgemein, also Clusterung, klar, soziale Netzwerke, da
gibt es sehr viele Anwendungen.
Okay, und das letzte ist, es gibt auch noch schwere Probleme, Problem
des Handlungsreisenden, das werden Sie vielleicht erst im dritten
Semester in seiner vollen Pracht würdigen können.
Das ist NP vollständig.
Und das ist also einfach ein schweres Problem.
Und dafür Approximationslösungen zu finden, also die beste Lösung
anzunähern, da ist einfach, da sind MST-Algorithmen ein gutes
technisches Tool.
Okay.
Das wäre es von meiner Seite.
Gibt es von Ihrer Seite Ausfragen?
Gut, dann bedanke ich mich für die Aufmerksamkeit.
Wir machen nächstes Mal weiter.
Achso, eine Sache ganz wichtig.
Bitte beachten Sie, am Mittwoch ist die Vorlesung nicht hier.
Steht doch auf der Webseite.
Wir mussten leider tauschen, weil hier eine, ich glaube, Karrieremesse
ist.
Wir sind am Hörsaal im Fasanengarten am Mittwoch.
Bis Mittwoch dann.