Approximation Algorithms

Video thumbnail (Frame 0) Video thumbnail (Frame 10457) Video thumbnail (Frame 20720) Video thumbnail (Frame 30983) Video thumbnail (Frame 42594) Video thumbnail (Frame 56312) Video thumbnail (Frame 60224) Video thumbnail (Frame 64884) Video thumbnail (Frame 78971) Video thumbnail (Frame 80957) Video thumbnail (Frame 83021) Video thumbnail (Frame 85914) Video thumbnail (Frame 89947) Video thumbnail (Frame 99432) Video thumbnail (Frame 101637) Video thumbnail (Frame 103514) Video thumbnail (Frame 114401) Video thumbnail (Frame 122902) Video thumbnail (Frame 125449) Video thumbnail (Frame 131219) Video thumbnail (Frame 133391) Video thumbnail (Frame 138342)
Video in TIB AV-Portal: Approximation Algorithms

Formal Metadata

Title
Approximation Algorithms
Title of Series
Part Number
12
Number of Parts
12
Author
License
CC Attribution - ShareAlike 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this license.
Identifiers
Publisher
Release Date
2012
Language
German

Content Metadata

Subject Area
Abstract
Auf Basis analytischer Sachverhalte entwickeln wir algorithmische Ideen für Verfahren auf Graphen. Daraus entstehen zunächst generische Verfahren, welche formal bezüglich ihrer Korrektheit und Laufzeit analysiert werden. Im Anschluss daran werden in jedem Kapitel Techniken zur Verbesserung und Beschleunigung vorgestellt. Abgerundet wird der Stoffplan durch zahlreiche Modellierungs- und Anwendungsbeispiele und der (optionalen) Implementierung eines Benchmarks verschiedener algorithmischer Varianten.
Loading...
Greedy algorithm Euclidean vector Weight Maxima and minima Lösung <Mathematik> Matching (graph theory) Weight Approximation Order of magnitude Physical quantity Connected space Divisor Quantum computer Weight function Proof theory Matching (graph theory) Rounding Inequality (mathematics) 10 (number) Symmetric matrix Function (mathematics) Network topology Physicist Universe (mathematics) Abschätzung Factorization
Kante Greedy algorithm Euclidean vector Weight Decision theory Maxima and minima Moisture Matching (graph theory) Weight Approximation Connected space Mathematics Solution set Divisor Summation Weight function Proof theory Inequality (mathematics) Symmetric matrix Index Logic Function (mathematics) Optimum Factorization Weight function
Kante Plane (geometry) Greatest element Greedy algorithm Euclidean vector Bindung <Stochastik> Weight Covering space Density of states Maxima and minima Matching (graph theory) Approximation Connected space Inclusion map Divisor Vertex (graph theory) Weight function Proof theory Slide rule Square Vertex cover Set (mathematics) Approximation Inequality (mathematics) Symmetric matrix Function (mathematics) Optimum
Kante Trail Stress (mechanics) Complex analysis Graph (mathematics) Weight Ende <Graphentheorie> Total S.A. Approximation Subset Rand Mathematics Plane (geometry) Network topology Complex number Graph (mathematics) Length Algebra Complex analysis Cycle (graph theory) Moment (mathematics) Spanning tree Desire path Set (mathematics) Logic Network topology Theorem Object (grammar) Mathematical optimization Factorization Singuläres Integral
Kante Network topology Network topology Spanning tree Theorem Mittelungsverfahren Length Mathematical optimization Approximation
Hamiltonian (quantum mechanics) Logical constant Graph (mathematics) Direction (geometry) Reflection (mathematics) Total S.A. Approximation Distance Hausdorff space Network topology Logic Travelling salesman problem Network topology Theorem Divisor Mathematical optimization Chain rule Factorization Directed graph Singuläres Integral Proof theory
Kante Hamiltonian (quantum mechanics) Logical constant Graph (mathematics) Approximation Approximation Distance Sample (statistics) Travelling salesman problem Divisor Length Mathematical optimization Factorization Proof theory
Hamiltonian (quantum mechanics) Logical constant Graph (mathematics) Transitive relation Set (mathematics) Approximation Approximation Distance Sample (statistics) Travelling salesman problem Optimum Divisor Length Mathematical optimization Factorization Proof theory
Hamiltonian (quantum mechanics) Logical constant Graph (mathematics) Approximation Approximation Distance Logic Travelling salesman problem Optimum Divisor Mathematical optimization Multiplication Factorization Proof theory
Kante Point (geometry) Norm <Mathematik> Greatest element Metric system Weight Graph (mathematics) Maxima and minima List of anatomical isthmi Mass Equation Approximation Dreiecksungleichung Hausdorff space Mathematics EUKLID <Programm> Summation Length Multiplication Triangle Proof theory Hamiltonian (quantum mechanics) Link (knot theory) Set (mathematics) Transformation (genetics) Axiom Approximation Distance Inequality (mathematics) Travelling salesman problem Network topology Vertex (graph theory) Metric system Matrix (mathematics) Factorization Singuläres Integral
Metric system Graph (mathematics) Maxima and minima Mathematical analysis Approximation Approximation Inequality (mathematics) Spanning tree Network topology Travelling salesman problem Network topology Optimum Divisor Vertex (graph theory) Multiplication Factorization Triangle Proof theory Singuläres Integral
Spanning tree Metric system Graph (mathematics) Maxima and minima Mathematical analysis Equation Approximation Dreiecksungleichung Inequality (mathematics) Spanning tree Network topology Travelling salesman problem Network topology Divisor Vertex (graph theory) Length Mathematical optimization Multiplication Factorization Triangle Proof theory Singuläres Integral
Kante Zahl Metric system Graph (mathematics) Weight Gradient Laufzeit Maxima and minima Mathematical analysis Approximation Inequality (mathematics) Computational complexity theory Mathematics Network topology Travelling salesman problem Network topology Divisor Vertex (graph theory) Summation Quote Multiplication Triangle Proof theory Singuläres Integral
Kante Greatest element Metric system Matching (graph theory) Graph (mathematics) Weight Maxima and minima Approximation Approximation Network topology Travelling salesman problem Network topology Heuristic Vertex (graph theory) Multiplication Singuläres Integral
Metric system Matching (graph theory) Mathematical analysis Approximation Approximation Dreiecksungleichung Network topology Travelling salesman problem Optimum Vertex (graph theory) Length Mathematical optimization Triangle Proof theory Singuläres Integral
Kante Metric system Graph (mathematics) Gradient Spanning tree Maxima and minima Matching (graph theory) Mathematical analysis Weight Equation Approximation Dreiecksungleichung Network topology Index Travelling salesman problem Optimum Vertex (graph theory) Summation Mathematical optimization Maß <Mathematik> Multiplication Triangle Proof theory Singuläres Integral
Kante Metric system Matching (graph theory) Matching (graph theory) Mathematical analysis Inequality (mathematics) Dreiecksungleichung Approximation Network topology Travelling salesman problem Optimum Vertex (graph theory) Summation Mathematical optimization Triangle Proof theory
Polynomial Slide rule Direction (geometry) Approximation
so genau sind die anderen immer so sein dass er verlängert werden an der TU Darmstadt so letzte
Runde heute wir waren stehen geblieben beim Thema nach approximieren Algorithmen wir wir haben haben erst einmal abgesehen alle Markus betrachtet letztes Mal musste leider kurzfristig auf freien weil ich physiologische absolut unfähig gewesen wäre der letzten Mittwoch eine Vorlesung abzuhalten ich bitte um Entschuldigung und das nachzusehen hat allerdings den Vorteil dass wir heute punktgenau am Ende der frühen ankommen so das ist also wenig Sinn macht noch vorne in den Folien wir ausgelassen haben jetzt noch einzelne Punkte auszuwählen und noch die letzte Stunde zu füllen sondern kommen heute genau man Ende der Folie nehmen ist doch schön oder so wünscht man sich das so worum geht es dabei nicht es geht dabei um zunächst mal um algorithmische Problemstellungen wie fast die ganze Zeit in dieser Vorlesung die endlich Wir sind das heißt noch nochmal was ist pragmatisch heißt wir haben jetzt hier nie betrachtet was es theoretisch mathematische heißt man wolle auch heute nicht aber was ist pragmatisch heißt ist wenn Sie eine algorithmische Probleme schon haben die in wer ist zum Beispiel dass die TSB zum Beispiel Steiner Baum zum Beispiel ganz Gelenkprobleme Probleme wir betrachtet haben und und und fast alle Probleme die jenseits der GDI 2 unterkommen bei G 2 passiert Ihnen das nicht dass sie endlich ihre Probleme sehen oder höchstens mal ausnahmsweise aber jenseits davon in der freien Welt der freien Wildbahn draußen sowieso sind fast alle Probleme eine Beschwerde ebenso entgegenkommen was heißt das für jeden Algorithmus denn sie sich auch nur irgendwie ausdenken können egal wie egal auf welcher Plattform auch Quantencomputer Plattform egal was sie werden Eingaben Instanzen Beispiele von moderater Größe finden konstruieren können so dass der Algorithmus denn sicher genommen haben auf diesen Beispielen länger rechnet als das Universum uns ihr zu Verfügung gestellt wenn die Physiker Recht haben zwar ich da dieses Universum so auch das nächste und das übernächste und noch ein paar größere Zehner Größenordnung hoch also eine sehr unerfreuliche Situation aber genau mit dieser Situation haben wir die ganze Zeit in Optimierungsalgorithmen mehr herum gemacht wir haben verschiedene Algorithmen eine Ansätze betrachtet wie man trotzdem heuristisch versuchen kann wenn man schon keine Garantie hat dass man in vernünftiger Zeit die optimale Lösung hat dass man dann also in vernünftiger Zeit wenigstens eine möglichst gute eine sehr gute Lösung hat auch wenn man vielleicht nie weiß wie gut die Lösung am Ende war so und hier bei diesem Abschnitt bei den letzten Abschnitt der Vorlesung haben wir es noch mal mit Algorithmen zu tun also ansetzen zu tun die so ein bisschen in der Mitte sind sie garantieren nicht optimale Lösung mathematisch aber sie garantieren zumindest eine gewisse mit der Garantie wobei diese Güte Garantie dass sehen sehen Sie hier ein Beispiel jetzt nicht so besonders berauschend ist eine typische Sache ist das die kosten die ihre produzierte Lösung hat höchstens doppelt so hoch ist wie die kostenoptimale Lösung es ist nicht so berauschend oder dass der Profit denn Ihrer mit diesem Algorithmus konstruierte Lösung hat mindestens halb so hoch ist wie der Prophet eine einer optimalen Lösung auch nicht sehr berauschend der Punkt dabei ist der Raum das durchaus für die Praxis relevant ist ist und das ist natürlich eine hochgradig konservative Abschätzung sollen Faktor die Lösungen da wenn wir auch dem Beispiel sehen gleich bestellen haben wir die Lösung die man da produziert man kann durchaus hoffen dass diese Lösung sehr sehr viel besser sind als so ein Faktor 2 das heißt also mathematisch kann man etwas beweisen muss aber jetzt nicht gerade berauschend ist aber in der Praxis so wie bei den anderen rheinhessischen ansetzen die wir sonst so betrachtet hatten diese Vorlesung kommt kann man gut hoffen dass da was ordentliches dabei herauskommt so worum geht es jetzt hier noch nochmal hier waren immer wegen der stehen geblieben und noch mal die Problemstellung um die es dabei geht hat wir wir wollen einen Gewichts maximales Mädchen haben also wir haben gegeben eingerichteten Grafen so wurde kann ruhig hier irgendwo müssen ausfransen ja ja gut so ich zeichne den Graf planar weil man eigentlich immer Grafen less than wenn man sie aus der Hand zeichnen das scheint in wieso im im Menschenkopf vor zu sein aber hier das auch noch mal die besondere Bewandtnis dass das Thema mehr Schenk also was Mertsching ist natürlich deutlicher wird klarer wird und zwar deutlich wird wenn ich hier keine Kreuzungen von kann der Zeichnung dran sind so was ein Mertsching ich fange einfach mal hier ich nehme mir diese kann der mehr als Teil des Mädchens vielleicht diese Karte hier dann diese könnte da macht es Sinn diese könnte zu nehmen hier nämlich vielleicht die hier die in die und wenn ich jetzt die mehr nehmen wir dann bin ich am Ende nicht dann kann ich nichts mehr weiter hinzunehmen wenn ich das richtig sehe das ist jetzt ich weiß nicht ob das maximales Matching es wahrscheinlich schon ich habe das sie angesehen ich habe so ein bisschen regelmäßig konstruiert aber wir haben ja schon gesehen das Thema Matching ist Ihnen eigentlich bekannt wir haben Sie gesehen dass der die Algorithmus im Allgemeinen nicht das optimale mitschwingt liefert und wo zumal habe ich habe in dem Beispiel jetzt nach unterschlagen das ist nicht unbedingt um die Kardinalität des Mädchens geht sondern und jeder kann dort noch ein Gericht und was wir wollen ist das Gericht dieser dieses Mädchen zu
maximieren das geht natürlich nicht mehr in dem ich jetzt hier einfach ohne Berücksichtigung der Kanten Gewichte einfach von rechts nach links versuche was wirklich großes hinzukriegen so aber wir haben gesehen der greedy Algorithmus wird im Allgemeinen nicht das Optimum liefern für das Problem hier ein maximal gewichtetes Mertsching also Summe deckt der Gewichte der kannten im Menschen maximiert dafür zu finden sie erinnern sich Mertsching er die Algorithmus kann nur dann ferner Problemstellung garantiert immer das Optimum finden werden diese wenn die wenn die Lösungsmenge Madrid Struktur haben und gesehen bei im Allgemeinen bei den meisten Grafen haben die Mädchens keine Madrid Struktur das heißt also dass man kann immer es keine tritt Struktur ist kann man immer eine Gewichtung definieren bei der Decke des Algorithmus nicht das Optimum liefert die Aussage dieses Lammers hier ist es war schade dass es nicht das Optimum liefert aber immerhin etwas was mindestens halb so schwer ist wie das Optimum also immerhin eine Garantie dass der Lady Algorithmus nicht beliebig schlecht sein kann als dass diese Garantie nicht gebe muss man damit rechnen dass er vielleicht Faktor 100 oder Faktor 1000 schlechter als das Optimum ist aber das ist die die Struktur des Mädchen Problems ist glücklicherweise so das ist dann immer noch eine nur Faktor 2 nur in Anführungszeichen Faktor 2 rauskommt so wie beweisen wer das ist wir gucken uns den Autor des greedy Algorithmus anders ist dieses mit Index APP ich weiß es nicht wo für APP steht derjenige der die Folie gebaut hat weiß dass der Mann an dem man nicht jemand für Application oder so ähnlich Anwendung der Faksimile danke das ich brauche noch ein bisschen Koffein aber Xen aber ist wahrscheinlich der Gedanke dahinter so und dieses vergleichen wir mit einem optimalen mit Schlägen und was Ende daraus bekommen wollen ist das was hier unten noch gerade so auf der Vogel auf die aufgepasst hat das ist das was wir raus bekommen haben dieses ab mindestens halb so gut ist wie ob zu oder andersrum das Ort nicht mehr als zweimal so gut dass wir im aber sehr identisch ist so was wir gucken uns diese beiden jetzt genau an und gucken uns jetzt die Situation an an dieser Folie habe ich ein bisschen geknabbert vor allem an dieser genialen Formulierung soll erst stark Stairway auf die Töne Es sind ätsch und wir wirklich Welt da habe ich lange dran überlegt fast könnte damit gemeint sein ich will also versuchen hier in 2 läutern was diese Folie meint und weil das ein bisschen kompliziert eine Vorbereitung geraten es habe ich mir das mal ausnahmsweise ja selber so'n bisschen zusammengesteckt gespickt so wenn Sie eine Kante haben ich hatte mich in der Terminologie an die Folie wenn Sie eine Kante haben je aus dem aus dem Optimum aus dem optimalen mitschwingt aber das ist und dann kann das auf der linken Seite eine kantige strich geben aus dem APP maximal 1 denn natürlich kann es keine weitere von diesen Knoten ausgehende Kante geben aus diesem ab der was der DDR muss produziert hat und Sie können auf der anderen Seite ich würde mich ein Fragezeichen dahinter weil diese Kante kann da sein muss nicht da sein E 2 comma Element aus ab zu richten ja jede dieser beiden Kanten kann da sein muss aber nicht da sein so was wir jetzt wissen ist aber das ist jetzt auf für im Grunde der der 4. bis vom Tisch dash wir wissen das das Gewicht von strich mindestens so groß ist dass wie das Gericht von E oder dass das Gewicht von E 2 comma mindestens so groß ist wie das Gewicht von E oder beides weil das kann auch sein woher wissen Sie das das folgt daraus dass das für Dingli Algorithmus angewandt haben hier geht jetzt an dieser Stelle geht es allen dass dieses ab erzeugt wurde nicht durch irgend Algorithmus sondern durch den des Algorithmus der wenn diese kannte mehr Gewicht hätte Entscheidungen wenn diese kannte ja schwerer wäre als diese und als diese sofern überhaupt existent jeweils dann hätte der Krieg die Algorithmus weder diese noch diese genommen sondern er hätte die genommen hat er aber nicht sondern er hat diese oder die hier genommen in dem muss natürlich eine kann der die die nicht in beiden drin ist habe ich vergessen zu sagen Werk kannten den beiden und sind machen kein Unterschied kann den beiden Instanzen die kann man vergessen so ist es eigentlich egal die Situation ist völlig symmetrisch das heißt ohne Beschränkung der Allgemeinheit sie kennen das vielleicht aus der Mathematik und WDR denn Sie ohne Beweis der Annahme und in der Gemeinheit und so weiter nehmen wir einfach mal her das WE strich größer gleich wie ist so jetzt auch ich ein bisschen mehr Platz und das bitte noch mal im Prinzip zu zeichnen mit dem etwas
anderen Darstellung und das doch nicht da hinten runter fallen dann ich aufgeschmissen sie sehen dass hier so ein so ein kleiner Schacht ist so na ja das bestimmt einiges drin ja gut wie die so jetzt immer wieder dahin dass noch ein bisschen Feuchtigkeit 2 und wir betrachten noch mal diese beiden also vielleicht alle 3 noch mal alle 3 könnten noch nochmal die ich spreche in 2 comma und die beiden hier die verknüpfen wir miteinander also genau gesagt geht der Fall von Inge Stillig nach E für jeden für jede solche Mädchen kannte er strich er geht der Frage geht der Fall dahin so was haben wir jetzt wir haben verschiedene kannten das brauche ich doch noch mal wissen Platz 4 wir haben auf der einen Seite kannten die mich immer einfach so zeichne Aust ab und auf der einen Seite kann aus im Ort so und diese Verknüpfungen wichtig ist jetzt das jeder Kante in dem Ort maximal mit 2 davon verknüpft ist höchstens 2 ein hat ja wollen sie können Ihre nur links eine und rechts eine Kante haben mehr nicht so und damit haben sie die Korrespondenz mit 2 zu 1 Korrespondenz hergestellt zwischen denn zwischen diesen Kanten und diesen Karten hier und die Kante ist Gründen mindestens so groß jeweils wenn Sie die Verknüpfung haben das war die Voraussetzung hier ohne Beschränkung für ihr strich größer gleich W wenn Sie diese Verknüpfung haben dann ist das Gewicht der kann in ab größer gleich dem Gewicht erkannte in ob das heißt also nein die rum ich muss noch mal ganz kurz das hat schon seinen Grund warum ich mir das so auf notiert hatte genau Schwellung es ist genau falsch falsch rum so um ist die Logik auf der Seite des Ort und auf der Seite des im ab jede Kante in dem Ort jeder kann in dem ab nee wir uns das selbst das habe ich mir so viel Mühe gegeben das Feuer zu überlegen und bin schon wieder hängt kommt jede Kante in ab also ja genau für jede Kante ne so umgeht der vor ihr zur für jede Kante ne nicht mehr diese Sprecher könne die die nicht selber im Mertsching er die nur den Markt aber nicht in dem ab ist nehme ich mir diese kannte die mindestens genauso großes Gewicht hat und abdrehen ist so und wird das jetzt was und und jeder kann der ab kann auf diese Art und Weise nur zweimal verknüpft worden sein einmal links von davon und einmal rechts davon so so rum geht das jetzt das heißt also jede Kante jede kannte im Ort ist mit einer Kantine im ab verknüpft jeder Kalendern ab höchstens zweimal mit ob geht das Herz auf das heißt die Ketten das jetzt werden sie noch mal in genau wie einmal wir wollen zu dieser Korrespondenz hier unten hin und die haben ein prinzipiell schon weil hier 2 2 fällt das 2 zu 1 ist jede Kante hier entspricht hier eine Kanzel genau maximal 2 kann hier von der jeweils entspricht eine Karte hier diese Karte ist größer gleich jeder dieser beiden kannten das was wir am Verhältnis von von maximal 2 zu 1 in jeder einzelnen dieser Teil Bilderrahmen Verhältnis von maximal 2 zu 1 und damit habe insgesamt ein Verhältnis von maximal 2 zu 1 also ich hoffe ich konnte Ihnen das jetzt besser nahe bringen als als man dass die Folie selber nahe gebracht hat mit diesem schönen Formulierung wird erst Charge der Welt ICF ist schade musst also ich hoffe dass es damit jetzt deutlicher geworden okay nächste
Problemstellungen kann Minimum Bereska warum geht es hier hatten wir kurz angesprochen beim letzten Mal aber da wir jetzt nicht in Zeitdruck Bindungen sind will ich das noch mal kurz ansprechen was die Problemstellung ist für sie haben wieder einen ungerichteten Grafen das macht wiedersehen er ist normal ist in den USA zu zeichnen aber mal wieder Planer zu zeichnen um den Überblick besser behalten zu können schon so mal keine kommen könnten so zum Beispiel so könnte das aussehen es also das reicht mir jetzt so was ist eine möglichst klar war dass es eine Menge von Knoten die alle kannten überdeckt also es erscheinen erst mal so der Draufsicht plausibel diesen Knoten her zunehmende überdeckt schon mal diese ganzen kann hier dann nämlich mal diesen Knoten her der bedeckt dann diese ganzen kannten der Herr vielleicht der hier das von warum kann nicht überdeckt nämlich den hier dazu hier ich glaube ich habe ich nicht besonders klug eingestellt es muss ich und den nämlichen die nämlich nicht sonderlich nehmen denn wir dazu und den hier wahrscheinlich sind schon jetzt weit weg von optimal die wenn hier vielleicht in ich vergesse dass man mit Optimalität ich sogar von oder für Dosen zulässige Lösung wird wir haben noch was vergessen ja diese kann das noch nicht diese könnte auch noch nicht dann hier Hamas jetzt sind alle Kanten durch Knut überdeckt nee da unten ist noch ein Problem und dann sie immer noch eine Kante nicht überdeckt so Hamas ich glaube es war nur so oder ich sehe jetzt keine Karte mehr die nicht der 10. zu einem entknoten den ich jetzt zunehmend zu einem Quadrat gemacht haben da ist noch alles okay gut danach was es hoffentlich endlich so noch was vergessen aber da ist noch eine richtig also Sie sehen so würde es gar wird schon ziemlich groß auch wenn man es optimiert so wir wollen ein wird ist klar haben was minimale Anzahl Knoten enthält das eigentliche das Problem wie sich das bei uns gehen vorlesen gehört wie gehen wir vor approximieren es wenn jemand und ein maximales Mertsching gemeint damit ist ein Inklusions uns maximales also dass man nicht mehr weiter vergrößern kann da also wo man keine weitere kannte man zunehmen kann es muss es nicht die Karte Inhalt maximales Mädchen seiner Sauce und muss nicht unbedingt eine ein eine maximale Anzahl von Kanten enthalten außer technische Sache ist weil wir können einfach eine kann alle kannten durchgehen in der Reihenfolge der Familie eine Menge an und immer dann wenn eine Kante wenn der eine kann der betrachten wenn die die Menschen Eigenschaft das stören würde weil einer der beiden entknoten schon mit einer Mitsching kannte verbunden ist das vergessen dir und ansonsten fügen Sie ein comma so sehr schnell zu einem solchen maximalen entstehen so und überhaupt und dann immer von diesem Match in dem wir die einen Knoten alle entknoten fest beider von jeder kannte die mitten drin ist und die Behauptung ist dass das nur 2 Approximation für wird ist kann man liefert warum na ja zunächst einmal ist das ein würdigst wenn wir das so machen weil wir das mit maximal ist wenn es keine wird es gewohnt mehr wenn es also eine Kante gelber die nicht von A 1 Knoten einer Mädchengang überdeckt wäre dann könnte man diese kann natürlich zu Menschen Herrn im Widerspruch dazu dass wir maximales Mitsching gewählt haben also ist das was wir so pro konstruiert haben tatsächlich ein würde es Carver das hat natürlich wir wissen genau die Anzahl der Knoten in diesem speziellen wird ist klar war dass sie konstruiert haben nämlich zweimal Anzahl der Mädchen könnten weil wir ja jeden entlohnt einer Menschen kann gewählt haben eingenommen haben so waren es aber auf der einen Seite klar dass ein weites Kar war mindestens Anzahl Mertsching kannten viele Knoten haben muss denn 1 für jede Kante muss einer der beiden in würdest geworden seien also für die Menschen kannte und es ist nicht möglich dass ein Knoten 2 Mädchen kann überdeckt bei den wären diese beiden Mädchen kann er in sie denn zum selben gewohnten Widerspruch zur Definition von Mirtschink und damit bekommen wir diese 1 zu 2 Korrespondent schon hin die Größe des Mertsching ist mindestens so groß muss das Optimum auf der einen Seite ist das was wir konstruiert haben also also hier dieser parkte melde genau zweimal Anzahl der Mitsching so wie wir festgestellt haben muss das Optimum mindestens genauso groß sein wie die Anzahl der Mädchen kannten und damit haben es hingekriegt also eine einfache Sache comma
noch zum dritten vielleicht interessanteren Beispiel Steiner bei sie kennen den Stein aber Problem wir hatten das schon ich jetzt einmal ganz kurz wiederholen hier sehen Sie ein einfach strukturiertes schön übersichtlich es Beispiele Gittertürchen stellvertretend für welche Beispiele die Millionen Knoten groß sind und nicht mehr so viel schön übersichtlich planbar sind und alles so was die Problemstellung Sie haben eben einen ungerichteten Grafen mit Kanten gewichten jede kann da hat ein Gewicht und Sie haben noch zusätzlich eine Auswahl von Knoten drin dass ich hier A B C D in diesem Beispiel das sind die terminale also der Termin erzählt der Menge von Terminal die Menge K ist besteht aus den Knoten A B C D und was sie wollen ist jetzt kein spannender bauen der im Grafen alle Knoten auf man dieses von muss banyantree Problem meckern sondern einen Baum in diesen Grafen der speziellen nur die Knoten B D aufspannt dieser kleine Unterschied nochmal zur Änderung dieser kleine Unterschied dass wir nicht minimal spannende Bäume alle ein nicht einen einen einen minimalen Baum haben wollen den Grafen der alle Knoten auf sondern nur eine Auswahl dieser kleine Unterschied sorge dafür dass die Problemstellung nicht mehr Napoli Nummer nicht mehr effizient lösbar ist wie sonstige die 2 mit Primo Kunstwerken haben sondern es ist in der schwer warum ist die Problemstellung SEG-2 minimal spannen wollen mehr leicht lösbar habe gesehen wie Algorithmus hat Madrid Struktur ich hier diese wenn sie wenn sie weg gehen von der Forderung dass alle Knoten aufgespannt das unsere sondern wenn sie sagen eine zu Beginn der Teilmenge wie hier so aufgespannt werden ist da keinen Kopf ruhig Struktur mehr das heißt also der wie Algorithmus Grüß Gott Rhythmus wird nicht mehr funktionieren und alle anderen funktionieren auch nicht mehr so gut da weil das Problem dann gleich in die schwer geworden ist so was machen wir wir verdichten die Problemstellung also das hier links ist ist die aus ganz Problemstellung das einzige was weggelassen wurde in diesem Bild sind die Karten Richter sind es auch nicht so beziehungsweise in diesem Beispiel das sehen Sie wenn Sie hier rüber gehen in diesem Beispiel sind die kann Gerichte eine 1 das heißt also die Länge eines Weges sie uns kannten in diesen Weg nur zu vereinfachen damit dass das Problem immer noch in der schwer wenn sie es reduzieren auf werde auf kann Gewicht 1 das ich bei jeder Problemstellung so zum Beispiel wenn sie es dies beim TSB alle kann Gewicht eines nehmen wir sie runter optimal das heißt dass die SPD ist nicht mehr in der schwer wenn eine kein Gewicht eines haben hier ist es aber so auch wenn sie alle kann Gewicht eines haben bleibt das Problem noch endlich mehr ärgerlicherweise außersinnlicher weil sich mal so sehr Leute wie wie und vielleicht auch sie arbeitslos wenn das alles so einfach wäre also was machen wir Wir für Dich das ganze wir gucken uns nur die Termine an und den vollständigen Grafen darauf wies der gebildet wir nehmen uns jeweils den kürzesten Weg zum Beispiel von A nach B der hier oder der 3 kannten das heißt also hier in dieser Verdichtung hat die Kanzel zwischen A und B die Länge 3 zwischen C und D der kürzeste Wege so oder so rum hat länger 2 das heißt die Kante zwischen C und D auf der rechten Seite hat länger 2 und so weiter hier vielleicht noch von A nach C die kürzeste Weg länger wussten die lang 1 2 3 4 also die kürzeste Weglänge zwischen A und C ist das aber die Kante von A nach C hier auch den Gefieder dieser Graf ist beste ist übrigens Plan aber auch wenn das jetzt hier nicht so aussieht er lässt sich durch aus alten mit geraden Linien kreuzungsfrei man muss einfach die Knoten bisschen anders platzieren das übrigens nur mal so am Rande erwähnt eine generelle Eigenschaft die man mit der an einer alles ist der komplexen Zahlen beweisen kann jeden Grafen den sie so mit krummen Kanten wie hier in die eben einbetten können kreuzungsfreie können Sie auch mit geraden Kanten irgendwie anders kreuzungsfrei einbetten falls Sie da mehr dazu interessiert über die Hintergründe müssen Sinne Mathematik Vorlesung über Funktionentheorie über komplexe Funktion die an nur so am Rande so also weißer kann verwirklicht besser dafür für Vorlesungen als schwarze Kleidung ansonsten so Rotwein Spaghetti Sauce oder ähnliches schwarz natürlich perfekt so was machen wir hier drin in diesen Grafen berechnen wir jetzt einen Kürze eine minimale Spannung bauen das sage ich jetzt einfach mal das ist der da wir den roten kannten so so was machen wir mit diesen Schweinen Baum so auch jetzt wieder das Bild wenn spannen bauen das ist der verdichtete Graf die 3 Kanten sind der Spree sind die kann spannenden Baums für 7 auf der Folie hatten diese setzen wir jetzt wieder dieses kannten ersetzen wir wirklich die ursprünglichen Pfade wenn wir das machen konnte aber ein bisschen Kraut und Rüben aus können kann sein je nachdem wie diese fade gezogen waren können da zum Beispiel in dem bewegenden wenn wir jede keine wieder dich züchtigen entsprechen Christen Fahrt ersetzen können der Zügel draus wird kann der Züge drin gewesen sein die Kammer natürlich aufbrechen weil wir wollen Steiner Baum haben das heißt also was Züge frei ist immer die schwerste kann daraus Hamas Züge freies und es kann immer noch sein wenn wir es kannten ausgenommen haben ich mache das mal vielleicht das einem Beispiel damit das klar wird vor nach Helga und so versuchen ein Beispiel dafür zu basteln könnte sowas aus sehen ja mehr zum Beispiel so Sie haben einen Knoten A wir haben einen kürzesten Weg irgendwie durch den Grafen durch zu einem B und den anderen kürzesten Weg so durch den Grafen durch nach C ja kann ja passieren möchte sehe dass die dass dieser kürzeste Weg so aussieht und dieser Cosovic sieht so aus und die beiden nochmal kann gemeinsam wenn diese beiden kürzesten Wege jetzt in dieser Lösung drin sind weil diese beiden sprechen kann A B und A C in diesen fertig den Grafen in dem Wunsch dass bei den Privaten dann produzieren sie natürlich jeder genau dieses Bild genau einen Züge die und was sie vor sagt ist dann nehmen sie erst mal irgendwo die die keine größten Richter und schmeißen sie raus kein Problem jetzt haben sie aber noch plötzlich hier so freihängende Enden dies natürlich daran erkennt dass der gerade eines solchen Plotins eines ist genau eine kann denn sie denn das können sich aber mit in den Klo im Club mit zählen wie viele kann man sie denn sind und solange das passiert so das der Fall ist schmeißen sie schrittweise und haben dann am Ende tatsächlich wir bauen eine Baumstruktur nur auf diesen Termin ein das ist das was hier mit diesen beiden spiele er Punkt B und Punkt C gemeint ist und Sie sehen was ich vorhin schon mal anfangs gesagt habe auch wenn die Garantie zu der gleich kommen nur Faktor 2 ist ist die Lösung die hier in diesem Beispiel produziert wurde doch deutlich besser fällt 7 zu 6 Std was will man mehr so und wie ist die
Garantie erst einmal was ist die noch mal das ist die Behauptung die Behauptung ist dass der Algorithmus ich ihn ins geziert habe vollständigen Grafen hernehmen auf dem Terminal 1 mit Kanten gewichten gleich kürzeste Wege also kurze Wege allgemein nach den Gerichten nur ein Beispiel waren sehr was man für die Ansage kannten dann da in einem minimal spannen bauen den übersetzten wieder zurück in vor die Kantine wählen Faden Ursprungs Grafen zurückübersetzen und unnötige kannten wie wieder in dieser Zeichnung wieder rausschmeißen das ist der Grund dass der Probe der Topos Alge würden die Behauptung ist dass das ein Nische S Markus wir das offensichtliche Steiner bauen uns die worden ist dass er höchstens zweimal so lang ist wie der optimale stellen aber um und die Beweise das das beweisen er dadurch dass wir sagen dass wir und diese Steiner Baum haben spielen dass Sie diese Steiner Baum denn am Ende viel konstruiert haben endlich gar nicht weiter betrachten was wir betrachten sind 2 Objekte das eine ist und wir betrachten auch nicht mal den spannenden Baum der die wir konstruiert haben in diesem verdichtet Netzwerk selbst dem betrachten wenn nicht was wir betrachten ist folgendes wir betrachten irgendeinen uns nicht bekannt den optimalen Steiner Baum und diese Baumes planbar ein es immer kleiner denken Sie meine eben ein Zeichen dass es nicht in diesem Beispiel so sondern das ist immer so das heißt sie klingt immer so ein Bild her wie hier sie nehmen sich den optimalen Steiner Baum und zeichnen den sozusagen nochmal hier so in die Ebene daneben wie hier tragen ab wie lange lernen sind dieser einzelnen Wege hier einmal so rum und von A nach B von B nach C von 10 und von den nach wieder zurück und kleinen Moment muss ich noch mal überlegen wie jetzt die Logik ist
werden das ist jetzt ein spannender Baum denn das ist das erst mal noch der schönen der Spiele der Steiner Baum
Grafen der hier muss Grafen den habe ich hier noch mal der hier noch mal zur Seite gezeichnet und die Christen Weg liegen nur eingezeichnet im Uhrzeigersinn im Gegenuhrzeigersinn einmal rund um und wenn ich jetzt als spannen Baum her nehmen wir einfach den Pfad von A nach B von B nach C und von C nach D dann hat dieser dann habe ich jede einzelne kann auf den Steiner Baum jetzt als ich okay ich nehme hier in diesem Beispiel als spannen Baum eben fertig den Grafen her die keine von A nach B B nach C C nach D das ist immer das das Prinzip ich habe die ich habe den Baum kleiner eingebettet und ich gehe einfach mal im Uhrzeigersinn folgen wo starten um A nach B ist eine Kante Spannung Baums den ich konstruiere B nach C und C nach D und damit habe ich jede einzelne kannte Steiner Baums höchstens zweimal gezählt wenn ich zum Beispiel die kann hier von diesen von diesem Mittel pro ermittelt Knoten nach B habe ich einmal gezählt in der kann den kürzesten Weg von A nach B und einmal in Weg von B nach C das heißt dieser spannende Baum würdigte den Grafen der aus den Kanten A B B C und steht hat höchstens doppelt so viel Gewicht wie der ursprüngliche Steiner Baum weil ich bei der Konstruktion der kann dann würde ich den Grafen jede die ursprüngliche kann Steiner Baums nur maximal zweimal gezählt habe einem etwa hier diese könnten einmal kommt sie kannte A B und eine Kanne bitte sehr so wenn es jetzt also einen spannenden Baum geht dessen Gesang im verdichteten Grafen dessen Gesamtlänge höchstens zweimal so groß ist wie die Länge des optimal Schleier uns im ursprünglichen Grafen dann heißt es auch der von uns konstruierte minimale spannender und für den ist natürlich erst recht ja wir haben von irgendeine einen Wesen von einer optimalen Lösung des Stein aber wo ausgegangen haben daraus eine minimal spannen Baum konstruiert im verdichteten Grafen nein ein nicht einigen Beispielen haben aus einen spannenden Baum konstruiert dessen Gesamtlänge höchstens zweimal so groß ist wie die Gesamtlänge das optimal Stein aber uns und das was wir Herr genommen haben der minimale Steiner bei die minimale Spanne bauen das ist natürlich höchstens besser und das was wir aus dem minimalen
sparen sondern dann gemacht haben bei der Transformation da haben nur noch kannten rausgeschmissen kann auch nur noch besser werden
in dieser Gesamt Kette von Argumentationen ergibt sich dann dass das was wir gemacht haben als er geben Steiner Baum höchstens zweimal so so großes Gewicht hat wieder Stadt brauche ist dass Entwickler geworden oder soll ich mal die Kette wiederholen also wenn sie mit dem nehmen man kopfschüttel heißt es ist ist nicht klar geworden oder heißt es sich so nicht wiederholen also wer möchte sich also noch mal versuchen zu rekapitulieren gut können sich ja dann noch mal zu Hause anhören oder anschauen gut und damit
habe dieses Beispiel und jetzt comma zum letzten Beispiel TSP Sie kennen das Damentennis P hat alles begonnen wird auch alles hier aufhören zunächst einmal ein Beispiel dafür dass es auch negative Resultate zum Thema approximieren gibt dass man beweisen kann für manche Problemstellung dass sie überhaupt nicht gut ab ob sie mir war sind generell nicht und zwar ich muss hier vielleicht der kleine der kleine Schlenker machen steht so was Komisches Pii kurz NPD ich habe mir ganze Zeit gesprochen von den endlich wieder ein Problem ich habe ihn immer heute noch mal gesagt was es pragmatisch heißt nämlich dass es keinen sagen wir mal so dass es keinen ordentlichen Algorithmus gibt der die Problemstellung exakt da ist eine kleine mathematische Feinheit drin die immer mit 1 P Grills n ausgedrückt wird es gibt 2 Mengen von Problemstellungen die bos abschätzbarer Algorithmen gibt und die wo es nicht der dem Esstisch so fällt basierte Polen mehr abschätzbar Algorithmen gibt Pfalz P ungleich NPD ist gilt das was ich gesagt habe mit den schwer ab so mit denen nicht vernünftig lösbaren Problemen uneingeschränkt auch theoretisch falls B gleich NP ist geht es theoretisch nicht mehr aber praktische pragmatisches ist das was ich gesagt habe immer noch richtig ja das nur als kleiner flinker nebenbei ist natürlich nicht prüfe also eines Spiegels NPI diese dieser dieser kleiner ein führender Halbsatz das ist nicht unser Land also er es bewusst was das englische Wort alles sagt können Sie anders alles heißt falls nicht es gibt 2 Wörter dieser Art an im englischen falls nicht nicht und lässt LSD können Sie das damit nicht das finden Sie zum Beispiel in Formulierungen lässt die vor Gerd damit wir nicht vergessen pathetischen Situation gut an das heißt falls nicht aber wie gesagt dieses eines gebe NP ist nicht prüfungsrelevant jedenfalls nicht in dieser Vorlesung hier ja so dieser Satz sagt für keinen also wieder für Faktor 2 wie bisher noch für irgendeinen fragt auch nicht verfolgte Tausende für 1 Million können wir ein Algorithmus bauen der er der wenigstens garantiert dass die Lösung höchstens eine Million also mindestens oder und man höchstens eine Million mal schlechter ist als die optimale Lösung wir können keine also so bauen wir den wir garantieren können dass die dass die Lösung höchstens eine Million mal schlechter als die optimale Lösung ist oder eine Milliarde oder eine Billion setzen Sie ein was sie wollen nicht so toll ich sollte sich der nicht Abdunkelung längst Plenum so so wie beweist man das durch Widerspruch nämlich wenn 1 gibt so Algorithmus und zeigen wenn es den gibt dann gibt es da dann können wir ein anderes endlich wieder das Problem ob er tatsächlich lesen was aber nicht geht das ist die Logik also ein bisschen gewöhnungsbedürftig so müssen von hinten durch die Brust ins Auge aber ich glaube man kann sich dran gewöhnen wir beweisen dass es keinen Algorithmus mit der Eigenschaft gibt weil wir beweisen dann müsste es auch einen Algorithmus für Problemstellung geben die den die diese Problem exakt löst und da diese Problem Jungendlicher ist geht das nicht so was ist hämmert und ins Werke das ist fast so sehr wie die SPD so das reicht es oder ich bin schon wieder dabei sämtliche Kreide immer hierher zu bringen immer wieder zurückbringen Herr mit Tonnen zurückkehrt ist im Prinzip die wie sie am ungerichteten Grafen ist in gewisser Weise die ungerechte die die ungesichtete Version vom so und sie stellen sich die Frage wenn die und durch den Grafen hat der eine Rundtour überhaupt ja und die SPD haben den vollständigen Grafen und da ist natürlich immer noch und wollte den zu können einfach in beliebiger Reihenfolge sämtliche Punkte besuchen wenn Sie jetzt beliebigen durch den Grafen hernehmen das ist die Frage ob der wirklich Grund oder wenn es oder nicht erst einmal nicht so ohne weiteres ersichtlich ist ich kann wie in anderes Beispiel nehmen zum Beispiel so hier dieses Beispiel hat offensichtlich keine Rundtour weil sie müssten dann zweimal diese kantige hier durchlaufen und diese beiden Knoten aber der hier hat offensichtlich die Rundtour Sie gehen einfach einmal außen rum und über die Frage ob und gerichteter Graph eine solche unter Art das ist ein solches solchen mit dem Kreis wenn man den Hermogens werkelt dies wieder in welcher dumm gelaufen so also wir nehmen an es gibt ein Algorithmus für das die SPD für einen gewissen Faktor egal ob Faktor 2 oder Faktor 2 Millionen oder Faktor 2 Billionen das ist vollkommen egal für um den Faktor K kann der Lösung konstruieren von den Gemahl damals beweisen können das sie nur um diesen Faktor K schlechter sind als die optimale Lösung zurück in dem man so ein Algorithmus gibt es denken Sie sich vielleicht immer Faktor 2 so wie wir das eben hatten es vielleicht am Ende zwar tiefsten so oh jetzt nehmen und jetzt gucken wir uns das das dieses Vermögen Kreis Problem an und für ihr für für Sohn Import Grafen weißen Kreis Problemen konstruieren wir eine eine Instanz ist die SPD mit bestimmten das Tanzen nämlich wir haben dieselben Knoten wie diese aus ganz Graf und haben bestimmte kann man nämlich die Kantenlänge 1 falls diese kannte schon im aus ganz klaren drin ist und beim TSB Vorschlägen Grafen als die kann jetzt zusätzlich reinkommt und ist jetzt und außen TSB Instanz zu machen setzen wir diesen wer diesen komisch steht definierten da drauf wieso der so aussieht wenn wir gleich sehen weil es natürlich dann wieder Richtung genau aufgeht ja also abhängig von diesen K Faktor Faktor 2 zum Beispiel setzen wir die Gerichte entsprechend so was
passiert jetzt wir nehmen an es gibt so ein
Algorithmus die SPD mit der der an den Faktor von K Approximation garantiert denn wenn wir auf
diese so konstruierte Instanz ist TSB an und es gibt 2 Möglichkeiten entweder liefert der Algorithmus eine Tour der Länge n was heißt
das das heißt dass er nur kannten aus dem Ursprungs Grafen hat eine Rundtour mit Carlos muss treffen das heißt der Ursprungs traf hat eine Rundtour das hätte der kann sie nicht gefunden ja von den kann man
hier bei der Länge n findet wir müssen alle einzelnen kann die in der Rundtour Länge eines gehabt haben das heißt sie müssen alle eine kann sowohl vom traf gewesen sei dieser Welt die und ist natürlich größer als 1 das heißt also für die gesamte GN es kann keine einzige dieser kann unten dieser zusätzlichen kannten verwendet worden seien so
ansonsten wenn das nicht der Fall ist wenn ich länger hat hat er mindestens eine von den
unteren Kanten hier das heißt er kann höchstens N minus 1 x Kantenlänge 1 gehabt haben und muss mindestens einmal diese Größe kann gehabt haben und das finden Sie
hier muss mindestens N minus 1 x also höchstens N minus 1 x Länge eines gehabt haben und mindestens einmal diese größere Länge was sie so aus so so können Sie die Klammer sodass sie so vereinfachen können so K 1 plus 1 so was passiert hier ab der also mindestens so hoch heißt es dass das Ergebnis der das approximieren ergibt das mindestens keine bloß 1 Menge hat hat aber höchstens Länge K mal Optimum weil hier geht es ein
Widerspruchs Annahme wir haben einen Algorithmus der einen Faktor von K Approximation garantiert das
geht hier in diese zweite ungleichen mit ein also dort geht sie ein so das das bedeutet aber wenn Sie diese bei wenn Sie hier die Transitivität hernehmen bedeutet das zwangsläufig das ob ich größer in sein muss K 1 plus 1 kleine gleich kann man ob er zwingt das ob größer ist Optimum größer ist ein Optimum größer N
ist heißt das es kann keine Lösung geben keine Rundtour geben die nur Kantenlänge 1 hat weil die optimale Lösung das schon ich hat und das heißt ist es gibt keine Rundtour es gibt keine mit dem Kreis es vielleicht
ein bisschen komische Logik wenn man daran nicht gewöhnt ist was haben wir was haben Sie gemacht wir leben und wir wir gehen davon aus wir haben eine Rundtour nein wir haben ein Algorithmus fürs TSB der eine Approximation um Faktor K K beliebig aber fest garantiert wir sehen uns eine Instanz her ein ungerichteten Grafen und basteln daraus eine Instanz ist die SPD und kriegen 2 verschiedene Fälle raus entweder ist das was der unser Algorithmus angenommen Algorithmus konstruiert so groß oder es ist gleich so groß und dann so groß ist der gibt es einen mit dem Kreis eine Rundtour in den Ursprungs Grafen wenn es stattdessen gleich so groß ist gibt es denn nicht weil das Optimum auch mindestens größer sein muss und das heißt also aus dem Ergebniss unseres angenommen fiktiven Algorithmus für TSB können wir ablesen ob es im Ursprungs Grafen einher mit dem Preis gegeben hat oder nicht wenn ich aus dem Wert denn in denn die Lösung hatte dieser Algorithmus liefert das ist die Logik und da dieses mit dem Kreis endlich wer ist kann es keinen Algorithmus geben bei dem wir das aus den Werten ablesen können Tristesse das ist mir etwas gewöhnungsbedürftige aber eigentlich doch recht interessante Logik oder so das ist die schlechte Nachricht und die SPD
gute Nachricht ist er dass es für das metrische TSP für den Spezialfall mich die SPD doch gute Approximation gibt sogar besser als Faktor 2 worum geht es da in den allermeisten für Anwendungen vom TSB wenden wir müssen die ein Geometrische Anwendungen den geografische Anwendung oder ähnliches haben Sie die Dreiecksungleichung ja Sie haben 3 wenn sie 3 Kanten haben beliebige 3 Kranken period die ein Dreieck bilden mit X y z dann ich mache das mal andersrum so Uhrzeit und jetzt y dann ist die Länge dieser kannte hier nicht größer als die Summe der anderen beiden könnten sie indes aus der Mathematik der Beruf Metrik vertraut eine Metrik euklidische Metrik sehr vertraut also das mitreden Distanz Maße und deren konstituierendes Axiomen deren wichtigstes Axiom ist die ist die 3 zum Gleichung der hinzukommt noch arg als Axiom das ist symmetrisch also die Distanzen Einrichtung des gleich das Tanzen an und ein 2. Satzung kommt hinzu dass also eines Bundes ich selber 0 ist aber das konstituierende ist sie Dreiecksungleichung also Normen Metriken so sie noch vertraut aus der Mathematik oder und bin ich aber so das selbst in diese Einschränkung gesprochen jetzt nicht weiter hier zu verfolgen also dieser Beweis hier unten ist nicht Prüfungsverband oder Beweis ist einfach diese Andeutung wie man vorweisen kann ist nicht prüfungsrelevant selbst diese Einschränkung auf den Fall dass die Dreiecksungleichung gilt im Allgemeinen muss sind SP nicht gelten weil die kann man ja beliebig sein können aber in der Einschränkung dass die kann man die Dreiecksungleichung erfüllen ist dass die SPD immer noch endlich werden aber
besser approximiert als der ganz allgemeine Fall hier ist sehe die 1. einfach Approximation es Technik die Faktor 2 wieder liefert wir werden danach noch einen Faktor 3 halbe also nur 50 Prozent Fehler dann kennen lernen also wie gehen wir vor also was wir dich hier diesen hier kann man das lesen das ist der ist der BUanz der Token das lesen okay gut was hinter steht es eine Instanz ist der SPD mittels der SPD gegeben durch die Punkte hier und deren deutliche Distanz er das 1. was wir machen ist wir nehmen uns diese Instanz diese Eingabe diese Menge von 10 Punkten und bauen darauf eine Minimums banyantree und der sich dann in diesem Beispiel so aus ich gehe mal davon aus dass das wirklich hier ein minimal Spanner Baum konstruiert wurde ist wieder sehr stark danach aus so 1. Schritt minimal spannen Baum aufgebaut 2. Schritt passiert ist nicht allzu viel erst einmal eine Verdoppelung jeder kannte ja gut 3. Schritt ist dass es hier so eingequetscht 1 1 Eulersche schon weg ich weiß sie nicht ob ihn das vertraut ist kann sie das Königsberger Problem also wir das ich kenne schaut es einfach mal nach der Google Königsberger Brücken Problem oder so ähnlich und Bernhard Euler damit finden sie es ganz schnell ist jetzt für uns ist nicht weiter relevant hat ist hat er historische Bedeutung als als jetzt methodische so das heißt also einen solchen Weg durchläuft jeder einzelne kannte genau einmal das hier ist ein Beispiel wie man wie man jede Kante genau einmal durchlaufen kann um kommt natürlich dann wenn man da wieder raus von von 1 nach 2 von 203 von 3 wieder zurück nach 2 von 2 nach 4 von 4 6 von 6 nach 5 geht es hier lang von 5 nach 7 von 7 auf 5 zurück von 5 nach 6 zurück von 6 nach 8 von 8 nachzählen von 10 nach 9 von 9 18 zurück nach 8 nach 6 nach 4 nach 2 nach 1 geschlossen Tour immer dann wenn jeder Knoten geraten gerade hat und der Graf zusammenhängend ist können Sie geschlossen einmal in Jahr geschlossen und war einmal durch alle kannten durchlaufen Jahr Knoten haben Sie wie Sie hier sehen mehrfach durchlaufen jeder kann wird aber nur einmal durchlaufen ja Sie kennen das vielleicht nur noch matt Illustrationen das ist das Haus vom Nikolaus ja hier habe ich 2 Knoten ungeraden gerade sich mit einer angefangen mit einem 1 und mit dem andern Knoten geendet wenn ich irgendeinen kann oder genommen habe es nicht funktioniert aber wenn ich jetzt alle Knoten gerade gerade mache indem ich hier noch die 2 Kanten einfüge da kann ich irgendwo anfangen und kann alle kann einmal durchgehen und kommen am Ende wieder dort raus wo ich angefangen habe das diese Tatsache wird hier ausgenutzt dass wir so eine so einen Durchlauf durch alle kannten haben natürlich auch durch alle Knoten aber dicht nur wie gesagt mehr mehrfach und ich kann nur ein jeder kann noch einmal so und jetzt machen wir Abkürzungen mehr von 1 auf 2 noch keine Abkürzung für oder auch noch keine Abkürzung aber wenn Sie hier von 3 nachts über 2 nach 4 gehen wieder zurück von 3 nach über 4 dann haben wir den Knoten 2 ein zweites Mal schon jetzt besucht da machen wir eine Abkürzung gleich von 3 nach 4 also statt von 3 über 2 nach 4 im ich Work gehen wir direkt von 3 dafür streichen die dass das 2. vorkommender der 2 weg 4 6 5 7 bleibt so jetzt kommt die 5. 2. Mal in dem einer Schienenweg vor können die 6 kommen wir auch schon mal da können wir überspringen und können kleine können einfach ausstreichen die 5 und 6 und dann gleich bei der 8 hier statt über über 5 und 6 zur von 7 Uhr 5 und 6 zurück zu 8 ich bin mir gleich zu 8 in dem einfach jedes jedes Vorkommen eines Knotens der nicht der Vorkommen dieses Knotens ist einfach ausstreichen und genauso von von 8 die weiter nach 10 habe noch nie gesehen noch 9 aber viel gesehen 10 aber schon mal gesehen 8 haben schon mal gesehen 6 haben schon mal gesehen viermal schon mal gesehen zwar schon mal gesehen also gleich zurück zu 1 von der von der von der neuen aus so das ist dann eine Tour dadurch dass wir jede der Unterschied zwischen Sonne Juli Wort wenn Sie sich hier die Knoten durch den Durchlauf ankucken und einer Rundtour ist einfach der dass in so viel wie Ohlenburg jeder Club mehrfach auftreten können und was wir getan haben ist jedes Auftritt eines Knoten wir lassen nur das auf das aller 1. Auftritt des Knotens stehen und ein anderes streichen wir raus und das ergibt dann von dem comma damit kann nur von diesem Bild auf dieses Bild nur Kultur das ist die Rundtour die wir so konstruiert haben offensichtlich nicht optimal ja das kann nicht optimal sein sie können sich leicht überlegen das alles in einer optimalen Rundtour keiner keine solchen Kreuzungen vorkommen das das einer optimalen und keine 2 kann sich kreuzen mit der Dreiecksungleichung wir sich das wenn sie wollen zu Hause so sieht die optimale Tour aus und die Frage ist jetzt wie schlecht sind wir hier geworden gewesen dadurch dass wir das nicht optimal Togos Rede haben sondern diese diese Tour auch über diese 4 Schritte
und die Behauptung ist dass diese auch hier wieder eine Faktor 2 Approximation aus kann das heißt dass das was wir
hier linke Hand und das der vor konstruiert haben höchstens doppelt so lang ist wie das Optimum und sie sehen an diesem Beispiel auch wieder in der Realität einer Praxis kann man davon ausgehen dass das Ergebnis was man so konstruiert hat sehr viel besser ist als Faktor 2 so aber wie beweisen wie jetzt
Faktor 2 zunächst einmal machen uns klar wir das was wir hier im
1. schritt generiert haben diese minimale sparen Baum ist höchstens so lange wie die wie die optimale Rundtour warum wir nicht wenn ihr eine unter Herrn immer die optimale ich eine kann daraus da habe ich mich bei einem Baum in sehr sehr einfach strukturierten nämlich der Pfad nämlich als Pfad strukturiert aber sie schwanger bauen und was ich hier konstruiert habe ist der optimal Spanner Baum der minimal Spannung bauen das welch eine kann daraus und meinem Baum bekommen kann das nur besser sein als die optimale runter von gestartet bin und der minimale spare man kann natürlich auch nur besser sein das heißt das Gesamtgewicht dieses minimal spannen Baumes kann höchstens so groß sein wie das Gewicht der optimalen Rundtour das steht im 1.
dash so wenn ich jetzt jeder
kann verdopple hier kommt es der Faktor 2 rein wenn ich jetzt Ziel kann der verdoppele die also jede keine zweimal durchlaufen hat dann ist die Länge dieses allein schon wegen des dann ist die Länge ist aller schon ist natürlich höchstens zweimal so groß wie die Länge Spannung Baumes Ich habe ihre kann dass man in Baums verdoppelt und durchlaufen sie jeweils einmal hier dann eben dieser verdoppeln kannten so also das was hier in Schritt 2 konstruiert wurde bis höchstens doppelt so groß wie die Legende optimal und worden und wenn ich hier Abkürzungen machen jetzt auf diese jetzt an dieser Stelle kommt jetzt in der kommt jetzt hinein dass es das metrische TSP es die leisen Gleichung wenn ich die Abkürzung mache Dreiecksungleichung kann ich nur besser werden nicht schlechter das ist die Stelle bei der es bei einem ethischen der SPD in die die ganze Argumentation der ganze also schiefgeht aber bei mittelschnellen dies bitte Reizung Gleichung habe ich von hier vom mehr gibt es von Schritt 3 zum Ende des von Fortschritts 4 nur höchstens eine Verbesserung oder es ist gleichgeblieben und damit ergibt sich insgesamt
dass das was wir konstruiert haben höchstens zweimal so schlecht sein kann wie auch immer noch und hoher das kann
aber noch treiben du hole ich einen der Pioniere der Algorithmik und der Komplexitätstheorie also endlich beschwere und diese ganzen Sachen wie wie wie ist es mit der Laufzeit der von Algorithmen nämlich Christoph jedes der hat das vor mehr wie lange ist es her fast 40 Jahre entwickelt sie Sendeformate sind 40 Jahre eine Ewigkeit nicht im Gegensatz zu zu anderen Disziplinen wie beispielsweise Mathematik vor 40 Jahren ich gar nicht sind im Verhältnis zu Gesamtgeschichte so der gegeben kleines bisschen raffinierter vor er mache das selbe zunächst mal wie hier in Schritt
1 ein minimal sparen am Baum zu konstruieren aber alle andern Schritte er auf dieser Folie vergessen Sie da macht dieser Algorithmus und sowie das was anderes so was macht der jetzt hier und jetzt sollten wir uns ein period klarmachen die Knoten mit ungeraden gerade hier das ist die 1 die 2 der gerade 3 der 3 hat hat unseren gerade die 7 die 6 und die und die neuen ja wir haben 6 Claude mit ungeraden gerade diese 4 Blätter hier haben gerade 1 und die beiden hier haben gerade 3 das eine gerade Zahl von Knoten und das ist kein Zufall das ist immer so und nun wieder mal ein bisschen Platz wurde bitte ab wenn Sie denn gerade die Anzahl der in siedendem kannten so bezeichnen was ist dann die Summe aller Knoten gerade das ist gerade zweimal die kann Zahl weil wenn Sie eine Kante VW haben dann zählt die einmal in diese Summe hinein wenn Sie den gerade von Fauch hinnehmen und diese bekannte zählt nochmal hinein wenn sie den Grad der anderen er des anderen entknoten zählen nehmen das heißt also Sie kriegen insgesamt zweimal diese kann und das ist eine gerade Zahl immer natürlich das heißt die Anzahl der Knoten gerade die ungerade sind muss gerade sein ich hoffe das das sich auseinander Vierteln Quoten es dummerweise heißt es im in den Deutschen auch noch der Knoten gerade auch noch gerade also sehr nah bei gerade männlichen wäre es vielleicht ein bisschen einfacher dann aber auf Laute geriestert Ort Mast das ist ein bisschen sprachlich auseinander aber wie auch immer die Anzahl der Knoten an die wir hier die für jeden Grafen nicht will nicht nur für Bäume die Anzahl der Knoten die ungeraden gerade haben muss gerade sein so was wir jetzt machen ist alten Bekannten da einzusetzen wir wir rechnen ein optimales Mertsching also wir haben hier in diesem Beispiel ich nehme dieses Beispiel mal her um das noch mal zu illustrieren was auf den Folien ist das nicht weiter gezeichnet und nichts gut die sie haben sie haben die Knoten 1 bei Wahlen ich wollte mal ein bisschen hier also es wächst 9 und was fehlt auch die 2 das egal in welcher Reihenfolge hier ist und wo dann die 2 und die Sie eben das sind die 6 Knoten mit ungeraden gerade in diesem Beispiel und die Verletzten sie allesamt miteinander das wir das müssen schwierig für mich zu zeichnen so Sie das mal einen so was fehlt es fehlen jetzt die könnten hier also ich will die vollständigen Grafen haben das kann ich jetzt noch andeuten dass klappt alles nicht mehr zum Zeichnen doch ich glaube es klappt fast so ich glaube ich habe damit tatsächlich vollständigen Grafen gezeichnet oder halt 1 2 3 4 stimmt nicht doch 5 so 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 Tatsachen der Vorschläge aus 6 Knoten und auf dem bau ich jetzt ein minimales Mertsching minimales perfektes mitschwingt auf das heißt also 3 kann 3 Kanten in diesem Falle die Mädchen bilden und minimales Gewicht haben wie wir sowas macht haben wir alles gesehen nämlich sehen sich in die Augen und die der Fahrt Sache ziemlich zu Anfang der Veranstaltung kann sich jetzt nicht an der inneren zur Prüfungsvorbereitung werden sich hier dran ändern so und was machen wir jetzt
so was wir haben erst eine minimale Spannung Baum T gefunden konstruiert dann gucken wir uns die Knoten an die ungeraden gerade haben dass jetzt in den Beispielen in genau die gewesen ein Minimum ein perfektes Matching mein Gericht perfekt heißt dass sämtliche können mit stehen das geht natürlich am falschen Grafen immer in allgemein diesen Grafen nicht so jetzt haben wir dieses minimale Mädchen gefunden und jetzt fügen wir diese Mädchen kannten hier an das will ich versuchen
auch wieder zeichnerisch zu bewerkstelligen ich nehme mir diese diesen Spannung Baum noch mal her so uns die Knoth um die es geht sind der da der der der der da der und der und ich weiß jetzt nicht wie das minimale Mädchen ausreden so ansieht er der es ist nicht unwahrscheinlich das 12 ich kann dass diese Kante drin ist wie sieht das jetzt hier optimal aus wahrscheinlich so ungefähr in der Form das eine der der Gemeinden ist und das hier die beiden miteinander verbunden sind so ja so könnte so könnte wenn die Religion geometrischen dass da sehr kritischen Distanzen hier die Geräte die die Kantenlängen sind er scheint es mir plausibel dass das wahrscheinlich das optimale Mädchen ist von diesen 6 kannten so jetzt immer wieder dieselbe Situation wie vorher W ich hier wo wir wo wir auf primitive Art und Weise diese so und erreicht haben sich verdoppeln jeder kannte wir haben wir dieselbe Situation das alle Knoten gerade jetzt gerade geworden sind dann sind bei jeder einzelnen kann Knoten der ungeraden gerade hatte haben jetzt eine kann hinzugefügt und jetzt immer dasselbe machen wie hier auf der Folie nämlich einen eulerschen Wort hier irgendwie durch zu gehen aber zum Beispiel ich Zeugnis doch mal die die Nummer 1 hier ja 5 6 wegen 8 10 9 zum Beispiel können oder aus sehen es war legte Rally wir 2 zu 2 zur 4 das zur 6 und jetzt einmal so rum macht zählen neuen sie geben 5 6 1 ja da bin ich einmal so im Uhrzeigersinn um das Ganze umgegangen und jetzt kann ich wieder selber machen die um bei der einfachen Heuristik also bei der einfachen Approximation so guten sowie genau sagen die 2 comma decimal 7 2. Mal vor hier schmeißen raus die 4 als die 3 fällt 3 die 4 die 6 ist kann zum 1. Mal vor 8 zählen neuen sie leben 5 6 2. das mal vor die 1 das heißt also die Rundtour die wir dann konstruieren ist von 1 nach 2 nach 3 nach 4 nach 6 8 10 9 sie geben 5 und direkter Sprung zu also genau einmal sozusagen hier ich hier im Uhrzeigersinn wenn man so will so das ist der eine der anderen von Christoph Wedel ist also sehr ähnlich nur dass er sehr ähnlich wie diese aggressive eben vorher betrachtet hatten nur mit dem Unterschied das hier die ganzen die die die die die Herstellung der Situation dass wenn alle schon weg haben dass wir also gerade als sei er gerade c't und darüber haben dass sie auf eine Art und Weise bewerkstelligt wurde warum
ist das jetzt warum die das ist was Beßres nur 3 halbe Approximation das heißt das Ergebnis das höchstens die Idee die Länge der so retten unseres Wissens 3 halbe die Sänger der optimalen und hoher gut also zunächst einmal die Tour wieder selber Argumentation legitimierte geht 3 das ist der das metrische TSP erst von hier nach hier die Abkürzung zu nehmen kann ich mich nur verbessert haben dann der Dreiecksungleichung so wir haben schon festgestellt dass der Spanier bauen am Anfang konstruiert haben dass der höchstens so groß sein kann wie die optimale Tour länger okay das heißt also wir müssen erst noch beweisen nur noch einflussreichen dass die Größe des Mädchens diese 3 kannten die wir hier eingesetzt haben dass diese Größe dass diese dass das Gesamtgewicht dieses Mädchens frühestens in halb so groß wie das Optimum ist wie optimal rund war die beweisen das wir nehmen uns die optimale rund oder Ja Theo Haupt wir wissen wie sie aussieht bitte Sie uns trotzdem mehr und gucken uns die Knoten an über die wir diese 6. und über die wir die ganze Zeit gerichtet geredet haben in der Reihenfolge in der sie auf diese Rundtour erscheinen ja das hat mit den Reihenfolge wollen über die ob zu tun in der wir wissen nicht wie optimal du aussieht aber in der das heißt wir Wissens doch da hatten dass er in optimalen
Tour wir gucken uns diese Knoten an die 1 die 2 die 3 die 7 die 6 der 9 in der Reihenfolge in der sie auf der Rundtour hier auftreten also 1 2 3 6 9 7 das Ziel das damit
ist W 1 bis W 2 K bezeichnet es wir gerade Anzahl hat können wir 2 K schreiben als Index und wir konnten uns diese zweimal Tschings an einerseits da ist 1 mit zwar der 1. 2. 3. mit dem 4. und so weiter gematcht wird und zum anderen dass der zweite mit dem dritten der Fehde mit dem 5. und so weiter gematcht wird ja wie kommen Sie dazu das sind 2 verschiedene perfekte Match längst für diese Knoten so das Optimum ist wieder die Dreiecksungleichung das Optimum das das sind 2 das sind 2 Abkürzungen vielleicht mache ich doch besser noch mal am Beispiel hier an dem an der optimalen
Tour das wird sonst zu unübersichtlich wenn ich das nicht aufzeichnen bitte was wird da so wir haben einerseits die Mädchen kannten 1 2 3 6 und 9 7 das ist eine Menschen das uns angucken auf der optimalen und oder die Knoten ungeraden Grades aus dem spannenden Baum in dieser Reihenfolge und wir haben natürlich stattdessen die andere Reihenfolge auch 2 3 man hat eben nicht mehr der sondern 6 9 und 7 1 ja diese beiden Mädchens betrachten wir hier jeder von den beiden kürzt hier irgendwas von der Rundtour ab ja zwischen sie noch andere Knoten Rundtour und hier wird auch irgendwas abgekürzt von der Grund war hier wird die eine Hälfte man von solchen die eine tolle der Rundtour durch 3 Kanten apt-get abgekürzt und hier wird der der verbleibende Teil der Rundtour durch 2 andere Kanten abgekürzt ja das heißt die Summe dieser beiden mehr Tschings dieser beiden Menschen Gerichte die 3 Kanten Gewichte plus die 3 kann Gerichte sind wegen der Dreiecksungleichung wieder die von beiden alle 6 kann zusammengenommen sind wegen der 3 zum Gleichung höchstens so groß so lang wie die Rundtour denn jeder Teil der Rundtour wird von einer Kante entweder hier in dem Mädchen oder von einer kann in dem Mädchen abgekürzt das führt zu der
Ungleichung die Sie hier sehen das Optimum kann nicht besser sein als das Gericht dass ein Mädchen mitschwingt links und das Gewicht des armen Mädchens rechts weil diese beiden Mädchen zusammen jeder Teil der Rundtour also wir haben 6 Teile der Rundtour nicht so so gekritzelt bezeichnet habe aus den diese und besteht und jeder dieser Sechsteiler wirklich eine dieser Kanten abgekürzt Dreiecksungleichung bedeutet dies und das diese ungleichen Geld so dass wir können was wir konstruiert haben ist aber ein minimales perfektes Matching das heißt also sowohl ups
sorry sowohl dieses M 1 es größer gleich hat größere Gleichgewicht also wenn großer Gleichgewicht ein das heißt die Summe von M 1 und M 2 sie sind mindestens so groß wie 2 das Gewicht des Mädchens oder andersrum gesagt da er die Summe aus einem Ei den Gewicht den also 2 höchstens so groß ist wie das Optimum wiederum dash da vor ist das Optimum mindestens so groß wie 2 Mal das Gewicht dieses Mädchens oder das was wir hier zu zeigen hatten das Gewicht des Mädchens das Wissen so groß wie die Hälfte des ob dem ums und damit ergibt sich insgesamt 1 3 Approximationen so an dieser Stelle sind wir auch so mit der Zeit fertig und mit den Folien
passt ja wunderbar wir haben das ist das ist der Ausblicks Folie die über diese Vorlesung hinausgeht es selbstverständlich nicht prüfungsrelevant wir wollen jetzt vielleicht auch gar nicht mehr weiter betrachten gucken Sie sich das an wenn Sie wollen aber für den auf für den in eine Richtung die theoretisch ganz spannend interessantes aber dann irgendwann doch in praktischen Bezug ganz verliert sofern entspricht diese das was Sie angedeutet wird auch nicht mehr der Philosophie dieser Vorlesung und deshalb können wir die zuvor gerne aus was ist auch die letzte vor diese nach ganzen Vorlesungsreihe passt doch wunderbar mit der Zeit da möchte ich mich bei Ihnen bedanke mich für Ihre Treue die sie mir gehalten haben durch diese finstere Jahreszeit hinweg ich hatte das ja schon mehrfach gesagt in jeder der Bilder gerne Prüfung machen möchte da erwarte ich ein ein Gespräch über die praktische Aufgabe zuerst ein individuelles Gespräch wenn Sie lieber zu zweit oder zu dritt kommen wollen ist mir das natürlich auch recht spannende Zeit aber wenn Sie lieber allein kommen wollen müssen endlich auch recht und dann machen wir eine Prüfung eine mündliche Prüfung und beide Termine werden wir ganz im gegenseitigen Einvernehmen bilateral ausmachen so das ist so dass der Termin passt und Soße Termin mehr passt und ob das jetzt ziemlich bald nach dieser Veranstaltung nach dem Ende der Vorlesungszeit ist oder ist den Beginn der nächsten Vorlesungszeit oder ich weiß nicht was ich habe es immer noch mal Interessenten für Prüfung aus der algorithmische Modellierung aus dem letzten Sommersemester ist mir egal wie wie Sie sich das dann einteilen wollen sollte rechtzeitig sein bevor ich in die Pensionierung der aber bis seines auf sich noch bis dann sind Sie hoffentlich auch so weit prinzipiell außer wenn ich natürlich da jetzt gerade nicht da bin also so im großen Ganzen müsste ich eigentlich immer so weiter sein also ich kann es nicht genau sagen soll Aprilwoche aber müsste eigentlich gut funktionieren kommen Sie bitte so sagen wir mal 3 Wochen vor Ihrem Wunschtermin auf mich zu dann wird sich sicherlich noch genug Platz in meinem Terminkalender finden lassen dass wir da einen beiderseits angenehm Termin finden werden das würde ich forsche würdigte dezidiert vorschlagen also es macht keinen Sinn einen Beratungsgespräch müsste oder ein Prüfungsterminen wir zusammen zu nehmen ja ok das kann auch unsere wenn Sie unbedingt wollen dann so am selben Tag unmittelbar machen nacheinander weil wenn sie darum vergnügungssüchtig sind gut dann bleibt mir nur ich bei Ihnen zu bedanken bitte um Entschuldigung dass ist die Folien dass die Videos immer etwas hinterherhinkt denn jetzt ist das jetzt das letzte Video das aufgenommen wird und ich hoffe mal sehr dass sie jetzt relativ bald an alle im Internet hin und nicht nur die 1. Preis comma mal was mit diesem dieser
Hintergrundprozess ist auch fertig prima dann können wir hier an dieser Stelle 2 Minuten überzogen können wir hier an dieser Stelle abbrechen und vielen Dank der
Loading...
Feedback
hidden