Gut, fangen wir an mit der sechsten Übung.
Ich sage euch heute auch noch ein bisschen was zur Klausur.
Aber im Grunde werden wir erstmal so ein paar Beispiele durchrechnen.
Also Sie haben ein paar Algorithmen kennengelernt in der Vorlesung.
Nachher kommt auch nochmal Carsten Sins.
Also wir machen heute noch eine Dreiviertelstunde.
Und danach kommt nochmal der letzte Teil der Vorlesung.
Sie haben den Dijkstra-Algorithmus kennengelernt.
Da rechnen wir mal zusammen ein Beispiel durch, dass man das mal
sieht, wie das aussieht.
Die Datenstrukturen auch.
Bellman-Ford-Algorithmus.
Minimale Spannbäume.
Janik-Prim-Algorithmus.
Kruskal-Algorithmus.
Für beide gibt es ein Beispiel.
Dann machen wir noch einen kleinen Exkurs zu NP-Vollständigen
Problemen.
Das ist einmal die Berechnung von Steinerbäumen und Travelling
Salesmen.
Da habe ich noch zwei, drei Fun Facts dazu.
Und das war es dann schon mit der letzten Übung.
Zur Klausur gibt es zu sagen, ich teile die üblicherweise ein in drei
Teile.
Das ist Teil A, Teil B, Teil C.
Es gibt insgesamt 60 Punkte für die Klausur.
Teil A, Teil B, Teil C.
Auf die gibt es jeweils 20 Punkte.
Auf Teil A gibt es gemischte Kleinaufgaben.
Da sind Wissensaufgaben dabei meistens.
Oder irgendwelche Beweise.
Mastertheorien.
Standard.
Teil B dreht sich mehr um die Algorithmen.
Wenn man sich mit den Algorithmen gut auskennt, und die schnell
ausführen kann, kann man in Teil B ziemlich gut punkten.
Da geht es darum, bekannte Algorithmen aus der Vorlesung auszuführen.
Auf gegebenen Eingabedaten.
Häufig geht es auch darum, interne Zustände der Datenstrukturen
darzustellen.
Auf was man da achten muss, ist, dass häufig, z.B.
bei Graftraversierungen, häufig sind die Ergebnisse nicht eindeutig.
Wenn ich jetzt eine Tiefenzuche mache, dann steigt der eine erst bei
einem Kind ab.
Und der andere steigt bei dem anderen Kind zuerst ab.
Und dann gibt es unterschiedliche Ergebnisse.
Um das Ergebnis eindeutig zu machen, machen wir häufig so Sachen, wie
zusätzliche Teile in der Aufgabenstellung.
Wie beachten Sie die Nummerierung der Knoten beim Abstieg in der
Tiefenzuche?
Das heißt für Sie, dass dann die Knoten irgendwie nummeriert sind und
wenn ich dann Kinder 2, 7, 10 habe, dann besuche ich zuerst das Kind
2, dann 7, dann 10, wenn das dabei steht.
Das Ziel dabei ist eigentlich bei uns, uns die Korrektur zu
erleichtern und das Ergebnis eindeutig zu haben.
Dann guckt der, der ist korrigiert drauf und kann schnell vergleichen.
Genau.
Und das ist aber Teil der Aufgabenstellung.
Das heißt, wenn man das nicht macht, gibt es auch Punktabzüge.
Das wollte ich einmal noch sagen, weil wir heute so ein paar
Algorithmen durchspielen und ich daran denken musste, Mensch, das ist
doch eigentlich sowas wie bei Teil B und es kommt ja auch bald bei
Ihnen dran, Klausur.
Naja, einen Monat haben Sie noch Zeit.
Okay, aber fangen wir jetzt mit der Übung an.
Ich wollte mal einen Dijkstra vormachen.
Was brauchen wir bei Dijkstra?
Wir brauchen ein Array mit Distanzen.
Also für jeden Knoten einen Eintrag mit der aktuellen kürzesten
Distanz zum Startknoten S.
Und wir brauchen eine Prioritätswarteschlange, in der wir die noch zu
besuchenden Knoten reinpacken.
Das ist allerdings keine normale Schlange, also keine First in, Last
out Schlange, sondern eine Prioritätswarteschlange.
Das heißt, die Knoten sind sortiert nach ihrer Distanz zum
Startknoten.
Was würde jetzt passieren, wenn man den Algorithmus auf dem Knoten
starten lassen würde?
Initialisierung sieht so aus.
Wir haben hier unseren Startknoten S, der hat natürlich zu sich selbst
die Distanz 0 und der Startknoten kommt in unsere Queue rein, in die
Prioritätswarteschlange der zu bearbeitenden Knoten.
Dann machen wir eine Breitensuche.
Breitensuche, was sind Kinder von S?
Das sind C, E und H.
Dazu haben wir dann einmal Abstände hier 1, 10 und 20 und genau so
sortiert sind sie dann in unserer Prioritätswarteschlange.
Dann haben wir Knoten S abgearbeitet.
Und dann nehmen wir unseren Nächsten aus der Prioritätswarteschlange
raus, das wäre hier C und schauen uns an, gucken wir uns erstmal an,
bevor ich jetzt weiter drücke, wo wir bei C ankommen.
Von C aus kommen wir wieder zurück nach S und wir kommen nach F.
Nach S hin haben wir jetzt nichts kürzeres, also jetzt irgendwie
Distanz 2 ist jetzt nicht kürzer als 0, aber zu F hin, ja, also hier
gibt es wahrscheinlich jetzt als nächstes eine 8, genau, das wäre
jetzt hier die 1 plus die 7 und dann kommt natürlich F auch in unsere
Prioritätswarteschlange rein, F wird dann hier in der Mitte eingefügt,
weil wir eben, wie gesagt, sortieren.
Dann geht es hier weiter mit E.
Was wären denn jetzt Kinder von E?
Also hier haben wir, hier kommen wir bei F raus als nächstes,
allerdings gibt es hier jetzt keine Relaxierung, also E hat, oder?
Moment, E hat Abstand 3, doch jetzt hier müssen wir relaxieren, genau,
über E aus erreichen wir F nämlich schneller als über den bisherigen
Weg.
Und dann wäre auch F hier der nächste zu besuchende Knoten.
Moment, wo sind wir jetzt gerade?
So, Moment, jetzt sind wir bei F wahrscheinlich, genau, gucken wir uns
Kinder von F an, F wird erreicht in 7, das heißt D wird jetzt erreicht
in 9, genau, D kommt auch nochmal rein in unsere Warteschlange, als
nächstes gucken wir an, was wir von D aus erreichen, hier geht es
weiter zu B und G, das sind hier Kinder in der Breitensuche, F haben
wir schon besucht, da gehen wir nicht weiter, also zurück brauchen wir
nicht laufen.
Jetzt gehen wir hier bei, das wäre der nächste Knoten, B weiter.
Jetzt können Sie alles auch nochmal zu Hause schön sich anschauen, wie
sich quasi die Datenstrukturen auch intern verändern.
Man sieht hier schön quasi auch markiert, wenn eine Kante dazu führt,
dass es nochmal relaxiert wird.
Und wenn wir dann alle Kanten abgearbeitet haben, sind wir fertig und
wir haben jetzt hier dann die kürzesten Wege zu S in unserem Array
stehen.
Das wäre im Prinzip mal ein Beispiel für Dijkstra, kann passieren,
dass sowas in der Art in der Klausur drankommt und einen Algorithmus
irgendwie einmal durchmachen und irgendwie so verschiedene
Zwischenschritte in den Datenstrukturen hinschreiben.
Dijkstra haben Sie auch schon in der Vorlesung gesehen, funktioniert
nicht, wenn wir negative Kreise haben.
Wenn es ein negativer Kreis ist, kann ich ja unendlich im Kreis laufen
und es wird immer weiter relaxiert und relaxiert und relaxiert.
Das heißt, meine Prioritätswarteschlange wird nicht leer und ich finde
immer wieder kürzere Wege, die so Richtung negativ unendlich streben.
Von der Distanz her.
Deswegen oder vielleicht auch, weil der Algorithmus schön ist, haben
wir noch einen anderen Algorithmus für kürzeste Wege kennengelernt,
das ist der Bellman-Ford-Algorithmus.
Da machen wir es uns ganz leicht.
Wir relaxieren einfach für jede Kante n-1 mal alles durch und kennen
dann am Ende die kürzesten Wege.
Den Beweis dazu gab es in der Vorlesung.
Man findet auch raus, wenn es negative Kreise gibt.
Ich zeige auch gleich sogar, wie man die dann auch ablesen kann, die
negativen Kreise, wenn der Algorithmus durchgelaufen ist.
Aber das ganz wichtige am Bellman-Ford-Algorithmus ist, dass der eben
abbricht, wenn er einen negativen Kreis findet.
Ich zeige es nochmal.
Also hier Bellman-Ford auf einem Graphen.
Wir gehen hier n-1 mal durch alle Kanten durch.
n ist hier die Anzahl der Knoten.
Hier für alle Kanten gucken wir, wenn man die Distanz noch mal
relaxieren kann, dann wird es quasi gemacht.
Aber nach n-1 ist es fertig.
Wenn man dann noch mal relaxieren kann, also das ist hier diese Zeile,
also hier gehen wir noch mal alle Kanten durch und gucken, ob man
immer noch relaxieren kann.
Wenn das möglich ist, dann gibt es einen negativen Kreis.
Die Korrektheit, das können wir uns kurz angucken, warum das
funktioniert.
Wenn es keine negativen Kreise gibt, dann gehen wir im Prinzip einmal
komplett durch.
Bei so einer Relaxierung wird ja auch immer von einem Knoten der
kürzeste Pfad durchpropagiert, zu den nächsten, zu den Folgeknoten.
Und wenn wir quasi n-mal durchgehen, dann schaffen wir es quasi über
die längste Anzahl von Knoten komplett einmal den kürzesten Weg durch
zu propagieren.
Das ist so die Idee dabei.
Das wäre im Prinzip der erste Fall.
Und diese negativen Kreise, das ist im Prinzip dann einfach über
diesen Widerspruch, der sich daraus ergibt, dass ich ja eigentlich
schon n-1 mal durch bin und n-1 mal relaxiert habe und dann immer noch
relaxieren kann, das sollte dann eigentlich nicht möglich sein.
Allerdings eben in diesem Fall bei dem negativen Kreis dann schon.
Ich mache es einmal vor.
Also was würde man jetzt tun?
Wir haben uns hier einen Graphen gegeben mit Startknoten S und vier
anderen Knoten.
Das sind insgesamt fünf Knoten, das heißt wir gehen hier jetzt einmal
viermal durch und relaxieren viermal für jede Kante.
Initialisierung wäre jetzt hier wieder alles geht auf Abstand
unendlich, außer S.
Und dann gucken wir mal, ob man relaxieren kann.
Ich habe jetzt hier die, ich hoffe man sieht's, die Kanten blau
gemacht.
Die gerade betrachtet werden.
Gut, also jetzt unendlich plus vier ist wieder unendlich, also hier
kann man auch nichts machen in dem Bereich.
Hier steht alles noch auf unendlich, da passiert nichts.
Aber jetzt hier haben wir eine Kante, an der man relaxieren kann.
Hier haben wir jetzt die zwei, die ist kleiner als unendlich.
Und deswegen können wir hier jetzt ein neues Gewicht eintragen.
Genauso hier unten, hier haben wir eine Kante mit Null.
Auch hier können wir das Gewicht updaten.
So, das war jetzt die erste Runde.
Jetzt sind wir einmal alle Kanten durch und wir sehen, dass wir quasi
hier von S aus einmal relaxieren konnten.
Jetzt gehen wir in die zweite Runde und schauen uns die Sache an.
Unendlich plus vier ist nicht kleiner als zwei, nein.
Zwei minus eins ist nicht kleiner als Null, das heißt hier können wir
auch nicht relaxieren, aber jetzt hier auf diesem Pfad von der Null
also von Knoten C zu Knoten B haben wir auf jeden Fall einen kürzeren
Pfad, der kürzer ist als unendlich.
Hier wird relaxiert.
Genauso, hier nicht, aber genauso hier von C nach D gibt es jetzt
einen kürzeren Pfad.
Genau, das war die zweite Runde.
Ja, die beiden Kanten schauen wir uns dann auch immer mit an nochmal.
Bei der dritten Runde tut sich weniger.
An der Stelle kriegen wir nochmal eine Relaxierung von der minus eins
minus drei auf minus vier runter von D nach B.
Ansonsten bei der Kante tut sich nichts mehr, bei den Kanten tut sich
auch nichts mehr.
Bei der vierten Runde gibt es hier oben nochmal eine Relaxierung.
Hier unten auch nochmal bei Knoten C.
An der Stelle nicht.
Wenn ich von B nach D gehe, hier auch nicht, aber hier von C nach D
habe ich schon wieder relaxiert.
Da vorne um S rum tut sich nichts mehr.
Und jetzt sind wir schon viermal durch.
Jetzt sind wir n-1 mal durch, haben viermal für alle Kanten geguckt,
ob man relaxieren kann.
Das heißt, jetzt sollten wir eigentlich fertig sein.
Jetzt sollte man nicht nochmal relaxieren müssen, weil jetzt auch
wirklich der letzte, kürzeste Weg, die Information über den letzten,
kürzesten Weg durch den ganzen Graphen propagiert wurde, quasi so
schrittweise von Knoten nach Knoten.
Wir waren eigentlich überall schon mal, wir haben uns alles
angeschaut.
So, das heißt, jetzt sollte eigentlich nicht mehr relaxiert werden
können, aber ich weiß es, ich habe es mir schon angesehen vorher.
Hier gibt es einen negativen Kreis.
Wir können hier doch nochmal relaxieren.
Genau.
Wie kann man den negativen Kreis jetzt auslesen?
Es gibt ein ganz einfaches Verfahren.
Jedes Mal, wenn wir relaxieren, merken wir uns, wo wir hergekommen
sind.
Also das wäre hier so ein Parent Array, den wir anlegen.
Und dann können wir rückwärts den negativen Kreis ablaufen.
Also wir schauen im Prinzip bei dem Knoten, wo wir jetzt in der
äußeren Schleife dann nochmal relaxiert haben, gehen wir diesen Parent
Array zurück, bis wir wieder bei dem gleichen Knoten ankommen.
Und das ist dann im Prinzip unser negativer Kreis.
Also hier nochmal der Algorithmus dazu, auf der Folie.
Wie würde das aussehen im Beispiel?
Genau hier ist jetzt so die Entscheidung gefällt worden, dass man mit
Minus unendlich markiert, sozusagen, welche Knoten zum negativen Kreis
gehören.
Also wir haben gesehen, hier haben wir relaxiert, jetzt laufen wir den
Parent Array zurück.
Also indem wir uns abgespeichert haben, dann kommen wir hier zuerst
bei D an, dann bei C, dann bei A, und dann wieder bei B.
Und dann sind wir quasi einmal hier rückwärts gelaufen.
Und wenn wir uns jetzt nochmal die Knotengewichte anschauen, dann
können wir hier
den negativen Kreis auslesen.
Das waren kürzeste Wege-Algorithmen.
Jetzt machen wir noch kurz die MST-Sachen durch und dann machen wir
nochmal zwei Algorithmen zum NP-Vollständigen Problem.
Minimale Spannbäume, auch beliebte Klausuraufgaben, ergeben sich
daraus.
Hier ist ein Graph, verwenden Sie, berechnen Sie den minimalen
Spannbaum, geben Sie diese und jene Zwischenschritte aus.
Sieht man auch in den alten Klausuren, wenn Sie sich die durchschauen.
Da sind immer solche Aufgaben irgendwo versteckt.
Was ist es jetzt mit Janik Prim?
Bei Janik Prim berechnen wir den MST so, dass wir quasi immer
schneiden und schauen, welche Kante auf diesem Schnitt liegt, ist die
kürzeste.
Wir fangen bei so einem Knoten an und schneiden den raus und nehmen
die kürzeste Kante, die diesen Schnitt kreuzt.
Jetzt haben wir hier A rausgeschnitten, durch die Kante, die mit 7,
die mit 9 und die mit 6 beschriftet ist einmal durchgeschnitten und
die kürzeste ist hier 6, also hier zwischen A und C.
Die gehört dann zu unserem minimalen Spannbaum dazu und dann nehme ich
meinen bisherigen minimalen Spannbaum und schneide den raus.
Also dann schneide ich A, C raus und dann habe ich hier Kanten 7, 9, 3
und 4, die ich kreuze und dann würde ich mir hier quasi die mit dem
kleinsten Gewicht nehmen, 3, die gehört jetzt zu dem minimalen
Spannbaum dazu.
So, jetzt habe ich hier 3 Knoten, die ich rausschneide.
Bei diesem Schnitt kreuze ich jetzt hier die Kante zwischen B und E
mit 5, 6, 2, dann hier nochmal eine zwischen A und D mit 9 und eine
zwischen C und D mit 4.
Man sieht es leider bei YouTube nicht, deswegen zähle ich das alles
auf.
Sie haben jetzt hier den Vorteil, Sie sehen den Laserpointer.
Also wir schneiden hier durch.
Für die YouTuber habe ich es nochmal aufgezählt.
B, E, B, D, A, D und C, D.
Kürzeste ist hier 2, dann haben wir einen neuen minimalen Spannbaum
über A, B, C, D und schneiden quasi E und F ab.
Kommt dann hier dazu, die Kante zwischen D und E zum minimalen
Spannbaum hinzuzufügen und dann gucken wir nochmal, wie erreichen wir
F am besten.
Das ist hier mit 3 und dann haben wir unseren minimalen Spannbaum.
Also mit Janik Priem wächst der so, der Spannbaum.
Der hängt dann auch automatisch dabei zusammen.
Bei Großkahl läuft das Ganze ein bisschen anders.
Bei Großkahl nehmen wir uns einfach die Kanten hinher und sortieren
die.
Und bei Großkahl müssen wir außerdem gucken, ob die Kanten jetzt schon
zum gleichen, also wenn ich eine Kante hinzufüge, ob beide Knoten
schon zum Spannbaum gehören oder nicht.
Ich mach's vor.
Wir haben die Kanten sortiert nach Gewicht.
Das heißt, die erste Kante, also die mit dem kleinsten Gewicht, ist
die zwischen D und E.
Die mit dem zweitkleinsten Gewicht ist die Kante zwischen B und E.
Die mit dem drittkleinsten, ja da gibt's zwei, CB und EF und so
weiter.
Und in der Reihenfolge gehen wir durch und dann schauen wir immer,
verbinden wir jetzt irgendwie zwei noch nicht miteinander verbundene
Teilbäume des Grafen oder nicht.
Gibt's dazu noch was zu sagen?
Genau hierzu haben wir eine sehr coole Datenstruktur kennengelernt,
Union Find, mit der das auch effizient zu prüfen ist.
Also da kann man dann schauen, okay, ist der Knoten jetzt hier schon
dabei oder nicht?
Am Anfang hat man quasi lauter so unabhängige Knoten, das sind alle
noch einzeln.
Und dann fangen wir an.
Okay, also D, E sind noch nicht miteinander verbunden, das heißt hier
gibt's dann ein Union auf D und E.
Die stecken danach im gleichen Grafen.
Okay.
Und dann schauen wir uns die nächste Kante an und prüfen, ob B schon
zu D, E dazugehört oder nicht, oder mit D quasi schon verbunden ist.
Das ist nicht der Fall, das heißt da wächst unser Spannbaum noch
fröhlich weiter.
Genauso hier mit Kante B, C und weiter noch mit der nächsten kleinsten
Kante E, F.
Jetzt kommen wir hier zu den Kanten hier unten, die mit Gewicht 4.
Die gehören jetzt nicht dazu, denn wir haben uns in unserer Union-Find
-Datenstruktur gemerkt, dass C und D schon zum gleichen Teilgrafen
dazugehören, der durch den Spannbaum aufgespannt ist und deswegen
werden wir die Kante auf jeden Fall nicht dazu packen, auch die Kante
brauchen wir nicht.
Hier oben geht's weiter mit der Kante mit Gewicht 5, die brauchen wir
auch nicht mehr.
Im Grunde, genau, sind wir fertig.
Warte mal, wann kam jetzt die letzte dazu?
Ah ja, hier.
Die letzte Kante, die dazu kommt, war jetzt hier die zwischen A und C.
Und jetzt haben wir zwar noch schwerere Kanten, also wir haben hier
noch Kante 7, 6 und eine zweite Kante mit Gewicht 6, ja, hier eine mit
Gewicht 9 noch zwischen A und D, die wir noch nicht betrachtet haben.
Allerdings haben wir schon alle Knoten durch unseren MST erreicht,
also können wir frühzeitig abbrechen, müssen wir nicht bis ganz zu
Ende laufen.
Genau, also das waren die zwei Algorithmen, die wir zum MST
kennengelernt haben.
Auch die sollten Sie locker abrufen können.
Steinerbäume Steinerbäume sind so ähnlich wie MSTs, aber ein Ticken
schwieriger und dieser Ticken, also diese kleine Änderung, macht das
ganze Problem NP-vollständig.
Also was machen wir bei Steinerbäumen, wenn wir die berechnen, also zu
einem Graph kann man einen Steinerbaum berechnen, wenn man noch so
eine zusätzliche Knotenmenge gegeben hat.
Also wir wollen quasi eine Art MST, die nur eine Teilmenge der Knoten
besucht.
Allerdings reicht es jetzt nicht zu sagen, okay, ich nehme halt
einfach den Untergraphen, also den knoteninduzierten Teilgraphen.
Wenn ich den knoteninduzierten Teilgraphen nehmen würde, hätte ich
nämlich auch wieder einfach nur ein MST-Problem und dann könnte ich es
wieder in Linearzeit lösen.
Der Ticken, der das ganze schwieriger macht, ist der, dass man die
Umwege über andere Knoten noch mit benutzen kann.
Und das macht das Problem dann kombinatorisch so schwierig, dass es NP
-vollständig ist.
Das heißt, wir kennen keinen effizienten Algorithmus dafür.
Es gibt allerdings Nährungslösungen und da will ich jetzt eine zeigen.
Machen wir erst mal das Beispiel für das Standardproblem, also eben
hier jetzt nochmal an dem Graphen, für den wir eben schon die ganze
Zeit MSTs ausgerechnet haben.
Hier nehmen wir jetzt eine Teilmenge A, B, E, F, das geht hier oben
rechts rum von Knoten und wir wollen jetzt hier den Steinerbaum dazu
berechnen.
Und das wäre jetzt in dem Beispiel der hier, der geht hier über A, B,
D, E nach F.
Das liegt im Grunde daran, hier sieht man noch deutlich, warum man das
nicht machen kann, dass man einfach den Knoten in den Teilgrafen
bildet, denn es könnte sein, dass man quasi einen kürzeren Weg über
einen anderen Knoten findet.
Sprich, die anderen Knoten, die müssen quasi nicht dazugehören, aber
man kann sie benutzen, wenn man die Knoten, die man mit kleinstem
Gewicht verbinden soll, dann mit kleinerem Gewicht erreichen kann.
Also hier quasi der Umweg über D ist 3, schwer, lang oder wie auch
immer, je nachdem, was für ein Problem man gerade abbildet.
Und wenn man direkt von E nach B geht, hat man das Gewicht 5 da
stehen.
So.
Jetzt gibt es hier eine Nährungslösung und die funktioniert ganz gut
auf unserem Beispielgrafen.
Ich zeige dann aber nachher auch noch ein Gegenbeispiel, warum das
nicht im allgemeinen Fall funktioniert.
Für die Nährungslösung gibt es glaube ich nachher sogar Garantien.
Also gucken wir uns das an, was kann man machen.
Man kann im Prinzip Knoten rausnehmen und naja gut, also man kann
einen anderen Grafen bilden.
Ich zeige es am besten am Beispiel, also den Algorithmus können Sie
sich zu Hause nochmal anschauen.
An diesem Beispiel brauche ich ja im Prinzip Knoten A, C, D und F
nicht.
Aber ich kann mir anschauen, ob es da kürzeste Wege zwischen Knoten A,
B, E und F gibt, sodass ich quasi die darüber erreiche, und dann nehme
ich Knoten raus.
Also ich nehme dann halt hier zum Beispiel jetzt diesen Umweg über D,
also von B nach E über D und trage dann hier oben die 3 ein und
schmeiße die 5 raus.
Oder wenn ich jetzt hier zum Beispiel eine neue Kante, die neue Kante
von A nach E steht hier für diesen für diesen Weg genau hier über D.
Also hier 9 plus 1.
Das wäre im Prinzip hier die Distanz, die man von A nach E außerhalb
von diesen Steiner Knoten, die man gegeben hat, nehmen könnte.
Genauso auch hier unten Wo kommt die 13 her?
Von A nach F.
Von A nach F ist der kürzeste Weg 13.
Können wir uns kurz anschauen.
Ja.
Genau.
Hier über B.
Oder über D auch.
Ja, das spielt eigentlich keine Rolle.
Also wenn wir hier D rausnehmen.
Wir haben hier eine 13 und die andere 13 müsste hier auch noch
abgebildet sein.
Genau.
A über B nach F.
Genau.
Und auf dem Graphen können wir jetzt dann einen von unseren
effizienten MST-Algorithmen laufen lassen.
Dann finden wir hier einen MST und lähen den Graphen hinterher wieder
auf.
Sprich, wir schreiben für Kanten, die wir hier modifiziert oder neu
eingetragen haben, tragen wir die ursprünglichen Knoten wieder ein.
Also hier ist jetzt wieder unser D.
Das im Prinzip hier durch diese Kante mit Gewicht 3 substituiert
wurde, ist jetzt hier wieder eingefügt.
Und das funktioniert.
Also wir haben jetzt hier den Steinerbaum, den wir haben wollten für
dieses Beispiel, aber das funktioniert nicht immer.
Man findet relativ leicht ein Gegenbeispiel.
Wenn man sich jetzt hier diesen Graphen anschaut, mit diesem E in der
Mitte und man soll einen Steinerbaum betrachten, der im Prinzip für
Knoten A, B, C und D den Steinerbaum berechnet und E weglässt, dann
kommt man nicht mehr auf den minimalen Steinerbaum.
Der minimale Steinerbaum, der wäre hier mit dem E in der Mitte, der
hätte ein Gewicht von, kurz ausrechnen, 19.
Also wenn man hier einen Baum an E aufhängt und von dort aus die
Blätter besucht, hätte man eigentlich den optimalen Steinerbaum.
Wenn man aber jetzt unseren Nährungsalgorithmus von gerade eben auf
diesem Beispiel laufen lässt und E rausnimmt, dann hat man jetzt hier
Gewicht 10 und 9.
E kommt gar nicht mehr vor und was dann als Steinerbaum oder als MST
für diesen Graphen rauskommt, hätte Gewicht 19.
Das hat auf jeden Fall nichts mit dem Steinerbaum zu tun.
Gewicht 24, habe ich 19 gesagt.
Genau, also hier passt es dann nicht.
Ja, schade, sonst hätten wir jetzt einen effizienten Algorithmus
gehabt.
Für vollständige Probleme war leider nichts.
Genau, man kann Garantien angeben, das beweisen wir nicht.
Der so konstruierte Steinerbaum ist höchstens doppelt so schlecht wie
der richtige.
Also der, den man findet, wenn man dann wirklich das NP-Vollständige
Problem löst.
Genau, noch ein NP-Vollständiges Problem, das in der Vorlesung
drankam.
Ich rede jetzt mal nur halb so schnell.
Carsten Zins kommt ja dann auch noch bald.
In 10 Minuten geht es dann mit der Vorlesung weiter.
Das ist jetzt das letzte Thema, was wir heute haben.
Travelling Salesman Problem.
Genau, was war das?
Also da suchen wir so einen Hamilton-Kreis mit minimalen
Kantengewichten.
Hamilton -Kreis haben wir gesehen, wir besuchen jeden Knoten.
Und im Allgemeinen ist das Travelling Salesman Problem auch NP
-Vollständig, aber wenn wir Zusatzannahmen treffen, wie zum Beispiel
die 3x-Ungleichung, können wir das Ganze effizienter lösen.
3x-Ungleichung sagt nichts anderes, als dass solche komischen Fälle
ausgeschlossen werden, wie dass ich, wenn ich einen Umweg über einen
Knoten nehme, auf einmal einen kürzeren Weg habe, als wenn ich den
direkten Weg gehe.
Da kann vorkommen, die direkte Kante hat irgendwie Gewicht 100, aber
wenn ich irgendwie über 10 andere Kanten, die jeweils nur Gewicht 1
haben, laufe, habe ich einen sehr viel kürzeren Weg.
Solche, naja, je nach Problem macht das vielleicht schon Sinn, aber
eben diesen am Anfang vielleicht unintuitiven Fall schließen wir hier
aus, mit der 3x-Ungleichung.
Also die Abkürzung ist immer eine tatsächliche Abkürzung.
Das wäre hier zum Beispiel nicht erfüllt, hier hat man das Beispiel,
also von B nach E komme ich auf einen direkten Weg mit Gewicht 5 auf
einer Kante, aber der Umweg über D ist eben länger.
Ist kürzer als der direkte Weg.
Was kann ich jetzt machen?
Man kann bei so einem Graphen, in dem die 3x- Ungleichung gilt, über
den minimalen Spannbaum sich Aussagen über die optimale Travelling
Salesman Tour treffen.
Also das Gewicht des minimalen Spannbaums ist sowohl untere als auch
obere Schranke für das Gewicht der Tour des Handlungsreisenden.
Warum ist das so?
Ein bisschen Intuition dazu will ich noch geben.
Wenn man bei der Lösung des Travelling Salesman Problems eine Kante
weglässt, hat man im Prinzip einen minimalen Spannbaum.
Das erklärt hier die untere Schranke.
Spannender wird es jetzt bei der oberen Schranke.
Wenn ich einen minimalen Spannbaum gegeben habe, und der schlimmste
Fall wäre eigentlich, wenn ich das so sternförmig halte und quasi von
diesem zentralen Knoten aus immer vorlaufe und wieder zurücklaufe.
Also jeden Knoten einmal Besuch.
Das kann ich immer machen.
Wenn ich einen beliebigen minimalen Spannbaum habe, laufe ich einmal
in die eine Richtung und dann rechts wieder zurück.
Und habe dann damit einen Rundweg.
Das bedeutet, dass ich dann im Prinzip das doppelte Gewicht meines
minimalen Spannbaums habe.
Und wenn ich jetzt hergehe und dann nochmal Abkürzungen finde, also
sprich direktere Wege, also diesen MST dann so ein bisschen relaxiere,
dann habe ich dadurch, dass die Dreiecksungleichung gilt, die
Garantie, dass die Distanz auf jeden Fall kürzer wird.
Und deswegen kann man das machen.
Also deswegen muss die Dreiecksungleichung gelten und dann hat man da
eine interessantere Ausgangsposition.
Genau.
Das war die letzte Folie.