Neighborhood-Based Approaches - Local Search / Exact Neighborhoods

Video thumbnail (Frame 0) Video thumbnail (Frame 5531) Video thumbnail (Frame 10911) Video thumbnail (Frame 14644) Video thumbnail (Frame 24516) Video thumbnail (Frame 26729) Video thumbnail (Frame 31837) Video thumbnail (Frame 36987) Video thumbnail (Frame 41792) Video thumbnail (Frame 46619) Video thumbnail (Frame 49614) Video thumbnail (Frame 53434) Video thumbnail (Frame 56969) Video thumbnail (Frame 60106) Video thumbnail (Frame 61889) Video thumbnail (Frame 64969) Video thumbnail (Frame 68864) Video thumbnail (Frame 70572) Video thumbnail (Frame 74196) Video thumbnail (Frame 76956) Video thumbnail (Frame 80917) Video thumbnail (Frame 90435) Video thumbnail (Frame 99953) Video thumbnail (Frame 109809) Video thumbnail (Frame 115371) Video thumbnail (Frame 122671) Video thumbnail (Frame 125296)
Video in TIB AV-Portal: Neighborhood-Based Approaches - Local Search / Exact Neighborhoods

Formal Metadata

Title
Neighborhood-Based Approaches - Local Search / Exact Neighborhoods
Title of Series
Part Number
2
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.
Neighbourhood (graph theory) Solution set Iteration Maxima and minima Directed graph
Kante Polymorphism (materials science) Neighbourhood (graph theory) Graph (mathematics) Maxima and minima Lösung <Mathematik> Parameter (computer programming) Order of magnitude Physical quantity Plane (geometry) Solution set Iteration Arc (geometry) Social class Slide rule Raum <Mathematik> Feasibility study Square Set (mathematics) Term (mathematics) Existence Solution set Well-formed formula Ecke Relation <Mathematik> Optimum Iteration Mathematical optimization Local ring Directed graph Combinatorics
Kante Neighbourhood (graph theory) Similarity (geometry) Hidden Markov model Feasibility study Shift operator Permutation Element (mathematics) Permutation Position Symmetric matrix Travelling salesman problem Natural number Relation <Mathematik> Modulform Identical particles
Kante Neighbourhood (graph theory) Greatest element Euclidean vector Graph (mathematics) Lösung <Mathematik> Weight Subset Mathematics Connected space Solution set Strategy game Zusammenhang <Mathematik> Vertex (graph theory) Summation Arc (geometry) Partition (number theory) Slide rule Neighbourhood (graph theory) Mass Feasibility study Set (mathematics) Connected space Sign (mathematics) Grand Unified Theory Travelling salesman problem Bipartite graph Network topology Number theory Partial derivative Optimum Euklidischer Raum Local ring
Kante Polymorphism (materials science) Computer programming Neighbourhood (graph theory) Graph (mathematics) Constraint (mathematics) Model theory Direction (geometry) Algebraic structure Kapazität <Mathematik> Infinity Approximation Graph (mathematics) Vertex (graph theory) Local ring Arc (geometry) INTEGRAL Slide rule Köcher <Mathematik> Venn diagram Neighbourhood (graph theory) Desire path Feasibility study Mass Subset Logic Function (mathematics) Number theory Partial derivative Relation <Mathematik> Condition number Set theory Quote Mathematical optimization Local ring
Computer programming Stress (mechanics) Neighbourhood (graph theory) Zahl Graph (mathematics) Direction (geometry) Algebraic structure Lösung <Mathematik> Matching (graph theory) Differentiable function Spacetime Convex set Vertex (graph theory) Length Exterior algebra Elementary arithmetic Konvexe Funktion Dimension 1 Slide rule Mathematical analysis Feasibility study Computer programming Zielfunktion Subset Function (mathematics) Relation <Mathematik> Optimum Integer Mathematical optimization Convex set Euklidischer Raum Schrittweite
Kante Neighbourhood (graph theory) Matching (graph theory) Symmetric matrix Graph (mathematics) Horizon Relation <Mathematik> Mittelungsverfahren Arc (geometry) Elementary arithmetic Proof theory
Kante Neighbourhood (graph theory) Symmetric matrix Graph (mathematics) Algebraic structure Relation <Mathematik> Optimum Exterior algebra Local ring
Neighbourhood (graph theory) Mathematics Symmetric matrix Graph (mathematics) Relation <Mathematik> Optimum Calculus Elementary arithmetic Local ring Proof theory
Kante Ramification Stress (mechanics) Neighbourhood (graph theory) Graph (mathematics) Desire path Connected space Symmetric matrix Zusammenhang <Mathematik> Relation <Mathematik> Linie Arc (geometry) Elementary arithmetic Proof theory
Neighbourhood (graph theory) Symmetric matrix Logic Graph (mathematics) Algebraic structure Desire path Relation <Mathematik> Exterior algebra
Kante Neighbourhood (graph theory) Slide rule Graph (mathematics) Matching (graph theory) Mathematics Symmetric matrix Graph (mathematics) Relation <Mathematik> Theorem Local ring Gebiet <Mathematik> Elementary arithmetic Exterior algebra Maß <Mathematik> Arc (geometry) Loop (music) Local ring Proof theory
Slide rule Symmetric matrix Network topology Direction (geometry) Matching (graph theory) Vertex (graph theory) Quote Local ring Electric current Exponentialabbildung
Kante Stress (mechanics) Cycle (graph theory) Direction (geometry) Moment (mathematics) Latin square Matching (graph theory) Theory Network topology Vertex (graph theory) Length Linie Exponentialabbildung
Kante Operations research Stress (mechanics) Matching (graph theory) Cycle (graph theory) Graph (mathematics) Matching (graph theory) Forest Urinary bladder Network topology Autoregressive conditional heteroskedasticity Reduction of order Proof theory
Stress (mechanics) Matching (graph theory) Constraint (mathematics) Neighbourhood (graph theory) Matching (graph theory) Canonical ensemble Length Local ring
Kante Stress (mechanics) Neighbourhood (graph theory) Constraint (mathematics) Direction (geometry) Maxima and minima Lösung <Mathematik> Kapazität <Mathematik> Equation Number Hausdorff space Cloning Divisor Summation Electric current Strömung Arc (geometry) Directed graph Desire path Set (mathematics) Professional network service Logic Function (mathematics) Steady state (chemistry) Cube Vertex (graph theory) Ecke Relation <Mathematik> Set theory Optimum Untere Schranke Flux Maß <Mathematik>
Stress (mechanics) Neighbourhood (graph theory) Slide rule Compass (drafting) Relation <Mathematik> Set theory Quote Nichtlineares Gleichungssystem Summation Bound state Arc (geometry) Proof theory
Kante Stress (mechanics) Addition Euclidean vector Compass (drafting) Direction (geometry) Vector graphics Desire path Maxima and minima Set (mathematics) Bound state Energie Index Function (mathematics) Vector space Negative number Summierbarkeit Divisor Negative number Summation Arc (geometry) Flux Directed graph
Stress (mechanics) Mass flow rate Lemma (mathematics) Desire path Feasibility study Sign (mathematics) Logic Helmholtz decomposition Integer Pairwise comparison Arc (geometry) Inductive reasoning Flux Proof theory
Neighbourhood (graph theory) Slide rule Lösung <Mathematik> Sequence Radical (chemistry) Iteration Relation <Mathematik> Heuristic Genetic programming Heuristic Local ring Mathematical optimization Local ring
so genau sind die Änderungen der immer so seine Haftstrafe Lernmaterialien an der TU Darmstadt gut
hallo allerseits ich darf Sie herzlich begrüßen etwas verspätet die Technik dein Freund und Helfer Sie haben sehr gesehen irgendwie ich bin mir nicht sicher ob die Kammer jetzt was aufnimmt oder ob sie nichts aufnimmt das werden wir dann später mal sehen ich würde mich das bemühen heute ich glaube es ist passt ganz gut heute wenn ich glaube ich weniger an der Tafel machen wollen und mehr auf den Folien wir haben das letzte Mal gesehen diesen diesen 1. einfachen Algorithmus generischen Algorithmus ein Muster für ein Algorithmus sehr einfach wir stellen uns vor der Lösungsraum es etwas wie eine Landschaft oder eigentlich haben das genau vorgestellt wie ein gerichteter Graph jede Lösung ist ein Knoten und wir kommen von einem Knoten zu einem anderen durch eine Nachbarschaftsbeziehung es am Beispiel von TSP gesehen wie das aussieht so wie das aussehen
kann etwa wie wir noch ein paar weitere Beispiele heute sehen aber das ist erst einmal das Grundschema dass wir dann in verschiedener Art und Weise dann verfeinern verkomplizieren um das Grundproblem dieses einfachen Schemas zu überwinden nämlich das Grundproblem das die Suche in einem Blog ein Optimum und dieses Lokal Optimum Karen zufällig kann muss aber kein globales nicht das gewünschte global Optimum sein kann sogar einen Wert haben der beliebig schlecht ist also der beliebig schlecht von Global optimalen wert ist und das ist natürlich sehr sehr ungeschickt werden wenn wir da mit diesem einfachen Schema am Ende kommen wir kommen ans Ende wenn wir keine Nachbarn mehr haben denn wir wir von der aktuellen Lösung erstellen Stern aus der besser ist als diese aktuelle Lösung erstellen und aber eben nicht umgehend global wir haben den Begriff der exakten Nachbarschaft beim letzten Mal eingeführt das ist ein das ist ein eine Nachbarschaft des exakt in dieses Lokal Optimum globales werden spielt gleich sehen im Fall dass die das Lokal Optimum global ist wissen wir definitif dass dies schon dieses einfache Schema ohne weitere Fahrkünste Lungen schon zu einem globalen Optimum führt wie gewünscht falls der alten muss terminiert natürlich selbst das kann man nicht immer auf von von einem sagen denn der Lösungsraum zu einer gegebenen Importe eingeben Instanz keine durch aus unendlich groß sein und in dem Fall kann man natürlich nicht so unbedingt brauche man zusätzliche Argumente um sagen zu können dass der Algorithmus garantiert terminiert aber in den Dingen die wir so betrachtet haben und auch betrachten werden in dem Problemstellung den sie uns Display es gibt nur endlich viele Rundtouren das heißt also auch dieses einfache Schema wird mit einem guten oder schlechten Ergebnis zumindest nach endlich vielen Schritten nach einen einheitlichen Anzahl von Iterationen auf jeden Fall zum Ende kommen werden weil er die Lösungen die wir durchlaufen von Schritt zu Schritt nur besser werden können er kann keine Lösung zweimal durchlaufen werden das heißt die Anzahl Iterationen beschränkte Skikursus Lösungs Raums und der Welt dazu muss natürlich im Allgemeinen dramatisch um Größenordnungen kleiner als etwas ist es uns raus
so also nochmal da gab es auch Anfragen Forum mit die ganz konkret zu Übungsaufgabe also wenn Sie beispielsweise sich immer von Herzen Folie implementieren und anwenden auf die Übungsaufgabe dann bedeutet das in der Implementation des Algorithmus darf nichts erkennbar sein das ist hier in diesem konkreten im Quelltext denn Sie schreiben um rechte Ecke geht die in der Ebene platziert sind es die man mit meiner vergleiche Größen klein und so weiter ob sie sich schneiden und und so weiter davon darf nicht sichtbar sein sondern ihre Implementationen des Algorithmus oder der ganzen Algorithmen sei so generisch seien wie hier auf den Folien nämlich dass wir Apps abstrakt von Lösungen abstrakt von Schritten vorwärts reden dazu sind geht genau diese die schöne Möglichkeiten von beispielsweise von Objekt Programmiersprachen wie sieht unser Plus Plus sehr gut geeignet mit dynamische Polymorphie durch Vererbung den ja aber auch durch Interface ist das heißt also in der alle im algorithmischen Code in dem in der Implementation des eigentlichen Algorithmus haben Sie irgendwelche in dafür ist es in die rechte Ecke stecken dann in den implementierenden Klassen salopp gesagt aber falls die gar nicht weiterkommen dann können Sie gerne auch im Forum entsprechend ihre Fragen platzieren kann man das gerne für alle sichtbar diskutieren so also wir sind so abstrakt dass nix mit Recht Ecken und auch nichts mit Rundtouren oder in sonstigen am Hut haben sondern nur 1 1 er beliebiger gerichteter Graph auf dem Lösungs Frauen das haben Sie beim Beispiel TSB schon beim letzten Mal gesehen er wird man im allgemeinen Nachbarschaft nicht so definieren dass jede Lösung mit jeder anderen Lösung benachbartes sondern wie beim Beispiel TSB vom letzten Mal sie kommen von einer Lösung seiner benachbarten lösen indem sie 2 Kanten rausnehmen 2 andere rein tun das ist natürlich eine daher die also die Menge der Lösung die Sie so bekommen können von Einnahmen aus ganz Lösung es natürlich um Größenordnungen kleiner als der ganze Süsens Raum aber trotzdem natürlich immer noch groß es ist erst einmal noch eine quadratische Anzahl von Nachbarn Quadrat in Anzahl von Knoten das ist das was hier steht im Verhältnis zum gesamten Lösungsraum ist das ist das sind die ist die Anzahl der Nachbarn einer Lösung er typischerweise Taini winzig aber immer noch aber nicht unbedingt klein in absoluten begriffen sondern eben wie in diesem Beispiel quadratisch was wir natürlich nie machen müssen das ist halt das wäre ja würde alles kaputtmachen was wir nie machen müssen das ist die diese ganze Nachbarschaft auch mal wirklich aufzubauen diesen ganzen Grafen war also ist das wäre natürlich Quatsch damit könnten wir die ganzen Ansatz vergessen sondern der ist Apps zu der ist einfach implizit drehen in den Modifikation zu regeln welche Möglichkeiten der Modifikation der aktuellen Lösung gibt es um von der aktuellen Lösung zu einer benachbarten Lösung zu kommen also in endlich in einem Stück Code in einem Stück Software
so betrachten wir mal ein paar Beispiele hier 2 Beispiele die gewisse Ähnlichkeiten haben sortieren und noch nochmal dass die SPD beim TSB waren schon zu können wenn wir das nur kurz streifen sortieren nicht so die ist natürlich auch eine
das pdi Problemchen wie TSB eine Problemstellung eine bestimmte Permutation zu finden nur die Zielsetzung seiner an und beim Sortieren die Zielsetzung die Ihnen bekannte beim TSB ist die Zielsetzung die Kanten die verwendet werden deren Sommer von Gerichten zu minimieren so wie wenn wir 2 Permutation haben das ist ein paar Beispiele einfach einzelne Beispiele für eine symmetrische und eine asymmetrische Nachbarschaft die 1. ganz einfach sie haben eine Sequenz des jetzt muss ich doch die Tafel benutzen sie haben eine sie können das ist Ihre momentane Permutation und Sie kommen zu einer neuen Permutation einfach in dem sie 2 mit austauschen ja genauso solche der Mutter zum Schulden machen sie bei den meisten Sortieralgorithmen an das ist ein Beispiel für eine symmetrische Nachbarschaft Beziehung wenn ich jetzt noch mal diese beiden Position Austausche bin ich wieder bei dem ursprünglichen hingegen das zweite ist ein bisschen komplizierter Hmm wir haben hier 2 Positionen E und J und was wir machen ist A B C D E F diese Werte zyklisch zu rotieren wiederum habe ich das hier gemacht von Ihnen ist jetzt J Was heißt hier ist er und alles andere wird 1 auf also mehr steht hier mit diesen Formen nicht drin als das was in auch dieses Beispiel hier sollte wenn es nach schauen wollen alles links von E ist bleibt gleich alles rechts von ihr bleibt gleich alles mit 1 auf uns 1 geht von hinten nach vorne so das aber beim letzten Mal schon gesehen
das Beispiel TSB sehnen sich 2 Kanten mehr irgendwelche 2 aus einer gegebenen Rundtour und fügen dann durch und durch 2 neue kannten diese beiden übrig gebliebenen Stücke wieder zu einer unter zusammen wobei sie daran denken müssen hier wenn sie die zusammenfügen müssen Sie eine der beiden Stücke da müssen Sie die Kanten umdrehen das ist hier in diesem Beispiel mit den Rechten mit dem rechten Stück gemacht worden so das selber hatten das hat mir beim auch schon gesehen Sie können das nicht nur mit 2 Kanten machen sollen auch mit 3 kann mit beliebig vielen da sehen Sie schon den Thread auf den sie immer haben wenn Sie sie können die Nachbarschaft natürliche reichhaltiger gestalten indem sie jetzt nicht mehr 2 Kanten rausnehmen und 2 andere Karten rein tun sondern so wie das auch schon beim letzten Mal gesehen haben 3 Karten rausnehmen und dann diese 3 übriggebliebenen Stücke durch 3 neue kannten wieder einfügen sie ändern sich nicht zeigen vielleicht noch mal ganz kurz zur Änderung an sie haben hier und so eine Rundtour mit 3 könnten die Sie jetzt hier ausgewählt haben und diese 3 Kanten schmeißen sie raus dann bleiben diese 3 Stücke übrig und wenn Sie das jetzt richtig machen so so so und dann die gegebenenfalls noch hier diese 3 Bruchstücke da was umdrehen wie eben bei den 2 könnten dann haben sie dann und ist eine reichhaltigere Struktur die Wahrscheinlichkeit noch nicht im Lokal Optimum hängen zu bleiben sondern weiterzukommen ist natürlich damit größer geworden nur dafür kostet natürlich die Evaluierung dieser Rundtour mehrere wären es plötzlich kubisch fiel der Nachbarn nicht mehr quadratisch viele Nachbarn soll ich die solches mehr nein Ja also ich denke mir in diesem Fall muss das Jahr ist er dass er mehr Gewicht als das Nein sowohl gedacht gut so und das ist das gerne Problemen ein weiteres Beispiel wir haben das Steiner Baum Problem letztes mal als Beispiel die sehen für alkoholische Problemstellung oder vorletztes letztes Mal Sie ändern sich die Problemstellung ist um noch nochmal visualisiert geben in Input ist ein ungerechter der Graf mit Kantenlängen plus Terminal das ist nur aus weil der Knoten und gesucht ist ein warum minimalen Gerichts so dass die also dass alle Terminal miteinander verbunden werden das ist die Verallgemeinerung des Minimums in Triest darauf dass nicht mehr alle Blumen einer verbunden werden müssen sondern eine Auswahl so und hier sehen Sie eine Möglichkeit beispielsweise wie man eine Nachbarschaft definieren kann wir haben hier ein kleines Stück ja genommen in einer Lösung ein kleiner einen kleinen Pfad schmeißen den aus und ersetzen ihn durch einen etwas anderen vor Ort das ist eine Möglichkeit anderes Beispiel in diesem anderen aber diese andern Problemstellungen wie man von einer zulässigen Lösung zu einer einer unzulässigen Lösungen kommen kann die Partition das Beispiel hat mir beim letzten Mal auch schon angesprochen kann kann man relativ schnell jetzt drüber gehen sie denken Sie sich das Szenario mir fällt leider keine mehr Szenario 1 Scheidung es gibt eine ganze Menge verschiedener Güter G aufzuteilen sind und man möchte gerne möglichst Fifty-Fifty aufteilen zum Beispiel hier wenn das B R 50 Prozent ist oder doch wir werden dafür doch was das ist ein stellen Sie sich vor Sie haben ein Lastwagen sie wollen viele schwere Güter transportieren dürfen das zulässige Gesamtgewicht nicht überschreiten wir wollen aber insgesamt möglichst viel Gewicht Wert Friend so dass es gerade so eben noch das zulässige Gesamtgewicht nicht über schreitet sie wollen also die Summe der Gerichte die sie in den Lastwagen packen können Maximilian wobei die Summe die genau diese Summe der Gesang Gewichte nicht das Gefühl diese Gerichte nicht das Gesamtgewicht zulässige sagen nein also genau gesagt die die zulässige Zuladung nicht überschreiten darf das Gesamtgewicht ist ja inklusive der dem Eigengewicht also wir suchen eine Teilmenge der Gesamtmenge von Gütern aber sind ja durch Ihre in die und wollen das Maximieren unter dieser Bedingung jetzt hat mir beim letzten Mal schon angesprochen die Möglichkeit eine Nachbarschaft zu definieren 2 zulässige Lösungen sind nach Bad genau dann wenn ich komme von einer Lösung zu anderen in dem ich aus dieser Lösung ein period ein alter Mann immer ein Stück aus dem und man muss dafür einsetzte aber beim letzten Mal schon gesehen warum das keine so gute Idee ist damit ist der Lösungsraum massiv fragmentiert dieser Graf auf dem Lösung warum diese der Nachbarschafts Graf ist massiv unzusammenhängend denn wenn den Zehen wenn 17 Stück zu transportieren haben und nur diese was wir unser meine Lösung mit 10 Stück und Sie haben ja diese Regel um zum Nachbacken Lösung zu kommen denn kommen Sie niemals und unter keinen Umständen zu einer Lösung mit 11 oder mit 9 Stück oder sie oder mit noch was an und sie kommen immer nur zu einer anderen Lösung mit 10 Stück deshalb wäre es also besser sie
kommen sie der Weg in die Nachbarschaft müssen anders so wie hier in diesem zweiten dash dass sie sagen sie kommen von einer zulässigen Lösung zu einer benachbarten indem sie schritte 3 Arten von wird erlauben diesen Austausch Schritt wie eben aber auch sie erlauben das in einer mit eingefügt wird einfach über sie dann auch noch das einem nennt ausgeschickt wird also ausgenommen wird ist im Zusammenhang mit lokaler Suche noch nicht so toll war in der man rausnehmen wird man nie keine keine Verbesserung geben damit mit einfügen ist noch irgendwo einen Schritt auch Schluss wenn sie entsprechend viel mit eingeführt haben kann sie keine Zeitung mehr einfügen er ist aber nicht unbedingt die optimale Lösung aber im Zusammenhang mit komplexeren Strategien die wir hoffentlich heute schon beginnen können wird er wäre so sollen Nachbarschaft schon ausreichen gut also generell sollte es aber merken wenn wir eine Nachbarschaft definieren dann sollten wir wirklich abstrakt auf den Nachbarschaft kaufen mal gucken und schauen ob der zusammenhängt ist wenig zusammenhängt ist dann kann es uns passieren wie studiere Staat mit einer Stadt Lösung in einer zusammen es Komponente und die gute Lösung sind der andern Zusammenhangs Komponente Pech gehabt in der Zusam es kommende Wohlstand nur schlecht Lösungen wenn wir Pech haben und wir haben keine Chance zu den wilden gute Lösung zu kommen so ein anderes Beispiel disjunkte
Pfade sie haben wieder den Grafen der Dekan gerichtet oder und gerichtet sein und was sie wollen die also das ist hier bei uns in Graf sie müssen sich also denken dass es setzen Welten der gaben eines Grabens mit Noten kannten dran und was sie jetzt insbesondere haben sind Knoten Paare zu S 1 der Valens es 2 T 2 erst 3 die 3 und Sie wollen Pfade jeweils 10 die Pfade zu ziehen zwischen S und T so dass sich diese Pfade nicht berühren was Sie also beispielsweise von S 1 nach T 1 4 Einfahrt durchziehen von S 2 nach T 2 müssen Sie dann schon jeden Raum gehen und von S 3 nach T 3 können Sie dann stattdessen dann wieder gehen ja also Sie wollen Pfade durchziehen zwischen vorgegebenen Quoten Mengen und zwar nicht nur einen Pfad pro Knoten Paar S T sondern eine vorgegebene Anzahl von Fahrten sogar noch den also durchaus und da komplexes Problem das Problem taucht in in Logistik immer wieder auf wählen Sie verschiedene Dinge auf auch auch er vielleicht nicht materielle Dinge wie sie beispielsweise er ins ein Informant der Informationsübertragung durch verschiedene Kanäle und roten wollen so und das ist die Aufgabe eine gewisse das Joint mehr das konnte ich in Zielsetzung ist eine maximale Anzahl dieser Vater tatsächlich zu realisieren allgemein würde es nicht klappen diese Pfade alle zu realisieren sondern aber dann wollen wir sagen wir wollen um möglichst viele davon haben je nach Kontext macht es Sinn der Kanten des jungen teilzuhaben das heißt es keine die die Liebe linkes keine Zweck einen dürfen gemeine keine 2 Pfade dürfen gemeinsam bekannt oder sogar strenger keine 2 Pfade dürfen ein gemeinsam keinen Eick keinen gemeinsamen Knoten haben außer natürlich gemeinsamen Knoten klar wenn seine Fahne am selben wurden starten sollen zum selben den Konsolen haben Sie natürlich diese beiden entknoten gemeinsam deshalb sagt man da auch von internen sehen und ist schon und internen Knoten ist und Kapazitäten also das wäre noch die dritte Möglichkeit dass jede kann eine gewisse Aufnahmekapazität hat dass wenn eine keine Kapazität 3 hat dann heißt es es können 3 Pfade über diese Kante gehen also diese kann und darf in 3 Pfaden enthalten sein ja eine natürliche und Modellierung die Ihnen sicherlich den einen oder anderen Form in ähnlicher Form auch beispielsweise bei Telekommunikation wieder unterkommen wird so sie sehen hier ein
question mark Überschriften Eberhard vor ist schon ein paar auf question mark Köchen Mark warum weil das hier jetzt keine Beispiele sondern an die Beispiel ist wenn man versuchen Sie sich das mal vorzustellen wie könnte ja eine Nachbarschaft aus sehen eine Nachbarschaft immer noch handhaben kann das wird schon ziemlich schwierig ja was wir gesehen haben die Rede einen Vorrat teilweise vielleicht zu ersetzen durch einen anderen Fahrt oder ähnliches wenn wenn die Situation ist es so dass uns und schon n geparkt ist dann wird man da kaum noch Bewegungsfreiheit in irgendeine Richtung haben um jetzt solche Modifikation durchzuführen man wird mindestens dann vielleicht noch erzwingen müssen dass ein anderer Pfad der hier ursprünglich langgeht stattdessen auch das geändert werden muss das kann wieder weitere Änderungen von anderen Faden provozieren weil jetzt plötzlich nicht mehr des Jungen mit anderen fahren und so weiter und so fort also ich denke es ist klar und das hat auch die Erfahrung das das ist ein Beispiel dafür wo man mit Nachbarschafts basierten Verfahren nicht weiterkommt und deshalb sollte man wenn man sich mit so einer Problemstellung befasst da sollte man eher nach anderen Möglichkeiten suchen so und die einfachen Ideenstreit fort die an die einfache nachhaltigen Ideen wenn wir am Fahrrad oder Teile des Vaters verpasst oder ein paar fade ändern wollen das führt man wie gesagt ich weiter weil man dann kaum mag also um wirklich zu den Verbesserungen zu kommen dass man plötzlich einen Pfad ziehen kann wenn man vorher nicht sehen konnte und damit die Gesamtzahl der Vater erhöhen kann das würde einfach algorithmisch nicht mehr handhabbar das heißt also die Wahrscheinlichkeit ist groß dass man nach ein paar Schritten wo man einfach in der freien Wüste nahe schönen paar Pfade einfügen kann das anfängt dich zu werden ist die Wahrscheinlichkeit groß dass dann schon schlecht ist dass man nicht mehr weiterkommt mit dem Versuch mit dem lokaler Optimierung oder ähnlichem jetzt zur Verbesserung zu kommen so der jetzt überspringen wir dass dieses Fallbeispiel haben wir auch beim letzten Mal übersprungen zu noch algorithmische Problemstellung betrachtet haben da so aber Sie kriegen natürlich die Information auch nochmal rechtzeitig was wir alles und vor den übersprungen haben und selbstverständlich bedeutet übersprungen nicht Prüfungs- und Ort so ist betrachten wir noch ein paar Beispiele von exakt Nachbarschaften das heißt von Probleme algorithmisch Problemstellungen mit einer zugehörigen Nachbar Nachbarstadt schafft Struktur da drauf so dass diese Nachbarschaft in dieser Problemstellung tatsächlich sagte ist was bedeutet das diese Problemstellung sich tatsächlich durch dieses primitive lokale Suche Schema lösen lässt optimal gewesen ist konvexe
Programmierung R da will ich jetzt noch mal kurz an das Bild der was wir schon zweimal glaube ich dran halten haben so wie es aussieht haben wir ach das gerade das können Sie sich gut im eindimensionalen vorstellen sie haben konvexe Funktionen definiert über einer konvexen Menge so konvexe Mengen eindimensionales Intervall und sie wollen das globale Optimum finden Sie sehen einen war an einem Beispiel schon das globale Optimum ist entweder anmahnt wenn die Funktion monoton wachsend oder monoton fallen in im Bereich so dass es irgendwo genauso wie hier markiert und wenn sie irgendwo anfangen Nachbarschaft ist definiert hier auf dieser Folie und so würde man das eigentlich immer ungefähr machen alle Lösungen sind benachbart deren Distanz zur aktuellen Lösung einen bestimmten Wert überschreitet das heißt also eine gewisse Schrittweite nicht überschreitet so dass wir auf die Art und Weise wenn wir immer verbessernde Schritte machen dann automatisch zu einer Lösung kommen der kann sein dass wir hier kurz über die Lösung überspringen aber dann comma im wieder noch weiter wieder zurück mehr gibt es dazu jetzt nicht zu sagen das ist sozusagen das prototypische Beispiel für lokale Suche wurde es gut funktioniert und wenn Sie so eine schöne differenzierbare Funktion haben Sie hier dann kennen sie aus seiner dass dass man dass man eben den gravierenden auch in mehrdimensionalen den gravierenden berechnet und in der Rechnung Richtung geht man kleine Stücke um dem ob dem globalen Optimum näher zu kommen zwar nur ein kleine Stück damit man nicht damit meine ich ein großen Sprung über das globale Optimum hinweg macht und wieder zurück laufen muss so diese Nachbarschaftsbeziehungen 6 sagt ich sei nicht aus dem Bild einsichtig wenn Sie Lust haben nochmal ihre ihre Kompetenzen in Analysis also per Killers nochmal anzuwenden können Sie gerne versuchen das zu beweisen aber das ist natürlich nicht relevant für die Veranstaltung hier auch nicht wie die Prüfung so Mertsching dieses Beispiel hatten wir
auch beim letzten Mal sie erinnern sich wir haben gegeben ein und ungerichteten trafen so was zum Beispiel ich zeichne den Grafen wieder planar damit es übersichtlich ist es muss natürlich keine dann halt auf sein so und Mertsching besteht aus kannten seine Kantenlänge mit der Eigenschaft das keine 2 kannten in diesem Match einen entknoten gemeinsam haben so ich nehme an dieses er anhand dieser Zeichnung möchte ich 2 Begriffe kurz noch mal klären das hier ist eine Match eine Karte die zum Mädchen dazu gehört und der Knoten der zu keiner Mädchen kann sind Sie denn ist das ist ein X Trost wird Text so wie das hier auf der Folie definiert ist oder ein Fieber Text meistens man 6 baust ich denke diese Begrifflichkeiten sind intuitiv so jetzt machen wir mal vielleicht kleinsten hierhin also zunächst einmal bitte wir befassen wir uns mit Fragen die auf dieser Folie Elmenthaler genannt werden das heißt jeder Knoten ist maximal einmal auf diesem Pfad drauf ja es gibt keine Schlingen keine Zügel in diesen Pfad außer höchstens so wie hier wenn sich der ganze Fall einem ist so hat er nicht den das wird in diesem Bild hier da visualisiert das ist das Ziel eigentlich die für den die Hauptaussage dieses Bildes die Decken sind die Mädchen kannten die den sind nicht immer stärker kann und das sind die 4 Fälle wie ein Alter ne Thinkpads ein alter Nieren Abfahrt aus sehen kann nämlich gematcht ungemischt gemanagt und gemischte Mensch und dem Match gematcht also Anfang und Ende ist eine Mitsching kannte oder so wie hier Anfang und Ende ist eine nicht mit innig gemischte kannte aber auch jedes zweite ihr 2. kann das Gemisch oder so wie hier eine entkam des gematcht die andere nicht oder er schließlich zu einem Zügel und beachten Sie dass dieser Züge dann natürlich gerade länger haben muss es geht nicht anders wenn alternierend gematcht und gemanagt einmal um klappen soll dann muss der Züge sowie hier Länge 6 haben aber jedenfalls gerade Länge so das ist das was hier steht wir haben einen Fahrrads entweder ich eh jeder jeder mit der ungeraden Zahl indizierte kannte in der Reihenfolge gehört dazu und die andere nicht oder eben umgekehrt so
was ist die Nachbarschaftsbeziehungen hier die Nachbarschaftsbeziehungen K siegten bisschen kompliziert aus ist aber gar nicht so kompliziert sie sehen hier 2 verschiedene Mertsching zum selben Grafen um ein blaues und ein rotes Matching und was Sie hier sehen rechts ist die symmetrische Differenz was ist die symmetrische Vereins also genauergesagt was sie also mit ich differenziere sehen ist noch mal so komisch Grünen um klingelt das ist dieser einzelne Pfad der hier unten hochgeht und hier oben untergeht die symmetrische Differenz das sind die Kanten die in dem ein Match in sind aber nicht dem anderen die also entweder gut oder grün sind aber nicht beides ja andere Fälle sind beispielsweise diese kannte hier diesen keine von beiden drin ist daher auch nicht mehr so mild Indifferenz drin diese kann dir ganz oben diese vertikale in die Horizontale ist in beiden trennen es ist daher nicht Teil der symmetrischen Differenz Weise will zwischen Franz nur die sind in exakt einen der beiden Mädchens dran sind so also die seine Pfad ist diese hier ist die symmetrische Differenz und genau das ist die Definition der Nachbarschaft 2 Mertsching 10 benachbart wenn diese Mittel der sein so wie in diesem Beispiel um ein einzelner alternierender Pfad ist das heißt also die beiden Mädchen sind nicht weit auseinander so ähnlich wie beim TSB oh ja 2 kann ich sagen ersetzt haben diese beiden Mädchen sie nicht weit auseinander wie können auf diesem alternierenden Pfad die einen Kanten durch die anderen ersetzen das ist die Idee dabei so dass die Ehre und kommen dann von dem ein Mädchen zum anderen so die Behauptung ist dass
diese Nachbarschaftsbeziehung exakt ist was
bedeutet das das bedeutet wenn wir wir können so lokale Suche Schema anwenden wir haben ein gegebenes Mertsching so wie dieses hier M 1 oder meinetwegen auch wie 2 also die normalen 1 wir haben sollen gegen das Mädchen das unsere momentane aktuelle Lösung wenn das nicht die optimale Lösung ist wenn es kein globales Optimum ist immer noch nicht da sind wo wir hinkommen wollen sondern wenn es noch eine schlechte Lösung als sie global optimal ist dann sagt das diese Exaktheit wir finden einen alternierenden Pfad mit dem wir dieses Mädchen verbessernden indem wir in dem wir die kann auf dem Altane in ihren Fahrt die zu und damit die Menschen gehören rausschmeißen und die andern kann die nicht so sehr mit denen wir gehören reinschmeißen und das ist natürlich dann
besonders dieser 2. Fall hier relevant denn schauen Sie mal wenn wir wenn man sich jetzt schon Gedanken vorstellen Wir nehmen die Mädchen kannten jeweils raus auf diesen Pfad im Gesamt Grafen habe diesen einen Pfad als Teil des Grafen den in dicke Menschen kann alle raus aus dem mit Schinken und die Gemische stattdessen rein hier um damit sogar noch ein Verlust gemacht von 4 auf 3 runtergegangen auf dem Pfad insgesamt dass das mit 1 reduziert hier in Fall 3 und Fall 4 hat sich gar nichts geändert die Anzahl der Menschen kann es gleich blieben aber hier im Fall 2 aber jetzt momentan 3 könnten auf dem Fahrrad und wenn wir wenn wir das in entsprechenden Austausch machen haben wir 4 Kanten plötzlich und das heißt die Aussage ist wenn es wenn wir noch nicht beim globalen Optimum angekommen sind dann gibt es einen solchen Fall wie hier in Fall 2 der bei 2 x Post wird es ist bei 2 freien Knoten alte wird ja die als Endnoten hat und in diesem Sinne alternierend ist dass jeder zweite kann dann Imaging kann ist den gibt es dem müssen wir nur finden um wir den gefunden haben dann können wir entsprechend austauschen und haben die gesagt ein eine könnte mehr inzwischen bekommen das ist die Aussage wenn da steht die Nachbarschaft ist diese Nachbarschaft auf diesmal irdischen Problem ist exakt wie
beweist man das oder vielleicht mal als umgekehrt wie ihm gesagt habe ist immer noch nicht einen globalen Optimum angekommen sind dann wissen es gibt den Herrn Hofrat das kann man natürlich logisch umdrehen und sagen wenn es wenn es keine alternierenden Fahrt mehr gibt dann können wir uns hundertprozentig und felsenfest sicher sein dass die Lösung gewählt haben ein globales Optimum ist denn nach Definition von exakt ist sie das Lokal Optimum ein globales aufgenommen so warum ist diese Nachbarschaft jetzt exaktes kommt dieses böse Wort aus der Mathematik aber Sie sehen dass das bei uns hier etwas andere Form von Beweisen als etwa der Mathematik typischerweise dieses dort kennen gelernt haben weil und Sie nicht wirklich ein ein solches mathematisches Kalkül zur Verfügung steht was man könnte wenn man wollte alles wirklich genauso wie der klassische Mathematik in hat einmal damals Kalkül hineinpressen aber das versteht kein Mensch mehr das viel zu komplex haben Sie kennen das ja von dem von dem Thema in ich glauben in FTD 3 mit der und und so Sie wissen was ich damals damit meine Beweise zu versuchen wirklich mit einem Kalkül bekommen da comma nicht wirklich weit so was müssen wir beweisen wir müssen beweisen wenn eine melde nicht das globale Optimum ist wenn im 1 kein globales optimal ist wenn es also ein bessres gibt M 2 dann gibt es eine Alternative alternierenden Fahrt für M 1 der tatsächlich eine Verbesserung bringt das heißt wenn wir diese mittelschwerer also es den beiden nehmen was nichts anderes bedeute man sich das vielleicht nochmal Nachhinein klar die semitische der anzuschließen diesen Mädchen in diesem allen ihren bedeutet einfach alle kannten auswechseln auf diesem Pfad die Menschen zunichte Menschen die nicht die Menschen zum Menschen machen so es gibt ein alternierender Fahrt mit dem Bau 1 besser werden das müssen wir beweisen dass es den gibt so wir machen uns folgendes mal klar wenn wir die symmetrische Differenz ansehen dass sie sehen
uns das wirklich noch mal an jeder Knoten jeder einzelne Knoten den Grafen ist Incident zu höchstens einer blauen könnte und zugleich auch Incident zu höchstens einer roten kannte das heißt also was nicht passieren kann ist das die Zusammenhangs Komponenten der semitischen Differenz komplizierter sind als das was Sie hier in diesem Beispiel schon sehen sie können keine Verzweigung drin haben wir stellen sich vor es wäre Verzweigung an irgendeinem dieser Knoten der müsste Rohzahlen oder blau denn er rot ist wäre das rote kein Mädchen gewesen wenn Applaus für das doch kein Mädchen gewesen also es gibt keine Verzweigung hier die zusammen es kommen der semitischen Differenz sehen so aus potenziell vielleicht geschlossen als Züge von gerader Linie oder eben als offen Fahrt die zusammen das gebundene symmetrischen Mertsching sind sowie in diesem Bild gezeichnet Pfade disjunkte Vater die sich nicht berühren die sich in keiner einzigen Knoten berühren weil die es werden wenn dieser Fall dass sich berühren würden wir an dieser Stelle ein Widerspruch dazu entweder das ist ein Bild das Paar oder oder Mädchen ist so dieses Bild sage also die Wahrheit ja sie müssen wir aufpassen Bilder sind so ist suggestiv man kann sehr schnell von einem Bild überzeugt werden Opfern von denen die einfach nicht stimmen aber ich hoffe ich konnte Ihnen erneut an dass dieses Bild in diesem Aspekt tatsächlich stimmt so wenn das also alles tatsächlich Pfade und Züge sind alle nehmen Fahrt und Irene geschlossene Pfade Züge mehr auf den geschlossenen Fahrt ergibt sich kein Unterschied zwischen den beiden Menschen zusammen festgestellt dass wir gerade Anzahl das heißt ans Euro die unser blauen Kanten sind gleich comma vergessen betrachten wir die Fahne werden dieses 2
tatsächlich größer ist als ist am 1 dann kann die symmetrische Differenz nicht
nur aus Faden vom Fall eines von Fall zu 3 und von fallen 4 stehen sondern es muss mindestens eine Fahrt geben von Fall 2 sonst könnte er nicht dieses Mirtschink das N 2 eine größere Anzahl von kannten damals dieses mit ist das ist die Logik es muss mindestens also nochmal die symmetrische Differenz zerfällt in Pfade die so aussehen wie diese 4 Fälle zwangsläufig die auch noch Knoten ist und sind es muss mir so ein Fall vom Fall 2 geben sonst kann geht es nicht auf rechnerisch dass das zweite mit 2 größer so vor dem 1. Menschen das heißt es muss diesen alternierenden Pfad zu von 2 geben fertig da Beweise macht es muss es muss einen solchen verbesserten eine Frage gehen ich kann nicht so schwer oder sonne Beweisführung
falls sie damit nur müsse Schwierigkeiten haben oder wer wer von ihnen hat vielleicht noch müssen Schwierigkeiten mit diese Art von Beweisführung jetzt mit dem was wir jetzt hier gesagt
haben man darf sich ruhig melden ok was
können Sie jetzt verbalisieren was Ihr Problem ist okay dann werden wenn das nicht möglich ist hier Probleme konkret zu verbalisieren dann da das wäre mein Vorschlag dass es noch mal sich genau ansehen und den haben Sie so verstanden dass Sie können eine konkrete Frage formulieren wenn alles mit Aufnahmen klappt können ist natürlich nicht nur ansehen so auch anhören so lokale Suche
bedeutet also der Mann Maxim Jungs Problemen wir die Anzahl der Kanten maximieren und in jeder Schleife haben werden ob das aktuelle in dem lokalen Suche Schema das betrachtet haben habe man aktuelles mit China nackte Lösung besuchen suchen eine benachbarte Lösung die da die sich von der jetzigen Lösung da darin unterscheidet das sie größer ist das sind ist das immer mehr Menschen kann hat das heißt wir suchen einen alternierenden Pfad innerhalb im jetzigen das Mertsching M Stern der den Fall 2 entspricht eben er hatte der uns erlaube durch Austausch der kann zu einem Mädchen von größere Größe zu bekommen die nennt man auch manchmal im Stern ob man die eine Fahrt also bezogen auf dieses mit China gut eine historische Notiz ist das das das Ganze schon gefunden wurde lange vorher von einem reinen Grafen Theoretiker namens bernischen Franzose der der überhaupt nicht mit lokaler Suche so wird am Hut hat so aber der schon her schon herausgefunden hat er schon vorweg genommen hat im Jahr 19 57 das ist wissen Sie in Informatik Sinne verwandten Gebieten der Mathematik ist das uraltes ist Dinosaurier Zeitalter schon herausgefunden hat das das ein Märchen maximales genau dann wenn es keinen solchen argumentieren Fahrt mehr gibt die so das aber leider nicht die
ganze Geschichte zunächst mal scheint es einfach zu sein etwas Glanz also auf den ersten Blick scheint einfach zu sein an solchen Armenien war zu finden ja Sie sehen es hier unten sie sind wir nehmen uns irgend einen freien Knoten mehr Erfahrung und ex-post möglichst und gucken uns allen mit naher breiten Suche beispielsweise tiefen Suche wie weit wir kommen wenn jeder zweite kannte gematcht Match das also die erst und gematcht 2. gemanagt und so weit und sofort Sie sehen hier wenn wir immer hier um dann comma zuvor zu diesen freien Quoten und haben schon einen alter Nieren Fahrt gefunden wie gesehen haben wollen oder wenn wir hier lang gehen kommen zu diesem Knoten haben auch schon ein alter Nieren Fahrt gefunden wie wir wollen wir wenn wir hier alt aus solchen machen habe auf Fahrt aus 2 Karten 3 könnten gemacht und damit insgesamt die Anzahl der Mädchen kann erhöht oder sie gehen hier und kommen so auch zu diesem Knoten also sieht so aus als ob es überhaupt kein Problem wäre mit der normalen Grafen suche einen solchen alternierend Fahrt zu finden in gut also irgend eine Sache wie bereiten Suche oder sonst was aber wie dieses Beispiel hier zeigt muss es nicht muss ist die Sache leider ein bisschen komplizierter solch einfache Grafen Suche reicht nicht ja wenn Sie sich vorstellen so wie hier im rechten Bild an jetzt angedeutet dass das ist die Ausgangssituation sie sehen hier es gibt eine Möglichkeit das Mädchen zu verwässern indem wir von FIV aus los gehen und dann durch den Zügel durchgehen und dann hier weitergehen es gibt einen ob man die einen Pfad aber ist die Grafen so könnte zum Beispiel so durchgehen wenn wir beispielsweise breiten Suche haben das wir hier 4 in beide Richtungen verzweigen und dann hier weitergehen und damit es völlig unmöglich diesen einen alternierenden Fadenzieher noch gibt zur Verbesserung zu finden damit das haben unsere verbaut mit unserer breiten Suche oder mit diesen so kann sie es Beispiel entsprechend variieren würde würde genau zum sein Problemen führen so jetzt ein
Wort was man ungern in der Wissenschaft liest dann bei in Mali ist peinlicherweise liest man natürlich sonst auch also wenn es einen selbst betrifft ist man es natürlich auch sehr ungerne zu dieses diese Tatsache dass das nicht
funktioniert das normale Grafensohn so nicht funktioniert bis 10 Jahre lang unentdeckt
geblieben in dem Mitte der fünfziger Jahre her Theorien von der Arsch hat man sich das Problem zum 1. Mal genau hingeschaut hat dieses Resultat gesundes Altern jedenfalls gegen sehr 40 davon ausgegangen überhaupt kein Problem mit Grafen sofern man das 10 Jahre später also einen der weg Outlines Jack Erdmanns Außenbereich Algorithmik plötzlich aufgefahren Moment so einfach geht das nicht da gibt es ein Problem und er hat nicht nur das Problem gesehen sondern hat auch noch tatsächlich den entsprechenden wackerer und gemacht wir gefunden und dann tatsächlich sein komme Kreitner Algorithmus und wenn solche Fahrt zu kommen was ist Problemen das ist genau das was die harten Kanten von
unserer länger erzielte und seiner Länge so wie hier die sind das Problem Züge und gerade Dinge sind kein Problem das können Sie sich vorstellen wenn man da reinkommt in einzige gerade Linie in der Grafen suche so was hier ein bisschen größer so jeder zweite könnte es gemanagt und sie kommen zum Beispiel von mehr machen wir in unserer Kultur üblich von links nach rechts sie kommen so rein dann brauchen Sie und so weiter und hier haben Sie auf jeden Fall die Möglichkeit sind schnell genug hier das der nicht schneller sein kann wenn nicht zuvor kommen kann und hier können Sie dann entscheiden dass sie auf die Art und Weise weitergehen können von hier aus nicht ja eine ungerade länger es ist kann es ihm passieren je nachdem wo diese Kante ist erst mal sieht das bitten kleines bisschen anders aus so so zum Beispiel und Sie entscheiden sich zum Beispiel dafür hier sagen zu gehen und der Ausgang ist hier dann müssten Sie eigentlich hier Land zu gehen aber sie kommen da nicht hin weil sie sich dadurch dass sie in diese Richtung gibt auch gehen diese Möglichkeiten der Färber und da kommen sie nie wieder mit der andern Suche gehen wo sie eigentlich hin müssen das Problem Züge und Länge genannt eine
Blüte mir hat mein Kollege gesagt er hätte eine Anfrage aus der Biologie bekommen da gibt es einen klassischen Artikel passt Triest ein flaues Blase Angstschürung Passpflicht im Glas und und der der andere muss der Biologie bekommen von der er hat den Leuten das dann auch immer geschieht das Papier hatte nie wieder was von dem gehört offensichtlich hatten die Leute darunter dann was an muss sich etwas was anderes vorgestellt was da vor dem Papier drin sein könnte so dass die Situation dass die er wie sich sie hier rechts gezeichnet habe alle Kanten sind so weit es geht gemerkt dass das der übrig gebliebene Knoten links in dem Bild das auch gemanagt und wir kommen von links herein so was er gemacht hat der Bürger war und ist das können Sie am besten einen Bild hier unten sehen wenn man den wolle ja man man findet die natürlich mit breiten suche so 1 zu 1 Siedlung hat länger weil man von 2 Seiten in kommt und dann treffen sie sich in der Mitte wieder kann der breiten Suche wird er hier 3 Schritte machen hier 3 Schritte machen und dann merkt man plötzlich dass dass diese beiden Teile suchen jetzt eine eigene kannte gemeinsam haben wenn man das findet dann ersetzt man diesen ganzen Züge durch einen einzigen wurden macht weiter als wäre nichts geschehen berechnet dann mit Schinken und aus diesen Mertsching berechnen man hinterher wieder ein Ursprungs Matching also Sie sehen es ist dann doch auch mal ein bisschen komplizierter weitere Details brauchen wir hier nicht
zu betrachten am Ende werden diese schrägen Operation diese Reduktion der einzelnen Züge auf period auf einzelne Knoten natürlich wieder mal an dann werden wieder zurückgenommen und das Mädchen wird dann oft auf diese könnten die jetzt wieder zurück entstanden sind erweitert so damit sind wir durch mit dem Thema
Matching noch ein Beispiel über 2 exakt Nachbarschaften was in gewisser Weise ähnlich ist aber doch ein bisschen anders und dann gehen wir über zu oft dazu den heuristischen Algorithmen nämlich zu den Algorithmen in dem wir dieses lokale Suche Schema variieren auf verschiedene Arten und Weisen variieren um dieses Kapital Problemen Meldung schön was für was ist die
Frage nur bei und ranzigen Züge unserer Länge ja das muss ich noch mal überlegen also wie man das Problem doch hier auch auf in diesem Beispiel ich ich habe leider akustisch nicht genau verstanden und immer zeichnen ich war verstehst jetzt nicht aus dem schlechter fest das Bild falsch bezeichnete ist der kann natürlich nicht weitergehen der hat dann die Möglichkeit um dann zu gehen weil er 2 ungemischte kannten auftreten würde genau wünschen wenn sie wollen ja okay ja den gibt es aber keine keine alternierenden Pfad weil wenn ich hier lang geht sind die beiden Kanonen gemanagt und wenn ich ihren geht sind die beiden Kanonen gematcht ok gut ist doch schön dass wir so eine kleine familiäre Kuppelsender nur dass der Raum nicht so hoch kleinen Familie ist gut
also noch ein letztes Beispiel das hat so zum Beispiel das hat inzwischen das hat viele Anwendungen aber es hat inzwischen neue Anwendungen die damals bei der Abfassung dieser Folie noch gar nicht gab noch gar nichts stellen sich vor in einem Kommunikationsnetzwerk Peer-to-peer Netzwerk der oder sonst wie ja in der eine der Hauptwerk Lutz oder wenn nicht sogar der Würfel Hauptwerk wird inzwischen ist das Runterladen von Filmen nicht was sie da haben ist über eine gewisse Periode von 2. weckt dann einen Arzt der die State und das ist ideal also die Anforderungen sind dann für Nummer ein bisschen länger dauert also ich rede jetzt hier von von Spielfilmen die Anforderungen sie sind also über eine gewisse Zeitraum hinweg mehr oder weniger die gleichen nur wenn mal jemand dem neuesten Wochen Firmenunterlagen will und jemand anderes keine Filme herunterladen will ändern also wenn einer fertig ist ändern sich die Anforderung aber so im großen Ganzen sind sie 10. bis sich gleichbleibend und das kann man sich vorstellen also ich es ist dieses Beispiels ist nicht von mir vollständig durchdachtes diente Illustration ich weiß nicht also um mehr zu verstehen worum es eigentlich geht ich bin nicht sicher ob man das wirklich so anwenden würde aber diese Problemstellung hat mehr als genug Anwendungen beispielsweise in der Logistik also das ist kein akademisches Beispiel so also bei aber bleiben wir mal bei dem Thema Kommunikationsübertragung sie haben dann also eingerichteten darauf dass es ihr Kommunikationsnetzwerk Sicherheits- könnte vielleicht auch um gerichtet sein wenn das wenn das bilaterale Kanäle sind bleiben sicherheitshalber beim gerichteten Fall wir haben zumindest obere Kapazitäten in dem Beispiel jetzt machen unsere Kapazitäten dass ein Mindestmaß an Fluss durch geben muss er macht das keinen Sinn in anderen Fällen macht es durchaus Sinn nehmen wir das haben zu also für unser Beispiel mit der für Übertragung sind obere Kapazitäten wichtig dass natürlich jeder Comic Einzel Kommunikationskanal zwischen 2 Knoten in eine gewisse Bandbreite hat dieses von von dieser Kante unten Kostenfaktor es hat eine gewisse Kosten es kostet etwas eine Einheit Fluss durch diese eine Kante durch durch zu schicken so Sie haben 1 Balance wird für jeden Knoten der aussagt die also im Prinzip sagt der letztendlich aus von hier wird was wird was rein gepusht wird hier Strom floß rein gepusht an dieser Stelle dann ist das ein positiver Balance wird oder ich hier soll was rein kommen dann ist das ein negativer uns wert oder so sagen dieser belangt wird es nur das heißt hier soll nichts rein nicht raus da das Durchgangs Knoten der momentan wieder Anforderungen noch noch noch Jahres hat so ich sehe jetzt gerade das Beispiel vielleicht doch nicht so gut ist weil dieses illustrative Beispiele weil er natürlich immer das nur Punkt-zu-Punkt-Verbindungen sehe er die disjunkten Pfade Beispiel er für diesen Fall die wir vorhin hatten das wir dass wir immer von einem bis zu einem T das haben im Mai im Mai jeweils unterschiedliche Sachen haben also nehmen wir das Beispiel mal lieber wieder zurück was wir hier haben ist eine etwas andere Situation wir haben einen Fluss Wert eine 1 eine Art einer von materielle oder immaterielle Sachen die wir von den Knoten mit positiven Balance werden zu den Knoten mit negativen Balance werden durch das Netzwerk durchdrücken wollen in einem Steady State in einem also nicht jetzt kommen Einheit hier und dann eine Sekunde später kommenden bekommen 3 Einheiten dar oder so etwas sondern einen ein stabiler Zustand den Zeitlang zumindest stabil ist so was heißt das der Fluss wert auf jeder keiner kannte also es ist ein Wert auch auf jeder kannte der besagt wie viel dadurch fließt wie viel eine Menge dadurch fließt an Qualität also die Qualität dessen was durch ist interessiert uns nicht das kann Gas sollen in dem das Netzwerk das kein Wasser sollen in dem Wasser Netzwerk was auch immer die und sie sie haben wie gesagt in manchen Situation haben Sie die untere Schranken natürlich ist immer nur eine untere Schranke klar also negative Werte können sie nicht durch fließen lassen aber in manchen Situation ist auch ein anderer unter Schranke als als 0 0 sinnvoll und Oboe schauen wir sicherlich immer sinnvoll so was heißt dass dieses durch fließen lassen alle Sie haben das vielleicht oder vielleicht auch nicht je nachdem er die 2 schon mal gesehen Fluss Probleme der von den hat schon einige die 2 gesehen okay schon so die Mehrheit zu sein wir ziemlich große Mehrheit gut ist aber jetzt auch nichts Schwierigeres also am einfachsten ist es einmal der Fall dass hier ein der Balance wird eines Knotens nur dass das bedeutet für diesen Knoten diese Gleichung bedeutet für diese dann wenn die 0 steht das wäre das die Summe an dem Fluss die reingelegt ist ist identisch mit der Sonne Einfluss die ausgeht das ist heißt es ein Durchgangs Knoten Oh wie der Fluss wer da reinkommen in das Netzwerk wo wieder Fluss produziert wird und so noch Fluss abgegriffen wird reine Durchgangs Noten wenn hier ein positiver erstellt die dann ist also die Summe der Fluss währte die rausgehen aus diesen Knoten größer als die Summe der Fluss werde die reingehen das heißt da ist ein Knoten an dem würde BV Einheiten Fluss erzeugt in
Netzwerke eingespeist ja das ist bei also ist das dass das Thema so Solarstromerzeugung durch private Kunden von Stromanbietern ist zum Beispiel nicht vor wo inzwischen Hunderttausende glaube ich er einzelne Kunden nicht nur Solarstrom für sich selber produzieren sondern auch er mit mit mit politisch vorgegebenen Preisen auch ins ins Netz einspeisen können und auf der andern Seite sind Kurt privat kann natürlich normalerweise Konsumenten von Strom an also ein Privatkunde der keine so Solaranlage hat keine Photovoltaik zum einspeisen hat der hat hier einen negativen Wert einer der mit Solarenergie Überschüsse ein Spaß hat den positiven werdende und die Kraftwerke haben natürlich auch einen sehr großen positiven hat so wenn er negative wird steht allen positiver steht heißt das was rein geht von diesem Knoten Hauses mehr als was so was als das also das was rausgeht aus dem Bundes mehr als das was rein geht das ist netto 1 Einspeiser und wenn er negative wird gibt es das Natur ein Jahr als das Gegenteil von Einspeiser Nein aus Speise wird's wohl nicht heißen das der ein Verbraucher danke und das in diese floh Balance Künstler ist und was wir wollen ist also diese ganzen B Werte zu hinzubekommen einen Fluss zu haben der innerhalb des Kapazitäts- bereist diese Fluss Haltungsbedingungen alle erfüllt Finanzen Knoten und aber da kann es sehr potenziell viele verschiedene Lösungen geben die aber verschiedene Kosten Werte haben die Kosten werde wohl wir wieder wie üblich minimieren und das minimieren wie hier die so kosten wert auf wieder kann kosten wird pro durch fließende Einheit also müssen wir den Kosten wird pro durchlesen Einheit mit der Anzahl der durchfließenden Einheiten das gibt uns die Kosten wieder bekannte und aufsummiert über alle kannten er gibt uns das dem er den Gesamtkosten wird dafür bezahlen müssen um diesen Fluss dadurch fließen zu lassen so oft noch eine Nebenbemerkung in manchen Kontexten ist es sinnvoll die besten ich variieren zu lassen sondern einfach von vorne rein die bis auf 0 zu setzen alle das heißt also bei jedem Knoten muss rein gleich raus seine und solche Flüsse nennt man dann auch Strömungen deutschen im englischen Stil ich es so was ist jetzt des Nachbarschaftsbeziehungen hier wir betrachten jetzt fade wiesen den Gerichten Grafen wir betrachten jetzt schwache Pfade das was wir hier schwache fallen denn das in Frage die eben nicht wie normale immer nur vorwärts kannten haben wo man immer von einer Ecke er jede Kante benutzt in der Richtung dieser kannte sondern wo wir auch kannten ihn rückwärts nutzen können vom vom vom hätte neben ihrem also von von den Knoten aus wo kann den zeigt zum Klonen von der sie weg zeigt ja also einen Pfad kann dann durchaus so aussehen wir vielleicht mit 2 vorwärts könnten dann zwar rückwärts könnten dann wieder den Vorwärtsgang den Rückwärtsgang zur und vielleicht noch normale vor was könnte so dürfen fahre jetzt aus sehen hier in diesem Kontext das in Strafverfahren und die Nachbarschaftsbeziehungen ist ähnlich einfach Willi im Fall eben mit dem Mädchen 2 zulässige vieles die also diese ganzen Bedingung erfüllen Kapazitäts- bedingungsloser Haltungsbedingungen 2 zulässige Flüsse sind nach benachbart wenn sie sich auf einen solchen schwachen Cykel Elemente wie also kein Gluten Kommerz einmal vor auf einen solchen schwachen Zügel unterscheiden sie sehen dass hier die Unterschiede wenn wenn sie hier ihren Sie 2 Beispiel im selben Netzwerk von 2 verschiedenen Flüssen also hier sind auf den Karten immer die Fluss werde dieser kannten abgetragen die F Werte und wenn wir sehen wo unterscheiden sich diese beiden Flüsse dann sehen Sie hier zum Beispiel auf dieser kann unterscheiden sich ist einziges nur 2 10 wahrscheinlich auf der kann dich ist einziges 0 hier unterscheiden sich Essen nur lesen 1 und hier wahrscheinlich ist 2 3 das sind die 3 Kanten oder jeder einzelne erkannte unterscheiden sich diese beiden Flüsse um einen für einen der 1 einen Zähler Zufall dass es nur einen Zähler ist es könnte auch mehr als 1 Zähler sein um würden sie sich unterscheiden so und diese beiden da diese beiden Flüsse oder Ströme oder Strömungen in diesem ganz konkreten Fall diese beiden Strömungen sind deshalb benachbart erfüllen diese Nachbarschaftsbeziehung so was wir jetzt auch wieder sehen werden ähnlich wie bei mit ist dieser beiden nach weil diese beiden also diese Nachbarschaft die so definiert ist ist exakt und das heißt wiederum ganz konkret ich fange wieder mit einer beliebigen zulässigen Lösung an und umso eine optimale Lösung zu komm mach ich immer wieder das selbe ich suche mir von aktuellen Lösung einen solchen Züge so wie hier sie sehen dass es nun schwacher Züge ist weil 3 Kanten gehen so rum und eine Kante geht so rum ich suche mir so einfachen Züge der eine Verbesserung bieten kann in Bezug auf Kosten werden und ich verändere entlang dieses Hügels die Fluss Werte entsprechen und kommen zu einer besseren Lösung das mache ich so auf dass es nicht mehr geht und wenn wir bewiesen haben dass diese Nachbarschaft exakt das dann wissen wir auch wenn wir das so lange treiben bis es nicht mehr geht dann ist das Wasser man herausbekommen ein globales und nicht ein lokales Optimum
so das ist also das was wir erweisen wollen und sie sehen das ist ein bisschen komplizierter ist mir so vor 125 und der Beweis geht jetzt das wohl vor die 130 da muss ein bisschen mehr Arbeit reinstecken so nur in ihr als als Bemerkung dass was wir wovon wir reden lokale Suche schlimmer anwenden das hat einen Namen Literatur deren Werke der Zeit in Kenzingen also müssen wir suchen wir suchen einen Zügel wo die Kosten negativ sind die sowohl Kosten werden negativ sind weil mir dann denn den Fluss auf diesen Zirkel verändernd dann drückt das die Kosten runter wenn wir gleich sehen deshalb Nägel dass Heike kämpfen ringt heißt aber er den den denn diesen Züge zu kämpfen diesen Zirkel zu bearbeiten und dann ist das kein Unterschied mehr zur optimalen Lösung so wir brauchen also
jetzt ein bisschen Arbeit an dieser Stelle so wir haben so einen Züge zum elementaren Züge und der hat vorwärts und rückwärts kannten weil wer von schwachen Zügen ausgehen ich hatte so der Züge geben den Zügen Orientierung so und zum Beispiel dann ist das also nur vorwärts könnte das ist nur rückwärts könnte das wohl wird kann nur vorwärts vorwärts rückwärts vorwärts rückwärts so also zum Beispiel ist daher diese Karte hier aber es war vorwärts eine Frau könnte und diese kann hier ist aus aber Deckwort eine rückwärts könnte weil die und die und das es eben so ist werden Sie anders umgehen können versichert als ungerecht so was wollen wir tun wir wollen wir haben ja schon wir haben ist aktuelle Lösung close bracket Fluss Werte F wir wollen insbesondere solche Züge betrachten wo die vorwärts kann wobei auf der vorwärts kannte wenn das A 1 ist das mir nochmal A 2 wo auf der vorwärts kannte noch Luft nach oben ist zur Erhöhung der Fluss wird also f von A 1 kleiner Kapazität von 1 aber noch Luft nach oben und bei der rückwärts könnte wollen wir das ja noch Luft nach unten haben größer als der untere Anschlag weil wir das haben wenn wir diese Luft nach oben nach unten haben dann können wir folgendes machen wir können den Fluss um einen bestimmten wer den und aus müssen können wir den Fluss auf einfordert kannten erhöhen und um denselben wird auf ein rückwärts kannten vermindern und haben damit eine aus einer zulässigen lesen zu dass wir so gemacht denn woran wir damit aus einer zulässigen Lösung eine sie gelesen gemacht wenn Sie also die Kapazität Bedingungen sind eingehalten weil wir nur so viel den Fluss erhöhen und unverminderten dass wir hier keine Probleme haben wenn wie hier auf seiner vorwärts kannte den Fluss erhöhen dass die er dass wir natürlich nicht über diesen oberen Anschlag hinausgehen und das werden natürlich nicht über den unteren Anschlag hier hinausgehen auf der rückwärts kannte wurden was vermindern und wenn wir das das heißt die Kapazität bedienen sind eingehalten und die Fluss Haltungsbedingungen wie sieht es mit den aus statt gucken wir uns in einem frühen Quoten an auf diesem fort die Fluss Haltungsbedingungen also was gibt es für Möglichkeiten ja genau entweder zweimal vorwärts wenn das die Orientierung ist oder einmal vorwärts einmal rückwärts oder einmal rückwärts einmal vorwärts oder zweimal rückwärts das sind die 4 Möglichkeiten was andern als sind nun auf diesem Pfad sein kann auf diesen Züge und das haben wir hier viele Situationen hier haben wir um in gewissen wird Epsilon Dahlem-Dorf gelesen wird als beides vorwärts Karten sind hier erhöhen wir um die Welt erzählt hier vermindernde um ändert Epsilon war sollte das könnte ist hier denen wertet sollen hier erhöhen wir hier verwenden wir und hier von Männern wir das sind die 4 Situation die auftreten können und sie sehen in diesem Fall hier oben das ist die Summe der eingehenden und die Summe der ausgehenden um denselben wird erhöht worden das heißt also für die Fluss Erhaltungs- Gleichungen hier ändert sich
gar nichts diese Summe ist um Epson erhöht wollen diese Summe mit Flanell worden bleibt gleich ändere sich nichts das Ärzte wird einmal also diese Gesamtsumme addiert und einmal subtrahiert wird in beiden Summen immer positiv genommene negativ gesungen sondern das ist was passiert hier das in 2 Reihen kannten das heißt an der Summe der rausgehen kann ändert sich sowieso nichts weil die gar nicht ist und die Summe der reingehen könnten ändert sich auch nicht die Fluss Werte weil auf einer Karte würden Ärzte und erhöhte um um auf meinen kann der würde selber zu unvermindert das ändert sich dieser einer Gesamtsumme nichts das selbe hier im dritten Fall das sind 2 ausgehende Kanten auf der einen auf deine ausgehenden kannte wird der Fluss wird um als Lohn erhöht auf der andern ausgehenden kann der würde Fluss wird und es vermindert das heißt die Summe der reicht ausgehenden Fluss Werte ändert sich nicht in die Summe der reingehen sowieso nicht weil die gar nicht berührt es ist alle Knoten die reingehen sind ja gar nicht mehr betroffen und hier nochmal spiegelsymmetrisch dasselbe wie der erste Fall wären 2 rausgehen kannten nein schön einer als generellen ginge könnte bei beiden vermindern wir den Fluss Wert und erzielen das heißt beide Summen in den Kloberdanz kannst er werde Nummer 10 und reduziert und das ist da die eine Summe positiven wie andere Summen negativ eingeht geht es entlang also einmal negativen einmal positiv und das hebt sich entdeckt die Fluss Haltungsbedingungen die Flaubert uns ganz schön ins bleiben erhalten das ist der der ganze Algorithmus sie finden einen solchen Züge wer hier und so dass die und betrachten dabei beim finde diese Züge nur könnten wo es vorwärts noch Luft nach oben geht und rückwärts noch Luft nach unten geht also Sie suchen nicht nur der richtige Sie suchen sie besuchen ihr Grafen Suche jede Kante nicht nur in der Einrichtung sondern sie das noch eine Richtung zu aber nur eben dann wenn Luft noch um mit 10 Luft nach unten da war dann dann dann Veränderung sie um noch von ihm zu bestimmenden wird erzielt worden die Fluss Werte entlang dieses Zirkels und wenn sie den Fluss wird so Züge so gewählt haben dass die Summe der Kosten Werte negativ ist positiv genommen negativ genommen kosten wird negativ positiv genommen positiv genommen negativ genommen wenn in dem Sinne die Summe der Kosten werden negativ ist haben Sie Verbesserung der Kosten wird erreicht das ist der ganze Algorithmus setzt sich zusammen aus Bestandteil des Grafen suche genau gesagt er küßte sie Wege suchen nicht negative Züge suche was ja außer G 2 Energie zu schon mal kennen gelernt haben sollten negative diese Züge zu finden negativ bezüglich der Kosten wobei wir jeder kannte in beide Richtungen als Kandidaten haben in Fahrtrichtung Richtung immer die Kosten positiv und rückwärts Richtung in die Kosten negativ Algorithmen die wenn man fort und fort was wir können damit umgehen mit negativen kosten und können auch negative Züge finden Dijkstal kann es nicht aber wir brauchen das er nach dieser Stelle nicht Ecstasy einen sich auch nicht negative Kantenlängen so also das
ist exakt so ein solcher Züge sich viel geschrieben hat beschrieben habe wo die vorwärts Karten nicht am oberen Anschlag sind und ihre Glanz kann ich am und und Anschlag sind das ist ein auch mit ihren Abfahrt und wir betrachten noch nicht einzelne Pfade oder Zügel seine wir betrachten auch ein eine Menge von solchen Fragen und zügeln und dienen der Konsistenz war steht hier der was hier steht ist da ist will ich auch nochmal kurz vielleicht zeichnerisch andeuten wenn Sie so ein was steht was was dort steht ist wenn Sie 2 solche Züge haben der bekannte gemeinsam haben ja ich lasse mal jetzt die die Kanten Richtung weg weil sie ihre Waren sind und dieser Züge hier diese Orientierung dann muss dieser Zügel diese Orientierung haben und nicht die umgekehrte das heißt beider haben diese kannte in dieser Orientierung dran das ist das was konsistent sagt das also eine Kante in jedem einzelnen Züge Abfahrt indem sie drin sind die wir betrachten entweder vorwärts drin ist oder rückte oder in jedem einzelnen rückwärts dran ist das ist das Bild was das was letztendlich aus sagt was hier steht diese formale Bedingung ist so wir haben noch ein bisschen Arbeit zu tun sie sehen aber wir kommen langsam aber sicher in Richtung Foley 130 vor es ist also nicht allzu viel mehr zu tun ich denke wir noch nicht mehr alles heute schaffen das heißt also Sie haben die Chance bis zum nächsten Mal sich das was wir jetzt hier betrachten nochmal zu vergegenwärtigen um dann wenn wir das diesmal mal an diesen Beweis fortsetzen und dann und dann fit zu sein und das alles dann auch weiterhin gut verfolgen zu können so wie betrachten Flüsse der Einfachheit halber als Vektoren auf könnten das heißt also Viktor wo die wohl die Kanten eben die die Nummer 0 1 2 3 und so weiter haben also jeder kann dort einen Index in diesem Sektor das macht die Sache natürlich ein bisschen einfacher und es keine beschränke gemein hat so das was ich Ihnen gesagt habe hier dieser bereit dieser Fluss wird Änderungen um ein gewisses erzielen auf allen vorwärts kannten positiv und um das selbe Epsilon auf ein rückwärts kannten negativ dafür für nur noch eine kleine Schreibweise und Sprechweise 1 für sagen Ärzte Normalpegel P diese Cycle P ist genau diese Differenz ist das wir 1 plus Epsilon Fluss setzen auf jeden vorwärts könnt oder minus entlang setzen auf jeden auf wieder etwas kann auf den Hügel und alle anderen Karten im Graf Norden sind aber nicht in diesem Züge die sind nicht anders da ist die Änderung neue ja dieses R 4 dieses Athlon X P ist die Differenz von welche gesprochen habe von der zulässigen lösen ausgehen und zu einer unzulässigen Lösung zu kommen so mehr den Zügen in der negativ das habe ich schon vorweggenommen wenn eben wenn ich jetzt auch allen vorwärts kannten die Kosten positive auf summiere und den zudem auf allen rückwärts kannten die Kosten dieser kannten negativ auf summiere und die Gesamtsumme ist dann etwas Negatives mehr was nicht was es bedeutet als er als auch das dieser dieser Fluss erzielen meine P den man definiert haben insgesamt negativen Kosten hat ja sehen es hier noch meine Formeln 1 im wurde anderes als das was ich in meiner Tafel versucht habe und mündlich zu skizzieren das wir entlang eines solchen Zügels den Fluss um eine y verändern und das ist das natürlich würde was bringen wenn die Kosten so sind dass die Gesamtkosten Änderung die sich daraus ergibt negativ ist so dass wir also einen besseren 1 ein Fluss mit kleinerem kosten durch seine kleine Modifikationen herausbekommen
so ich glaube das wird jetzt langsam ein bisschen Sie das ist genau das ideale wenn meine nächsten Woche um 9 Uhr 50 auf mich ein bisschen gründlicher als heute nicht vom 10. wirklich etwas besser wenn wir pünktlich anfangen frisch ausgeholt mit den Frühstückskaffee und so weiter nicht vielleicht nur ganz kurz worauf das Ganze hinausläuft Sie können sich gerne das frühere 130 da schon mal zum bisschen bis erst mal
ansehen wird die kommt es im Prinzip dieselbe Logik wie bei Mädchen das war die mehr was Waberlohe G R Dirk und bei Mädchen die Hand seiner Jeans und wir haben festgestellt den Unterschied zwischen den beiden können wir sind Pfade und Züge und wenn dieses Mädchen nicht schlechter ist als das andere dann muss es mindestens 1 zu 1 vor dabei geben bei dem der Verbesserung haben das ist jetzt genau dieselbe Logik wieder wir haben 2 verschiedene Fluss wert Flüsse und wenn denn der eine besser ist als der andere also erst einmal der Unterschied zwischen beiden dass sich auch wieder einfach strukturell beschreiben der Unterschied zwischen 2 Flüssen der Fels in und wenn eine vielleicht besser ist als der andere dann muss der schlechtere einen da muss einer dieser Züge wenn wir den auf den auf Fluss drauf addieren dann muss eine Verbesserung bringen mindestens eine musste Verbesserung bringen sonst könnt ihr diese andere Lösung ich bei insgesamt besser sein es genau dieselbe Logik wie beim Mertsching und damit sie mir dann auch wieder dabei durch wir machen es noch bisschen Mende Teil beim nächsten Mal
und nach den abschließenden
Bemerkungen gehen wir endlich über zum richtigen rumspielen melde verschiedene Heuristiken was man so alles machen kann da hin und wie also dieses strenge lokale Suche Schema aufzubrechen zum Beispiel indem wir hin und wieder auch schritte erlauben die nicht zur Verbesserung für soll zu einer Verschlechterung dass wir beispielsweise Szenenbild in allen seinen oder die mehrere Schritte vorwärts geht und dann gucken auch Verschlechterung zulassen mal kucken was war das Beste auf diesem auf diesen kleinen weg und von da aus dann weitergehen das sind Prozet und von den Königen Dateityp verschiedene Male von verschiedenen Stellen aus lokale Suche laufen zu lassen oder und das wird uns am meisten beschäftigen noch beispielsweise Evolutionsstrategie gehen oder genetische Algorithmen dass eine ganze Population von zulässigen Lösungen haben die gegen eine Weltstadt Track miteinander treten bei mir weil wir zur Schotte gehen oder die sich in gewisser Weise fortpflanzen über genetischen Algorithmen so damit möchte ich für heute schließen mit diesen kleinen Ausblick und ungewöhnlich mich freuen Sie dann ist man wieder hier zu habe ich hoffe wir dann mit besseren funktionierende Technik beziehungsweise mit besser Kompetenz meinerseits als diese Kamera da angeht okay vielen Dank bitte
Feedback
hidden