Wir hatten beim letzten Mal unsere Serie von Ergebnissen zur
Verbesserung von Dijkstra's Algorithmus beendet mit einem Algorithmus,
der in Linearzeit läuft, wenn wir zufällige Kantengewichte haben.
Und da er ja außerdem eine Erweiterung von Radix Heaps benutzt, hat er
eben außerdem diese Laufzeit m plus n log c.
Wir haben dann wieder schöne Beispiele für fortgeschrittene
Datenstrukturen, für Average Case Analyse.
Und ich möchte heute im ersten Teil der Vorlesung weitere Ergebnisse
zu kürzesten Wegen, die auch sehr schön ineinander greifen und die
auch wiederum neue Techniken einführen, die man auch jenseits von
kürzesten Wege-Algorithmen verwenden kann.
Dazu möchte ich mir zuerst das All-Pairs-Shortest-Path-Problem
anschauen.
Wir wollen jetzt nicht mehr von einem Knoten zu allen, sondern von
allen zu allen.
Ausgabekomplexität ist quadratisch in n.
Wir müssen also damit rechnen, dass vielleicht die Laufzeit höher wird
als für Dijkstra's Algorithmus.
Wie geht das?
Zunächst mal der Fall nicht-negativer Kantengewichte ist relativ
langweilig, weil im Wesentlichen können wir dann einfach von jedem
Knoten aus einen Dijkstra laufen lassen.
Dann kriegen wir n mal m diese Komplexität hier.
n mal m plus n Quadratlog n.
Und was viel Besseres ist auch nicht bekannt.
Es gibt Algorithmen, die für sehr dichte Graphen in n hoch 3 laufen.
Moment, das ist ja n hoch 3.
Das ist hier auch.
Viel besser weiß man eigentlich gar nichts.
Als einfach trivial Dijkstra's Algorithmus von überall anfangen.
Es kann sein, dass man dann mit schneller Matrix-Multiplikation bei
sehr dichten Graphen noch irgendwas machen kann.
Da bin ich gerade nicht informiert, aber das ist nicht so spannend,
weil es eben nur für sehr dichte Graphen wäre.
Aber was ein bisschen überraschend ist, wenn wir sowieso von allen zu
allen rechnen wollen, dann können wir mit der gleichen Komplexität wie
dieser hier auch mit negativen Kantengewichten auskommen.
Zur Erinnerung, wenn wir allgemeinen Kantengewichte erlauben, also
auch negative, dann gibt es einen ganz simplen Algorithmus, der
kürzeste Wege berechnet.
Das ist der Bellman-Ford-Algorithmus.
Was der im Endeffekt macht, der wiederholt n mal eine Relaxation aller
Kanten in beliebiger Reihenfolge.
Zumindest worst case ist das im Wesentlichen das Beste, was bekannt
ist.
Da muss man jetzt noch ein bisschen vorsichtig sein.
Wenn der Graph negative Kreise enthält, dann passieren komische Dinge.
Das haben wir auch in Algorithmen 1 gemacht.
Weil wenn irgendwie von Start zum Zielknoten irgendwie ein negativer
Kreis erreichbar ist, dann kann man den beliebig oft durchlaufen.
Und dann ist die Entfernung vom Start zum Zielknoten eigentlich
minusunendlich.
Das heißt, wenn es negative Kantengewichte gibt, im völlig allgemeinen
Fall, muss man dann komplizierte Fallunterscheidungen machen, ob
irgendwie ein negativer Kreis eingebaut werden kann in so einem
kürzesten Weg, dann ist es minusunendlich.
Und sonst kann man durchaus eine kürzeste Wegelänge definieren.
Wir machen es uns ein bisschen leichter.
Wir nehmen an, dass es überhaupt keine Kreise mit negativem Gewicht
gibt.
Das ist eine häufige Annahme.
Und es gibt auch viele Anwendungen, wo das der Fall ist.
Und dann gucken wir uns den Fall an.
Es darf negative Kanten geben, aber keine negativen Kreise.
Und den Fall betrachten wir jetzt.
Und in dem Fall berechnet ein Durchlauf von diesem Bellman-Ford
-Algorithmus den O von N mal M Zeit die kürzesten Wege von einem
Startknoten S zu allen anderen Knoten.
Und was ich Ihnen heute vorführen werde ist, der Triviale wäre, dass
man das N mal macht, dann kriegt man N² mal M.
Aber was wir jetzt zeigen werden ist, wir machen denen nur einmal den
Bellman -Ford.
Mit Laufzeit O von N mal M.
Und dann müssen wir nur noch den Dijkstra-Algorithmus verwenden.
Wir werden nämlich die Kantengewichte so manipulieren, dass sie nicht
negativ werden.
Und uns trotzdem die korrekten kürzesten Wegedistanzen verraten.
Und dafür braucht man ein Konzept, das bei Graphen-Algorithmen
allgemein sehr nützlich ist.
Das sind Knotenpotentiale.
Wir definieren für jeden Knoten eine reelle Zahl Pot von V.
Da sind wir erstmal frei darin, wie wir die definieren.
Aber wir werden die hinterher so wählen, dass wir was davon haben.
Und dann definieren wir mithilfe dieses Potentials reduzierte Kosten
c² von E für jede Kante.
Wo wir sagen, von der Kante E gleich UV kriegt ein reduzierte Kosten
c² von E gleich Potential von U plus die ursprünglichen Kosten minus
Potential von V.
Der Trick bei dieser Definition ist, das gibt uns eine Möglichkeit, an
Kantengewichten zu drehen, ohne dass sich kürzeste Wege verändern.
Das werde ich Ihnen jetzt zeigen.
Mit diesen Kosten finden wir die gleichen kürzesten Pfade wie vorher.
Das gilt für alle möglichen Potentiale.
Wir können sie also frei definieren.
Warum ist das so?
Schauen wir uns mal die reduzierten Kosten eines Pfads an.
E1 bis EK-1 und V1 bis VK sind die reduzierten Kosten dieses Pfades.
Einfach die Summe der reduzierten Kosten der Kanten EI.
Dann setzen wir die Definition ein.
Potential von VI plus Kosten von EI minus Potential von VI plus 1.
Der Trick ist, das nennt man in der Mathematik auch eine
Teleskopsumme.
Das Potential jedes Knotens im Inneren dieses Pfads wird genau einmal
addiert und einmal subtrahiert und fällt deshalb raus.
Das Einzige, was üblich bleibt, sind das Potential von V1 und das
Potential von VK.
Wir kriegen also für diese Summe hier Potential von V1 plus
ursprüngliche Kosten des Pfades minus Potential von VK.
Die kürzesten Wege Entfernungen ändern sich durchaus, aber die
Änderung hängt nur vom Startknoten und vom Zielknoten ab.
Das bedeutet, für beliebige Pfade, die den gleichen Start- und
Zielknoten haben, sind diese Veränderungen die gleichen.
Das heißt insbesondere gilt, eine Pfad P ist kürzer als der Pfad Q,
genau dann, wenn die reduzierten Kosten von P kleiner gleich den
reduzierten Kosten von Q sind.
Weil da einfach dieses Potential V1 und Potential VK das kann man
dann, wenn das auf beiden Seiten dieser Ungleichung steht,
wegsubtrahieren.
Das addiert man weg, das subtrahiert man weg und dann bleiben die
Kosten von CQ und die Kosten von CP übrig.
Was haben wir jetzt davon?
Im Allgemeinen klingt das jetzt nach irgendeinem hübschen Spiel, aber
was wir jetzt machen werden ist, wir werden die Potentiale so wählen,
dass die reduzierten Kosten nicht negativ werden und dann können wir
Dijkstra´s Algorithmus verwenden.
Und dieses Wählen der Potentiale, dafür brauchen wir den Bellman-Ford
-Algorithmus.
Das ist jetzt der Trick.
Das heißt, wir machen einmal den allgemeinen Bellman-Ford-Algorithmus,
der mit negativen Kantengewichten umgehen kann und der liefert uns
dann Knotenpotentiale, mit denen wir die reduzierten Kosten nicht
negativ machen können und ab dann können wir für beliebige Stazilpaare
den Dijkstra-Algorithmus verwenden.
Wie machen wir das?
Wir berechnen den Bellman-Ford nicht ganz genau auf dem Eingabegrafen,
sondern wir fügen einen zusätzlichen Knoten S hinzu und kanten von S
zu allen anderen Knoten mit Gewicht 0.
Das machen wir deshalb, weil wir im gesamten Grafen sozusagen was
machen wollen und wir brauchen zwischendurch etwas, das...
wir müssen sozusagen jede negative Kante da erreichen über das S.
Aber das wird hinterher klar werden, wozu wir das brauchen.
Und von diesem S aus berechnen wir jetzt den Bellman-Ford-Algorithmus.
Man könnte es auch ganz heuristisch erstmal so sagen, ich will ja
später kürzeste Wege von überall nach überall machen, deshalb, wenn
ich nur einen Bellman-Ford mache, wo sollte ich denn dann starten?
Und der Trick ist, naja, ich starte irgendwo hier in einem
zusätzlichen Knoten, von da komme ich überall hin und erreiche
insbesondere auch alle Kreise in dem Grafen.
Man hat dann den Nebeneffekt, dass man dann auch alle negativen
Kreise, wenn es die gäbe, finden würde.
Da macht man den gleichen Trick.
So, und das Potenzial, das ich definiere, ist dann ganz einfach die
kürzeste Wegedistanz von diesem neuen Knoten S nach V für alle Knoten
V in V.
Und wir behaupten, dass durch dieses Potenzial die reduzierten Kosten
nicht negativ werden und wir dann da extra benutzen können.
S können wir entfernen, weil in dem richtigen Grafen ist S ja nie auf
einem kürzesten Weg, weil da nur Kanten rausgehen.
Zunächst mal brauchen wir hier diese Annahme, dass es keine negativen
Kreise gibt, weil sonst dieses Potenzial nicht wohl definiert wäre.
Dann wären nicht alle von diesem µ von V reelle Zahlen, sondern einige
wären eben minusunendlich und damit kann ich keine Potenziale
definieren.
So, wenn das vom Tisch ist, kann ich mir jetzt eine beliebige Kante
angucken und es gilt halt ohnehin, weil ich...
nee, es gilt immer, dass die kürzeste Wegeentfernung von
U, also von S aus, plus C von E ist größer gleich µ von V.
Weil angenommen, das wäre echt kleiner, dann könnte ich ja einen neuen
kürzesten Weg zu V definieren, der über U läuft und dafür brauche ich,
dass von S aus U erreichbar sein muss.
Und das ist der Grund, wieso ich diese Kanten da einführe.
Also wenn das hier nicht gelten würde, dann gäbe es einen kürzeren Weg
von S nach U über diese Kante nach V und ich habe aber angenommen,
dass das hier die kürzeste Wegeentfernung ist.
Also das gilt und daraus folgt bereits, dass die reduzierten Kosten
nicht negativ sind, weil wenn ich mir jetzt eine beliebige Kante E
gleich U mal V anschaue, dann ist ja die Definition des
Knotenpotentials so, dass die reduzierten Kosten jetzt µ von U plus C
von E minus µ von V sind, aber das Rote hier ist ja gerade das hier,
da gilt, ist es größer gleich µ von V.
Also das ist
größer gleich µ von V minus µ von V und das ist 0.
Fragen zu diesem Beweis, dass wir jetzt nicht negative reduzierte
Kosten haben?
Und dann ergibt sich der folgende Algorithmus für All-Pairs-Shortest
-Paths.
Wir fügen diesen neuen Knoten ein, die Kanten von S nach V mit Kosten
0, dann berechne ich so ein Potential, das gleich diesem kürzeste
Wegevektor ist, mit Hilfe des Bellman-Ford Single-Short-Shortest-Path
-Algorithmus mit Startknoten S und der Gewichtsfunktion C.
Dann mache ich für jeden Knoten X in V einen normalen Dijkstra auf den
reduzierten Kosten und schließlich damit berechne ich so eine
Distanztabelle und schließlich muss ich die noch korrigieren, indem
ich eben µ von V w als reduziertes µ von V w plus Potential w minus
Potential v um sozusagen diese Manipulation durch die Potentiale
wieder rückgängig zu machen.
Fragen dazu.
Und wir werden dann später in der Vorlesung sehen, dass wir Potentiale
auch noch sozusagen am anderen Ende des Spektrums der kürzesten Wege
-Algorithmus einsetzen können, nämlich auch dann, wenn ich nur den
kürzesten Weg von einem Startpunkt zu einem Zielpunkt berechnen will.
So, Laufzeit ist hier den Startknoten hinzufügen O von N, die
Nachverarbeitung ist O von N² und ich habe N mal Dijkstra, also N mal
N plus N log N ist Nm plus N² log N.
Und hier habe ich vergessen den Bellman-Ford, das ist natürlich
nochmal ein Nm, aber das ist der gleiche Term wie der hier.
Eine ganz nette Beobachtung ist All-Pairs-Shortest-Path ist ein
relativ leicht zu parallelisierender Algorithmus, weil ich kann den
Bellman -Ford relativ leicht parallelisieren und N-unabhängige
Dijkstra -Suchen kann ich erst recht gut parallelisieren.
Jeder Prozessor schnappt sich einige von diesen kürzesten Wegen suchen
und führt die durch.
Dass es trotzdem Arbeiten zu parallelem All-to-All gibt, hängt so ein
bisschen damit zusammen, dass das unter Umständen ein
Speicherplatzproblem ist.
Wenn ich einen sehr großen Graphen habe, der den Speicher komplett
füllt, dann kann ich es mir vielleicht nicht leisten, diese Distanz
-Arrays für alle Knoten im Speicher zu halten oder für jeden
Prozessor.
Allerdings ist es so, dass hier schon die Ausgabekomplexität
quadratisch ist.
Das ist dann ohnehin die Frage, was man da überhaupt berechnen will.
Aber wenn man zum Beispiel nur alle kürzesten Wege irgendwie mal
aufzählen will und da irgendwelche Mittelwerte bilden will, braucht
man dafür ja nicht viel Platz.
Weitere Fragen zum All-to-All-shortest-Path.
Es geht um die Frage, es gibt noch den Floyd-Warshall-Algorithmus für
All -to-All-shortest-Path.
Der braucht, soweit ich weiß, kubische Zeit, also eher noch drei.
Das ist langsamer, außer wenn M quadratisch ist.
Jetzt gucken wir uns das andere Ende des Spektrums an.
Ich finde das auch eigentlich ganz spannend, dass Theoretiker
irgendwie so tun, als wäre es das natürlichste Ding von der Welt, dass
das kürzeste Wegeproblem einen Startknoten hat und dann alle Knoten
als Zielknoten.
Das ist überraschend.
Man kann ganz viele Varianten des kürzesten Wegeproblems formulieren.
Und warum ausgerechnet dieses?
Meine Antwort ist, weil Dijkstra's Algorithmus genau das ausrechnet.
Und das ist irgendwie der schönste von diesen kürzesten
Wegealgorithmen, zumindest von den klassischen.
Aber in gewisser Weise von der Anwendungsperspektive und auch von der
Frage, ich will ja oft eigentlich nur eine Sache ausrechnen, hat man
ja einen Startknoten und einen Zielknoten und will dann die kürzeste
Wegeentfernung dazwischen ausrechnen.
Und tatsächlich sind auch viele Anwendungen so.
Also zum Beispiel Navigationssysteme, da will man ja von irgendeinem
Standpunkt zu einem anderen und nicht zu allen anderen.
Das wäre irgendwie ein bisschen blöd, wenn ein Navi sagen würde, ja,
du bist hier, ich zeige dir jetzt, wo du überall hin kannst und wie
weit das ist.
Das wäre ein bisschen unübersichtlich.
Und natürlich kann man das auch ausnutzen.
Also ich will nicht alles wissen, sondern nur zu einem Zielknoten von
einem Startknoten.
Wie mache ich das?
Und jetzt kommt als Trick Null sozusagen eine sehr einfache
Beobachtung, die das wieder rechtfertigt, dass man vielleicht
Dijkstra's Algorithmus einfach verwendet, weil was man natürlich
machen kann, ist einfach den mal loslaufen zu lassen und dann bläht
der ja sozusagen so einen Ballon aus von Knoten, deren kürzeste
Wegeentfernung er gefunden hat und im Wesentlichen hört man einfach
dann auf, wenn der Zielknoten gefunden wurde.
Das ist dann wieder eine schöne Eigenschaft von Dijkstra's
Algorithmus.
Wir wissen ja, sobald der gescannt wird, dieser Zielknoten, ist die
kürzeste Wegeentfernung von dem auch endgültig bekannt.
Aber ein Theoretiker fragt natürlich jetzt, was nützt dir das?
Das könnte ja sein, dass T irgendwie der letzte Knoten ist, den der
Dijkstra's Algorithmus besucht.
Das heißt, im Worst-Case ist das die gleiche Komplexität.
Aber natürlich könnte man jetzt ja auch Average-Case-Komplexität oder
sowas angucken.
Dann würde der Theoretiker sagen, ja gut, ist aber auch nicht so
spannend.
Im Mittel ist es halt so, dass die Hälfte der Knoten weiter weg sind
und die Hälfte der Knoten näher dran als der Zielpunkt, den du hast.
Das heißt, du sparst die Hälfte der Laufzeit von Dijkstra's
Algorithmus.
Big Deal.
Aber jetzt frage ich angenommen, Sie bauen diesen Algorithmus in ein
Navigationssystem ein, zum Beispiel
wenn das Karten geladen hat für eine Europakarte.
Was meinen Sie denn, wie viel das im Mittel dann spart?
Sie sagen 90 Prozent oder wahrscheinlich ist es sogar 98 oder 99
Prozent, weil Europa hat irgendwie ein paar hundert Millionen
Einwohner.
500 Millionen.
99,9 Prozent von denen wohnen nicht in Karlsruhe, denke ich mal.
Aber wenn Sie sich die Statistik angucken, wie weit man mit einem Pkw
normalerweise fährt, dann sind das so 50 Kilometer oder sowas im
Mittel.
Das heißt, Sie gucken sich wirklich nur einen Bruchteil der Knoten des
Graphen an.
Google routet sogar auf einer Weltkarte, dann ist es noch schwieriger.
Trotzdem ist es tatsächlich so, wenn Google Dijkstra's Algorithmus
einsetzen würde, dann müssten Sie schon eine ganze Reihe zusätzliche
Server kaufen.
Man müsste eben, wenn man dann mal eine lange Anfrage macht, auch
ziemlich lange warten.
Also will man daran noch einiges verbessern.
Jetzt will ich erst mal einen Überblick über so Techniken geben, wie
man das noch weiter verbessern kann.
Wir werden uns als erstes angucken, was relativ einfach ist.
Ich kann vom Startknoten vorwärts suchen und vom Zielknoten rückwärts,
eine bidirektionale Suche.
Und man kann dann argumentieren in einem Straßennetzwerk, dass einem
das so was wie einen Faktor 2 spart an Laufzeit.
Es ist so, wenn Sie kürzeste Wege in irgendwelchen abstrakten
kombinatorischen Optimierungsproblemen suchen, dann ist das oft eine
exponentielle Verbesserung, diese bidirektionale Suche.
Weil man da sozusagen eine ganz andere Geometrie unter sich hat.
Deshalb ist das schon eine ziemlich wichtige Technik, die allerdings
für sich alleine auf dem Straßennetzwerk einen jetzt auch nicht vom
Hocker reißen würde.
Dann gibt es zielgerichtete Suche.
Das ist die Idee, dass ich vom Start nicht in alle Richtungen
gleichzeitig suche.
Das ist ja auch intuitiv nicht so sinnvoll, sondern vielleicht habe
ich eine ungefähre Idee davon, in welcher Richtung mein Ziel liegt und
gucke vorzugsweise in die Richtung.
Wir werden sehen, dass man Dijkstra's Algorithmus so modifizieren
kann, dass er das tatsächlich tut und einem garantiert optimale
Lösungen liefert.
Man kann die beiden Ideen kombinieren.
Das ist ein bisschen hässlich.
Da werde ich nicht so viel zu sagen.
Und dann gibt es fortgeschrittene Techniken.
Da gibt es eine eigene Vorlesung, die im Moment von der Arbeitsgruppe
Wagner gemacht wird, zu Routenplanungstechniken.
Dass man so Hierarchien ausnutzt.
Ich habe das so ein bisschen angedeutet darüber, dass ich sage, in der
Nähe von Start und Ziel muss ich vielleicht auch kleine Straßen
angucken.
Und weiter weg genügt es, das Fernstraßennetz anzuschauen.
Und ich habe dann erheblich weniger Aufwand.
Die Schwierigkeit dabei ist zu definieren, was ist das Fernstraßennetz
und was ist weit weg.
Das haben in den 90er Jahren die Leute, die Routenplaner gebaut haben,
irgendwie heuristisch gemacht, was dann dazu führte, dass man entweder
nicht die optimalen Routen bekam oder sehr viel Handarbeit involviert
war, das Fernstraßennetz zu definieren.
Man kann aber eben, wenn man Algorithmiker ist und Optimalität und
Korrektheit von Algorithmen beweisen kann, kann man eben die
Definitionen dann so bauen, dass man das automatisch herausfinden
kann, was das Fernstraßennetz ist.
Das ist so die Idee dahinter.
Man kann noch aggressiver sein und ganze Teilabschnitte tabellieren.
Aber das ist jetzt nicht in der Vorlesung hier drin.
Das habe ich hier versucht so anzudeuten, dass ich sage, man macht
jetzt tatsächlich nur noch in der Umgebung von Start und Ziel eine
Suche, findet dabei die Entfernungen zu bestimmten wichtigen Knoten
und man hat eben eine vollständige Abstandstabelle vorberechnet
zwischen diesen wichtigen Knoten.
Oder da gibt es eine ganze Reihe Ansätze, wie man eben noch
aggressiver vorberechnen kann.
Das hat aber auch immer was mit dieser Hierarchie hier zu tun, weil
diese Vorberechnung macht man eben vorzugsweise zwischen wichtigen
Knoten.
Man muss dann also immer diese Hierarchie automatisch finden.
Vielleicht auch noch so ein bisschen zum Hintergrund.
Diese beiden Techniken funktionieren für beliebige Graphen.
Diese hier funktionieren sehr gut für Straßennetzwerke.
Aber in anderen Anwendungen ist das irgendwie weniger klar, wie man
das macht.
Und je weiter ich weg bin von Straßennetzwerken, desto weniger
funktionieren die, sage ich mal.
Aber es gibt da durchaus auch andere Dinge.
Zum Beispiel fand ich das dann spannend, dass man diese Techniken dann
auch in Computerspielen einsetzt.
Und was ich noch witziger finde, ist, dass der traditionelle Name für
diese Sachen Game AI heißt.
Stellen Sie sich irgendwie so ein Ballerspiel vor.
Da gibt es ja Figuren, die der Computer spielt.
Und er muss ja auch diese Figuren über das Spielfeld bewegen.
Und das macht er mit Hilfe von kürzester Wegesuche.
Und wenn es viele Figuren gibt, kann tatsächlich diese kürzeste
Wegesuche einen erheblichen Teil der Gesamtlaufzeit des Spiels sein.
Und deshalb brauchten die eben effiziente Algorithmen dafür.
Und das galt wohl als einer der Kernprobleme der Game AI.
Der Computer muss dafür sorgen, dass diese Figuren sich intelligent
verhalten.
Und ein Zeichen von Intelligenz ist, dass die nicht durch die Gegend
irren, sondern irgendwie zielstrebig Dinge tun.
Und dafür muss man kürzeste Wege suchen.
Also insofern bin ich auch jemand, der AI macht.
Und das ist ja ganz toll, weil das im Moment einige Leute glauben,
dass das das einzige innovative Gebiet der Informatik ist.
Ich wäre nie auf die Idee gekommen, das als AI zu bezeichnen.
Gut.
Also diese ersten beiden Sachen möchte ich Ihnen vorführen.
Auch wie gesagt, weil die in vielen Anwendungen nützlich sind und es
gar nicht so unwahrscheinlich ist, dass Sie über sowas mal stolpern.
Übrigens, das hier findet man auch in AI-Büchern als klassische AI
-Technik.
Artificial Intelligence.
Weitere Fragen zum allgemeinen Setup sind jetzt in dem Spiel kürzeste
Wege zwischen einem Knoten und noch einem Knoten.
Wie mache ich bidirektionale Suche?
Ich mache eine Vorwärtssuche auf dem normalen Graphen.
Ich mache eine Rückwärtssuche auf was für einem Graphen?
Na ja, da muss ich die Kanten alle umdrehen in der Annahme, dass das
ein umgerichteter Graph ist.
Und dann gibt es zwei Fragen.
Die eine lautet, in welcher Reihenfolge mache ich das?
Wie wechsle ich die beiden Suchen ab?
Da gibt es verschiedene Varianten.
Aber ich glaube, eine robuste ist es, das immer strikt abwechselnd zu
machen.
Also immer einen Knoten zu scannen auf jeder Seite.
Und die andere Frage ist, wann bin ich fertig?
Ja, bisher bin ich abgebrochen, wenn ich das Ziel erreicht habe.
Aber es geht ja jetzt darum, ich will ja gar nicht von S bis zum Ziel
suchen.
Und ich will auch nicht von T bis zurück nach S suchen.
Sondern diese Suchfronten sollen sich irgendwie treffen.
Und da muss ich natürlich irgendwas geeignetes tun.
Und was man da halt macht, ist, dass man die kürzeste Distanz, die man
bisher gefunden hat, von S nach T sich merkt.
Die ist am Anfang unendlich.
Und am Anfang sind auch diese Distanzfunktionen für die Vorwärts- und
Rückwärtssuche unendlich, außer bei S und T.
Aber wann immer man irgendwo eine neue Vorwärtsdistanz ändert, ist die
Rückwärtsdistanz auch schon was darüber bekannt.
Und dann ist offenbar Vorwärtsdistanz von S nach U plus
Rückwärtsdistanz von U nach T eine obere Schranke für die kürzeste
Wegelänge.
Und die merke ich mir in diesem DST.
Und das läuft halt immer so mit.
Das kostet eben zusätzlich einen kleinen konstanten Faktor Laufzeit.
Und das Abbruchkriterium ist dann, wenn ich einen Knoten scanne, der
in der anderen Richtung bereits gescannt wurde.
Das heißt, die Suche trifft sich hier an einem Knoten, der in beide
Richtungen gescannt wurde.
Und den, der als zweites gescannt wurde, den muss ich dann auch gar
nicht mehr scannen.
Und auf den ersten Blick würde man jetzt denken, aha, und dann läuft
der kürzeste Weg über genau diesen Knoten.
Aber genau das ist hier nicht der Fall, sondern dann weiß ich, dass
DST die kürzeste Wegedistanz von S nach T definiert.
Das kann aber durchaus sein, dass das über einen anderen Knoten läuft.
Also man muss ein bisschen aufpassen, aber dann ist das einigermaßen
intuitiv, was hier passiert.
Fragen dazu?
So, jetzt zu dieser zielgerichteten Suche.
Also vielleicht wieder erst bildlich.
Normalerweise macht man halt so einen Kreis wachsen.
Und jetzt würde ich vielleicht so eine Ellipse wachsen lassen auf T
hin.
Und der Trick ist, ich habe das so intuitiv gesagt, wir wollen
irgendwie in Richtungen suchen, die auf T hinführen.
Und eine Möglichkeit, das zu präzisieren, ist zu sagen, ich habe eine
Funktion, f, die abschätzt, wie weit es von einem Knoten zum Ziel ist.
Und ich nehme an, die weiß ich irgendwoher.
Also dafür brauche ich im Allgemeinen zusätzliches Wissen über die
Anwendung.
Weil das im Graf selber erst mal nicht drin steht.
Wir werden dann gleich eine Technik sehen, wie man das über
Vorverarbeitung dann aus der Grafinformation selber rausziehen kann.
Aber tatsächlich sind die meisten Anwendungen dieses Verfahrens a
Sternsuche, so dass das aus der Anwendung dieses Wissen kommt und sich
dann leicht berechnen lässt.
Und dann je nachdem, wie gut dieses Wissen ist, ist das eine effektive
Technik oder es bringt halt nicht so viel.
Und was ich jetzt mache, ist, dass ich im Endeffekt wieder ein
Potential definiere, das genau dieses f von v ist.
Und ich definiere dann die reduzierten Kosten als
die ursprünglichen Kosten plus Potential von dem Anfangsknoten der
Kante minus Potential vom Endknoten der Kante.
Beziehungsweise, was man dann meistens macht, ist, dass man gar nicht
explizit die Kantengewichte reduziert, weil das würde ja dann lineare
Zeit brauchen, einmal durch den ganzen Grafen durchzugehen, sondern
dass man das implizit macht.
Und dann kann man genauso gut hergehen und sagen, ich verändere die
Definition der Priorität in der Prioritätsliste.
Da nehme ich nämlich jetzt die Priorität Distanz, also Tentative
Distance in Dijkstra's Algorithmus plus diese Abschätzung.
Das bedeutet, dass wenn dann Knoten einen hohen Abstand zum Ziel hat,
dann rückt er in der Prioritätsliste weiter nach hinten.
Und wenn er aber einen niedrigen Abstand hat, dann rückt er nach vorne
und dadurch kriege ich diesen Zielrichtungseffekt.
Genau, das habe ich schon gesehen.
Ich definiere dieses Potential und jetzt einfach, um mal zu sehen, zu
zeigen, dass das effektiv sein kann, schauen wir den Extremfall an,
dass wir die kürzeste Wegeentfernung schon kennen.
Dann ist die reduzierte Distanz Ich gucke mir jetzt eine Kante auf dem
kürzesten Weg an.
Die reduzierten Kosten von UV sind die ursprünglichen Kosten plus µ
von V,t minus µ von O,t.
Aber wenn ich diesen Pfad tatsächlich genommen habe, dann kommt da am
Ende 0 raus.
Das heißt, die Kanten auf dem kürzesten Weg kriegen alle reduzierte
Kosten null.
Und das würde bedeuten, dass der Dijkstra-Algorithmus nur Knoten auf
diesem kürzesten Pfad relaxiert.
Er würde also perfekt arbeiten.
Er läuft diesen Pfad entlang, relaxiert dann noch alle Kanten, die da
rausführen.
Insofern kann das nochmal zusätzliche Arbeit verrichten.
Aber der Suchraum ist sozusagen perfekt.
Guckt sich nur den kürzesten Weg an.
Hier haben wir nochmal ein Bild dazu.
Das hier ist das Kantengewicht.
Ich addiere das Gewicht von V nach T, das ist das hier.
Und ich subtrahiere das Gewicht von U nach T.
Aber µ von U,t ist ja gerade CuV plus µV,t.
Das heißt, das ist das Gleiche.
Das Grüne wird addiert, das Blaue wird subtrahiert.
Fragen dazu?
Genau.
Jetzt muss ich mir also überlegen, welche Eigenschaften muss dieses F
von V haben, damit ich am Ende korrekte Ergebnisse kriege.
Und ich möchte Dijkstra-Algorithmus verwenden können.
Das heißt, ich darf keine negativen Kantengewichte definieren durch
diese Schätzfunktion.
Und das nennt man auch Konsistenz bei A-Sternsuche.
Und die Eigenschaft, die man da eigentlich hat, ist die Kosten von E
plus die Schätzfunktion von V muss größer gleich F von U sein.
Man muss das Ganze eine konservative Abschätzung sein.
Das heißt, F von V kleiner gleich µ von V,t.
Und wir wollen eigentlich, dass F von T gleich 0 ist.
Also wenn ich am Ziel bin, dann merke ich auch, dass ich am Ziel bin.
Das ist sicherlich eine sinnvolle Anforderung an meine Schätzfunktion.
Und wenn das so ist, dann kann man tatsächlich auch abbrechen, sobald
man T scannt.
Ich möchte jetzt die Details davon nicht beweisen, weil das ziemlich
viel Symbol-Pushing ist.
Aber worum es mir geht, ist, dass man hier zeigen kann, wie man
mithilfe dieser Knotenpotenziale etwas, was eine sehr unscharf
definierte Heuristik ist, dann in ein beweisbar funktionierendes
Verfahren umwandeln kann.
Und es ist tatsächlich so, dass einige praktische Heuristiken für die
kürzeste Wege suchen.
Die benutzen dann Schätzfunktionen, die nicht immer stimmen.
Und dann passieren auch komische Dinge.
So, was wir jetzt nicht gesagt haben, wie man dieses F von V findet.
Da möchte ich mal ein paar Standarddinger erwähnen und dann eins, das
wirklich funktioniert für Routenplanung und Straßennetzwerke.