Neighborhood-Based Approaches - Exact Neighborhoods / Heuristic Local-Search Techniques / Simulated Annealing

Video thumbnail (Frame 0) Video thumbnail (Frame 3191) Video thumbnail (Frame 10166) Video thumbnail (Frame 12347) Video thumbnail (Frame 23381) Video thumbnail (Frame 33825) Video thumbnail (Frame 39126) Video thumbnail (Frame 42084) Video thumbnail (Frame 48334) Video thumbnail (Frame 62322)
Video in TIB AV-Portal: Neighborhood-Based Approaches - Exact Neighborhoods / Heuristic Local-Search Techniques / Simulated Annealing

Formal Metadata

Title
Neighborhood-Based Approaches - Exact Neighborhoods / Heuristic Local-Search Techniques / Simulated Annealing
Title of Series
Part Number
3
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...
Neighbourhood (graph theory) Mathematics Relation <Mathematik> Set theory Set (mathematics) Arc (geometry) Rotation
Kante Stress (mechanics) Neighbourhood (graph theory) Slide rule Neighbourhood (graph theory) Maxima and minima Lösung <Mathematik> Function (mathematics) Relation <Mathematik> Supremum Set theory Optimum Divisor Summation Dynamic range Arc (geometry) Flux Directed graph Proof theory
Stress (mechanics) Neighbourhood (graph theory) Slide rule Relation <Mathematik> Set theory Dreizehn Negative number Summation Arc (geometry) Proof theory
Kante Stress (mechanics) Neighbourhood (graph theory) Mass flow rate Slide rule Feasibility study Set (mathematics) Equation Sign (mathematics) Implicit function theorem Helmholtz decomposition Relation <Mathematik> Set theory Optimum Negative number Integer Pairwise comparison Arc (geometry) Inductive reasoning Flux Proof theory
Kante Stress (mechanics) Greatest element Mass flow rate Feasibility study Set (mathematics) Kapazität <Mathematik> Mathematical induction Boom barrier Sign (mathematics) Mathematics Logic Forest Helmholtz decomposition Vertex (graph theory) Supremum Integer Pairwise comparison Arc (geometry) Inductive reasoning Flux Proof theory
Stress (mechanics) Neighbourhood (graph theory) Greatest element Mass flow rate Multiplizität <Mathematik> Bound state Approximation Number Mathematics Plane (geometry) Heuristic Proof theory Slide rule Compass (drafting) Optimization problem Lemma (mathematics) Neighbourhood (graph theory) Set (mathematics) Logic Helmholtz decomposition Relation <Mathematik> Optimum Heuristic Negative number Mathematical optimization Flux Local ring
Kante Random number Presentation of a group Direction (geometry) Lösung <Mathematik> Physical quantity Sequence Degree (graph theory) Degrees of freedom (physics and chemistry) Radical (chemistry) Strategy game Solution set Iteration Heuristic Physik Local ring Chain rule Presentation of a group Simulation Slide rule Linse Decision theory Optimum Iteration Mathematical optimization
Logical constant Kante Direction (geometry) Markov chain Lösung <Mathematik> Propositional formula Parameter (computer programming) Ext functor Function (mathematics) Exponential function Tieftemperatur Asymptote Mathematical structure Subset Physical quantity Independence (probability theory) Mathematics Plane (geometry) Matrix (mathematics) Radical (chemistry) Negative number Physik Summation Length Local ring Social class Proof theory Potential energy Logarithm Logical constant Process (computing) Euclidean vector Thermodynamics Laufzeit Low-energy house Infinity Maxima and minima Thermodynamic equilibrium Measurement Simulated annealing Connected space Probability theory Electric current Hohe Energie Computer programming Neighbourhood (graph theory) Statistics Zahl Complementarity Maxima and minima Limit (category theory) Infinity Equation Mortality rate Number Hausdorff space Energie Exponential function Degrees of freedom (physics and chemistry) Causality Iteration Well-formed formula Zusammenhang <Mathematik> Modulform Spacetime Integer Loop (music) Stochastic process Multiplication Axiom of choice Matching (graph theory) Slide rule Military base Physical law Exponentiation Umrechnung Dimensional analysis Counting Feasibility study Set (mathematics) Statistical physics Subset Film editing Logic Travelling salesman problem Network topology Quotient Iteration Optimum Object (grammar) Mathematical optimization Local ring
so genau sind die anderen immer so sein dass er verlängert werden an der TU Darmstadt so hallo allerseits sie haben
gesehen ich beherrschen wir gekommen und halb vorbereitet aber es dort trotzdem wieder so lange gut diesmal 1 Anfängerfehler dabei dass ich nicht drauf geachtet habe das vorne der Schutz weg war und ich mich gewundert habe dass viele kein Bild zu sehen war letztes Mal dass kein Bild zu sehen war lag daran das ist da tatsächlich noch irgendwo einen einen kleinen versteckten Schalter gibt den man nicht so ohne weiteres findet unter sich aus irgendwelchen Gründen umgeschaltet hat aber seit dem ich das weiß kann ich da natürlich immer schauen wenn es wenn es nicht angezeigt ist ob das jetzt klappt oder ob das jetzt nicht klappt aber es sieht es also aus das alles diesmal aufgezeichnet wird beim letzten Mal hat es keine Videoaufzeichnung gegeben da würde ich dann halt irgendwelche entsprechenden Bilderchen dich einer Tafel bezeichnet haben und ihn noch einmal nach wie vor ich muss mir noch überlegen wie ich das jetzt mache mit dem das Rendern der der der der Rohdaten die aufgenommen worden sind kostet ne Menge Zeit das muss jemand machen der die ganze Zeit am Bildschirm am Computer arbeitet und dass man so in dem mehr X X X immer anstößt und wieder ab ein Schritt weiter macht und so weiter das ist leider nicht meine Arbeit stehen aber steht es doch ein bisschen mehr rumlaufen nein das heißt sie muss jemand finden der die ganze Zeit am Bildschirm arbeitet er sowieso und der das in dem Herrn macht bis dahin muss ich Sie leider vertrösten das dass sich die Aufnahmen sind alle da aber das Rendern das kostet doch unglaublichen Aufwand so gibt es noch weitere sowieso tun von Ihrer Seite aus gut dann können wir ja zur Mathematik einsteigen ja das letzte Mal hier stehen geblieben bei diesem Thema in Koslow Sie erinnern sich vielleicht immer nochmal ganz kurz zurück zur Definition
hier sie haben ein Netzwerk also eingerichteten Grafen Sie haben auf jeder kannte und und obere Schranken wie viel Flusstour drauf sein soll statische Fluss das ist ändern sich nicht mehr Zeit es gibt auch die Variante dynamischer Fluss die ganzen algorithmischen ansetzt für statischen plus lassen sich dann in gewisser Weise auf den dynamischen fall übertragen deshalb macht es Sinn den statischen Fall zu betrachten und für jeden Knoten soll gelten die Summe der Fluss Werte die rausgehen kannten ausgeht aus diesen Knoten minus die Summe der Fluss Werte die in diesen Knoten reingehen soll einen gewissen vorgegebenen wertet genau treffen und was wir wollen was wir minimieren wollen ist auf jeder kann das noch Kosten drauf pro Fluss Einheit drüber geschickt wird und diese Kosten wollen wir minimieren unter allen möglichen zulässigen Flüssen die diese Eigenschaften haben jeder Fluss wird jeder kannte es zwischen unseren und obere Schranke und an jedem Knoten sind es gilt diese Balance Bedingung sollen wir wollen wir einen Film mit in er mit minimalen Kosten so berechnet und und wir haben schon die Nachbarschaft definiert der grause Kontext ist bevor wir zu den ganzen realistischen Algorithmen kommen betrachten wir uns noch diesen Fall als letzten Falle für dafür dass Nachbarschaften auch exakt sein können was bedeutet dass der dass die einfache lokale Suche die nichts aus tut also von einer Lösung zur nächsten zu einer benachbarten so springen so lange wie es dabei immer eine stetige echte Verbesserungen gibt dass diese Nachbarschaft Suche tatsächlich zu einem globalen Optimum findet die Definition von exakt ist ja gerade jedes lokale Optimum ist ein globales Optimum und die lokale Suche ist immer erst dann beendet wenn sie im lokalen Optimum ist das heißt keine benachbarte Lösung ist mehr ist mir besser gleich gut oder schlechter und Sie sehen hier 2 benachbarte Lösungen wir haben gesagt die Nachbarschaft zweifellosen benachbart wenn Sie in Ihre Voss wehrte sich nur in einem einzigen zücke unterscheiden die Fluss werde müssen sich immer in einem Zügel unterscheiden sie können sich nicht in die in einem fahrt oder so etwas unterscheiden weil wenn sie sich beispielsweise in einem mich geschlossenen Pfad unterscheiden würden ja so zum Beispiel der so so etwas ich sollte so etwas allgemeiner zeichnen sie ändern sich keine rückwärts kannten enthalten ja hier muss die Summe der ein und ausgehenden Kanten von diesen Knoten hier muss die muss diese Differenz reingehen BV sein wenn das jeder der Knoten W ist muss hier BW insgesamt sein so wenn 2 Flüsse sich nur auf diesem Pfad unterscheiden dann kann nicht bei beiden Flüssen hier bei Frau tatsächlich rauskommen also man ausgehende Summer eingehend denn es gibt nur ein Unterschied auf dieser Kante und nirgendwo sonst an diesen Knoten V das heißt einer von den beiden muss diese Bedingung für sehr verletzen dass da gleich zu mir bevor auskommt das Problem haben wir nicht wenn wir einen Zügel haben weil sich da alles dann das hat mir beim letzten Mal schon betrachtet weil sich da alles gegenseitig auf die wenn die beiden sich wenn 2 Flüsse sich wie in diesem Beispiel hier auf der Folie um genau genommen einen Zügel unterscheiden dann sorge dafür die eine Veränderung hier und die Arme Veränderung hier hier einwendet wenn die Union des Züge Sohn ist hier ein Plus hier ein Minus hielt sich genau auf beides sind tatsächlich Flüsse und halt und beide haben diese Bedingung die die Balance an eben dieser Knoten wie Sie das an diesem Beispiel hier auch noch mal nachvollziehen können so Behauptungen dass das ganz
exakt dass diese Nachbarschaft exaktes das bedeutet ganz konkret exakt
bedeutet ich suche einen negativen Zügel einen Züge bei dem die Kosten werden negativ sind die Summe der Kosten der negativ sind wobei ich genau das Fernwärmenetz Masche betrachtet schauen muss vorwärts kannten auf diesen Züge da zählen die Kosten positiv rückwärts kann auf diesen Zettel Sendekosten negativ denn ich werde ja auf diesem Züge bei rückwärts könnten wie hier vermindern im Fluss vermindern die meisten Menschen sagen an dieser Stelle nicht vermindern sondern erniedrigen den Fluss wird erniedrigen ich habe mir angewöhnt verminderten zu sagen weil erniedrigen doch der etwas andere Konnotation hat so wir erhöhen um einen gewissen Wert meinte fest Epsilon den Fluss auf dem vorwärts könnten vermindern ihn auf dem rückwärts kannten und das bedeutet auf den vorwärts kannten klingende Kosten dazu auf den rückwärts weil Wärmefluss drauf haben auf dem rückwärtsgewandten kriegen wir weniger Kosten weil wir weniger Fluss drauf haben deshalb suchen wir einen nach einem Züge von negativer länger wie man das macht kann sie aus der DDR 2 Stichworte wie beim Antwort weil war
so gesehen ist also man so dass in
Züge das ist die Idee wenn man keinen solchen negativen Züge hat weiß man definitif aus dieser Lermer hier
das der Fluss den man erreicht hat ein globales Optimum ist und solange man noch so negativen Züge ist macht man genau diese Operation um den Fluss wird um ein bisschen zu verbessern so wird die wir gehen
mal hierhin die einen vor den hatten wir schon mal gesehen das ist wieder alles von eine von diesen Sätzen oder dem Verlesen der Matadi ein schlagen mehr also wenn ich sowas zum 1. Mal sehe fühle ich mich erschlagen es gibt noch andere ich weiß nicht ich kann mich dunkel erinnern in dem ist Buch nachdem ich als Student an also es 2 hatte da gab es zum Beispiel den Satz über implizite Funktionen und der in kann sie den also im Wesentlichen sagte dass Ende von zu noch dann davon sehen können Sie gar nicht nach y auflösen können also wenn Sie implizit gegeben ist als eine alte Gleichung X irgendwas Y gleich 0 oder so und allein die Formulierung dieses Satzes im mehrdimensionalen hat mehr als die Hälfte der Buchseite ausgemacht man kann das als eine intellektuelle Herausforderung ansehen man kann sich auch davon schlagen lassen am besten erst erschlagen das und dann als in der Lektüre Frost Auswertung angeht so ich will sagen was hier steht was hier steht ist 2 zulässige Flüsse egal wie die auswählen deren Differenz lässt sich beschreiben durch eine Menge von Zyklen durch eine Menge von Zyklen wird in dieser Form wir haben Zyklen B 1 bis B K eine endliche Anzahl von Zyklen und ich kann aus F 1 F 2 basteln in dem ich auch wir jeden Medien dieser Züge Herrn immer mir dieses Epsilon hernehme was es auch gibt und genau diese Operation machen die auch beim letzten Mal gesagt haben auch wieder vor das kann des Zyklus um erzielen A 1 erhöhen den Fluss der der Höhlen auf wieder rückwärts kannte das Zyklus um etwa 1 vermindern und ich dass ich mit mit 1 man 1. 7. mache sondern mit allen von diesen dann bin ich am Ende bei F 2 angelangt die Aussage ist wenn ich von F 1 nach F 1 2 kommen will finde ich immer solche so eine Menge von Zyklen und solche Epsilon Werte so dass ich von F 1 oder 2 komme in dem ich nacheinander alle diese bei auf allen diesen Zyklen entsprechen den Fluss wird ändere das ist die der dieser dieser 2. dash hier nämlich auf den vorwärts kannten ist der Fluss wird das 9 plus F 2 größer als der Fluss wird des alten Flusses F 1 auf rückwärts kannten umgekehrt so dass sich also genau wenn ich genau das mache ja auf vorwärts Kanten eines Hügels erhöhen auf Begriff kannten 7 vermindern dass ich genau dann immer hier einen Schritt weiterkommen so noch eine kleine Folgerung daraus diese Züge sind konsistent in dem Sinne wie wir es letztes Mal kennen gelernt haben nämlich in dem Sinne das beide Zügel wenn die beide in dieser bekannte enthaltenden Hand halten Sie beide diese kannte entweder als vor was könnte oder sie enthalten sie beide als rückwärts in diesem Sinne konsistent das geht ja gar nicht anders wenn 2 Züge diese kannte als vorwärts kann die enthalten als als wenn die 1 das vor was Kanther enthält dann heißt es F 2 hat größeren wird als F 1 und wenn er aber Züge diese kann der 3. kann enthalten würde würde es heißen F zweier kleinerer wird als F 1 aber es beides zusammen geht nicht in hat F 2 größeren wert oder kleineren hat oder gleichen wird dann interessiert uns nicht so hier steht die teils die der aus aber das nix ist möchte ich hier nicht einfach stehen lassen als eine Übung sondern ich möchte Ihnen den Eindruck geben warum es tatsächlich so ist dass je 2 Flüsse sich um in so einer Menge von Zyklen nur unterscheidet und nicht anders doch wo ich dann dass man bisschen Platz wenn Sie wie geht das kann man algorithmisch beschreiben diesen Beweis der hier ausgelassen ist den ich aber nicht auslassen möchte sie nehmen sich jetzt mit kann der beispielsweise eine kann der wo der neue Fluss zu die sie hinwollen größeren wird hat als der alte Fluss von dem sie herkommen so dann markieren Sie hier im Plus dann finden Sie hier garantiert einen anderen kannte so oder anders rum bei der werden dass er bei der ganze dasselbe ist also wenn Sie da so eine vorwärts könnte sich nicht nur dieses Mal mit F 1 A 1 bekannte A 2 die so das F 2 von A 2 größer als F 2 von A 1 ist oder ich bevor ich das erklären warum das so sein muss nämlich noch den anderen fallen sie finden jetzt hier eine Karte A 3 die reingeht verloren F 2 A 3 kleiner 2 er 3 da habe ich das falsch also schön F 1 danke das 1 von A 3 ist warum finden Sie die weil hier bei diesen Knoten bei den eingehenden kannten hatte eine Fluss F 2 mehr wert der Rhein gilt als der andere Fluss F A R F 1 damit beide dieselbe Balance des haben können muss da noch irgendwo was anderes sein was ist wieder ausbalanciert ist muss mindestens eine Karte geben die es ausbalanciert und wenn es nur raus kann es dies ausbalanciert heißt es auch bei dieser Karte ist es so dass es zum größeren wird hat es F 1 oder wenn es hier eine Kante ist die reingeht die das ausbalanciert heißt es hier ist eine
kann bei der F 2 kleiner ist als F 1 das ist zwingend notwendig wenn wir annehmen dass das 2 Flüsse sind das heißt dass sie an jedem Knoten diesen selben erfüllen ausgehende Fluss minus rein in Davos gleicht dem der Welt Bilder dieses Knotens und diese Argumentation kann man immer weiter führen immer weiter solange vielleicht solange vielleicht zweimal hintereinander wo endet diese Argumentation sie muss Entenwal den endlichen Grafen haben wo endet sie die einzige Möglichkeit wo sie enden kann und wo es dann nicht mehr weitergeht ist hier das heißt wenn wir nur eine könnte am die hier auf den sich der Fluss unterscheidet ich habe jetzt hier größer genommen dieselbe Logik spiegelsymmetrisch geht natürlich auch umgekehrt wenn ein kleiner stehen würde wenn auch nur eine Kante da ist bei der sich die Fluss unterscheiden dann kann man gleich die ganze kann man gleichen weiß man es gibt gleichen ganzen Zyklus in dem die beiden sich unterscheiden anders geht es gar nicht so jetzt kann man gucken ich hier und plus 4 und plus 4 und minus 4 wieder im Plus und Minus aus jetzt gucken wir uns an wie viele könnten wir denen wie groß könnten wir dieses Ärzte sondern setzen maximal dass wir den Fluss das Fluss maximal weit verändern na ja da kommen sie Kapazitäten an für jede vorwärts könnte die Kapazität Ober Kapazitäten des aktuellen Fluss wird um so viel können das verhindern mehr nicht weil wir ja nicht über den U-Bahn-Anschlag hinausgehen dürfen auf der rückwärts kannte haben wir so viel Platz weil wir natürlich auch nicht über den unteren Anschlag ausgehen dürfen und wenn ich über alle diese Werte jetzt das Minimum Wälder und um diesen minimalen wert den Fluss L verändere anderen dass wir es dann passieren 2 Dinge also es mal zu ich nochmal ein die Orientierung das Zügels es sind 2 Dinge passiert 1. wir haben wir zu einem neuen Fluss gekommen ohne die ohne die oberen und und Schranken zu verletzen und zweitens davor das Minimum ist bei der keine wo das Minimum ist bei der Karte gibt es kein Unterschied mehr bei mir keine warten Sie mal nee was haben wir jetzt hier bei der kannte kannst K in genau dem noch ein period dabei ich muss es noch mal ein bisschen neu schreiben das ist noch ein wenig zu das war jetzt leicht falsch nur keine Sorge nur leicht falsch bei einer vorwärts könnte da können wir den Fluss erhöhen bis maximal da so wir wollen ja nicht über 11 2 hinausgehen das heißt mein mein Denkfehler eben wir wollen ich über F 2 hinausgehen bei rückwärts könnte können wir den Fluss vermindern um diesen wert weil wir auch nicht über F 2 hinausgehen wollen wir können natürlich nicht über die den oberen und dann Anschlag hinausgehen F 2 selber im Fluss innerhalb der Breite von unter das obere Schranke ist kann muss also nix passieren so jetzt jetzt nochmal die Argumentation es passieren 2 Dinge 1. wir sind wir haben wenn wir diesen Züge etwas veränderte die auf diese Art und Weise den Fluss verändert haben entlang dieses Hügels dann sind wir wieder zu einem zulässigen Fluss gekommen und das zweite was passiert doch wohl das Minimum angenommen wird gibt es keine Unterschiede mehr zwischen in der Zeit zwischen den neu konstruierten Fluss und und F 2 und da greift jetzt was hier unten steht bei ihren Datschen auf Art also mit einem in Fall zu holen über die Anzahl der Kanten bei denen sich die beiden Flüsse unterscheiden wir haben eine Kante weniger bei der sich mindestens eine Karte möglicherweise sogar mehr weil mir das Minimum an deren Kanten angenommen wurde nach Induktion Voraussetzung können wir jetzt diesen neuen Fluss denn wir haben auf diese Art und Weise mit ein paar Zyklen bis F 2 treiben und wir haben es den 19. gefunden den mir noch zusätzlich zum zunehmend zu der Menge und haben damit eine Menge von darf also als sei gefunden eine Menge von Zyklen von etwa als auch als er ist diese Logik mit der Deutschen zum klar geworden oder nicht so richtig es ist eine andere Art von verschiedenen wie Sie oder anderer Anwendungsbereich wie als wie sie es etwa in der Mathematik kennen gelernt haben da so typischer Anwendungsbereich Summenformel nicht da rechne man ein bisschen rum und und hat von der von N minus 1 auf einen Sohn Schritt gemacht das ist auch dieselbe Logik vollständige so nur in eine andere Situation die die Induktions- Behauptung die wir durchziehen wollen ist dass sich der Fluss eben das sich der Fluss E F 1 in F 2 transformieren ist über solche Züge falsche länger Sohn über die Anzahl der Kanten auf den die beiden sich unterscheiden Induktions- Anfang wenn die Anzahl der Karten 0 ist das heißt also wenn die beiden sich nicht unterscheiden das ist eine leere Menge von Zyklen trivialerweise führt Induktionsschritt wir gehen davon aus für alle Flüsse ja Netz im Unterschied auf K kannten für alle Flüsse mit weniger als Kalkanten gilt Induktion Voraussetzung dass sich tatsächlich der Unterschied in solchen Zyklen ausdrücken ist wir haben jetzt von F 1 2 K keinen Unterschied wir haben wir haben ein Züge gefunden haben das reduziert auf einem auf einem Fluss Unterschied von weniger als K könnten Induktion Voraussetzung da haben wir die Züge haben diesen Zügen mehr in dem jetzt eben gefunden haben fingen in zu und haben eine Transformation von F 1 nach F 2 mit Zügen gefunden es vielleicht müssen ungewöhnlich auf diese Art und Weise vollständige Induktion zu sehen aber in unserem Bereich ist es durch Algorithmik ist durchaus üblich so gut hier sehen Sie noch mal ein
Beispiel dafür an dem sie noch mal nachprüfen können dass das tatsächlich so ist wir Dietz die roten Zahlen hier um sind sehr genau die Differenzen zwischen den beiden Flüssen und wir gehen muss zum Beispiel dem blauen Zügel könnte sein dass uns im blauen sie das 1. hernehmen vorwärts kannte mit 2 mit Unterschied 2 vorwärts könnte mit unterschied 6 vorwärts mit Unterschied 2 und Minimum es 2 wenn wir entlang dieses Zirkels den Fluss wird um zu ändern gibt es keine Unterschiede mehr auf diesen beiden Karten und der Unterschied hier ist eine 4 geblieben so jetzt kann man sich beispielsweise einen anderen Züge Herrn ich hier unten der grüne oder Türkis oder was das ist 3 3 3 7 unterschied 3 das heißt wir für für verändern Fluss wird um 3 und was dann übrigbleibt sind hier noch mal 4 hier viele hier 4 und hier 4 passt und das Beispiel ist natürlich so konstruiert dass es passt aber der Satz sagte Michel dessen Beweise jetzt jetzt geziert habe der Satz sagt dass es immer passt bei eben Beispiel kann sich anstrengen wie sie wollen sie kriegen kein Beispiel in das nicht passt so Exaktheit das ist jetzt wieder das selbe wie beim letzten Mal als wir das bei Mädchen kennen gelernt haben wie wie war das bei Mirtschink wir haben gesehen 2 Mertsching unterscheiden sich in einer disjunkten Menge von Fragen und Zyklen und die Argumentation war wenn ein Mädchen jetzt besser ist als das anderer dann müssen Sie muss in diesen Unterschied auch Einfahrt sein bei dem bei dem es von da nach da zu einer Verbesserung kommt und genau das was wir gesucht haben genau das was die Nachbarschaft konstituiert ein alter Nieren und Pfad der zu einer Verbesserung führt und dieselbe Logik ist sie wieder die und das dieselbe Logik lässt sich auf viele andere Beispiele auch anwenden ich will jetzt hier nicht die Folie durchgehen sondern ich will es versuchen vielleicht der mündlichen wissen davon davon weg gehend und zu formulieren obwohl das selber aus sagt wir wissen jetzt der Unterschied zwischen 2 Flüssen lässt sich beschreiben also eine Menge von Zyklen jeweils mit Epsilon ja so für Flussänderung auf jeden dieser Züge so wenn dieser Fluss optimal ist es das ist auf der Folie F 2 und der andere Fluss ist schlechter ist nicht optimal das ist F 1 die Beine unterscheiden sich in Zyklen wenn der ein optimale sind andere nicht in eine bessere sondern nur schlechter da muss ist darunter einen Zyklus geben bei beide bei dem die Kosten werden negativ sind das heißt also solange wir tatsächlich einen Fluss in der Hand haben es ist F 1 auf der Folie der nicht optimal ist finden wir einen negativen Züge weil wenn es einen besseren Fluss gibt muss in der die Komposition der Differenz auch was ein negativer Züge dabei sein sie kann ich alle positiv oder gleich gut sein sonst wär das nicht das war er sich besser als andere und das ist auch schon mit ja auch schon wieder weg von der Mathematik
keine Sorge jetzt comma wieder zu zum heuristischen okay bisschen Mathematikern war heute wahrscheinlich doch noch mal wieder sehen aber eine Art von Mathematik gut wir verlassen ist das Thema exakte Nachbarschaften ich wollte Ihnen nur ein paar Einblicke geben ich wollte ihn auch zumuten bewusst und absichtlich zumuten diese das Wechselspiel zwischen konkreten Ebene einer konkreten Problemstellung wie man Koslow noch konkretere eben ein konkretes Beispiel aber noch abstrakte Ebene nämlich über Nachbarschaften von ob denn in Optimierungsproblem ganz abstrakt zu sprechen ich denke das ist eine Zumutung für die da vielleicht etwas ungewohnt ist ich will nicht sagen schwierig ist aber die viel bringt denn letztendlich in anderen Situationen vor wenn Sie jetzt nicht gerade nur primitive JavaScript Webapplikation schreibe oder so was sondern das anspruchsvolles dann werden sie immer wieder damit zu tun haben dass sie auf den verschiedenen Ebenen gleichzeitig denken müssen auch auf der auf so hoher Ebene wie wir sie hier einen oft genug so flossen Wort zum Sonntag immer weiter also die meisten Nachbarschaften bei bei der Problem stellen natürlich nicht exakt das wäre zu einfach man kann hoffen das der das diese einfach Algorithmus die lokale Suche trotzdem ein gutes Ergebnis liefert am Ende wird sie in meinem Lokal Optimum sei niemals automatisch einen globalen Optimum dieses Lokal Optimum kann aber beliebig schlecht sein gegenüber dem globalen Optimum jetzt wollen wir gucken wie kann man aus lokalen Optima fürchten das ist letztendlich die Idee heuristischen Algorithmen vor
so noch mal damit auf mögliche absolut klar ist mit lokalen und ein lokales Optimum kann beliebig schlecht sein man kann auch immer einfach Beispiele konstruieren wo die lokale optimal sämtliche lokaler Beamer außer dem globalen Optimum beliebig schlecht sein können also wir müssen da was anderen suchen was kann man tun das ist nun ganz kurze Überblick sozusagen der Fahrplan für den Rest dieses großen Abschnitt Nachbarschaft basierte suche was kann man alles tun um aus lokalen optimal zu flüchten oder zu vermeiden dass man das Album muss zu Ende ist wenn der wo lokales Optimum erreicht ist die 1. Möglichkeit die wir also es ist es ist betrachtet werden es sind Variationen bei dem man nicht jedes Mal unbedingt zu einer Lösung zur nächsten Lösung benachbarte Lösung geht die besser ist sondern hin und wieder um akzeptiert zu einer schlechteren Lösung zu kommen in der Hoffnung stellen sich das vor wie so so Berg und Tal sowieso eine schöne Gebirgslandschaft sie sind jetzt in zum Teil drinnen in so er in seinem 1. Sie so ein richtig schönes Tal vor was zwischen sie auf ausgewaschen so stelle sich vielleicht so gerichtlichen Gebirgssee vor sie sind irgendwo unten in dem in dem sie drin oder man denkt es ist ein bisschen zu so und zu kompliziert also denken Sie sich so eine richtig schöne Weine ausgewaschen durch einen durch einen eiszeitlichen See und aber es gibt natürlich denn auf der einen Seite Bereiche die beliebig hochgehen Viertausender direkt an dieser an diesen kleinen Tal aber auf der einen Seite gibt es vielleicht auch einen Pass der gar nicht so hoch ist da wo damals der eiszeitliche sie seinen Ablauf hatte und die Hoffnung ist wenn man hin und wieder mal auch erlaubt vorwärts zu gehen durch der Verschlechterung dass man dass man es schafft in Richtung von so einem Pass zu kommen und über den Pass über dann weiter zu kommen in der Hoffnung dass es da auf der anderen Seite tiefer runter geht so zweite Möglichkeit ist dass man nicht einmal vorwärts geht und erst eine ganze Kette Vorführung vorüberschritten macht ziemlich blindlings und dann guckt auf diese Kette von Fortschritten was ist jetzt was weiß das beste und dort wieder anfängt und dann wieder eine Kette von Fortschritten Einrichtung macht das dritte ist relativ einfach da ich auch gar nicht viel dazu sagen kann sie wird es hinaus stellen sich die SPD beispielsweise vor oder stellen Sie sich das Problem aus der Übungsaufgabe voraus Programmieraufgabe vor sie fangen an mit der zufälligen Lösung und wenn dann lokale Suche so wahrscheinlich kein gutes Ergebnis ist einmal machen wenn es eine Million mal machen zufällige Lösung generieren und lokale Suche an werden dann ist die Wahrscheinlichkeit schon sehr viel größer dass sie zu und die guten Lösung kommen weil die Warschauer mit großer Wahrscheinlichkeit haben Sie irgendwann mal in welche Zufalls anfangs Lösungen generiert ohne das zu wissen weil ja blindlings Vorgehen mit großer Wahrscheinlichkeit haben Sie aber anfangs Lösungen generiert die schon sehr gut sind und durch lokale Suche das natürlich ein kleines bisschen besser das dritte das wird uns ein bisschen mehr aufhalten das sind so Themen wie Evolution Strategien genetische Algorithmen aus der Biologie motiviert wo es darum geht dass verschiedene Lösungen im im Lösungsraum im Wettbewerb um dann stehen manche sterben andere duplizieren sich gerne in 2 Richtungen weiter oder sogar einen Schritt weiter die ist genetische Algorithmen die Simulationen voran geschlechtlicher sexueller Vermehrung das heißt 2 kommen zusammen und produziere nachkommen wobei das einmal Nische in Schema sein wird 2 kommen zusammen 2 Lösung kommt zusammen und aus diesen 2 Ösen wenn werden wieder 2 neue Lösung konstruiert in der Hoffnung dass diese zu einer Lösung besser sind als das Lösung so noch mal
hier was sicherlich auch schon ein bisher der Fall war Bemerkungen über die Präsentationen Überschrift das bedeutet eine eine Anmerkung dazu wie ich hier den Stoff aufbereitet wie wir Hermann Hahnemann ich Stoffe aufbereitet haben wir lassen viele Details in den Algorithmen offenes und über lokale Suche schon gesehen das heißt diese Details die können Sie auf vernünftige Art und Weise fühlen wie sie wollen ja die Krise Frieden Frieden Freiheits- gerungen wenn Sie also tatsächlich jetzt ein konkretes Problem konkreten ein Algorithmus konkret anwenden wollen eine konkrete Implementation ist also muss bauen wollen dann würden Sie diese Freiheitsgrade adäquat fühlen mit Inhalten 2. period natürlich also die die Literatur über solche Verfahren ist riesengroß ist ein unglaublich viele Verfahren entwickelt worden ich kann natürlich nicht hier ja eine erschöpfende Liste der von Algorithmen geben aber was immer ich bisher gesehen habe in der Literatur von Verfahren sollte ihnen in dieser Taxonomie wie wir sie hier wie viel sie einführen sollte sollten immer als Spezialfälle drin sein die gegenüber über alle nur ganz kurz drauf durchfliegt hat statt abbauen über wir berühren jeden die Sache nur kurz oh sind um sie in den Stand zu versetzen die gegebenenfalls hinterher wenn sie tatsächlich mal ein Algorithmen implementieren wollen für konkrete Problemstellungen das in der Lage sind sich die im Selbststudium sehr effizient die dafür notwendigen Informationen selbst an eigenen oft genug kann ich dazu sagen oft genug muss ich sagen dass inzwischen Wikipedia schon eine sehr gute und praktisch ausreichende Quelle ist also erst recht nicht im Sinne von Schulnote 4 sondern ausreichend wirklich im Sinne von danach kann man loslegen so ein Punkt aber dazu wenn sie in der Literatur schauen es gibt leider hier keine Sterne die wirkliche Standardisierung der Terminologie das heißt also Sie können nicht erwarten dass die Big sie müssen immer gucken ob die Begriffe wenn sie in einer am Neuköllner schauen ob die genau dasselbe aussagen wie wie hier oder wenn sie 2 einer können einer vergleichen ob deren Begrifflichkeiten dieselbe sind es ist leider so wie sehr wir haben in der Informatik in weiten das Seitenteile Formate keiner DIN-Norm für Begrifflichkeiten so der 1. Algorithmus Juhu endlich mal eine etwas kompliziertere Algorithmus sich für dieses ich immer um ein auf diesem einfachen lokalen Sucher 7 der der Niering auf gut deutsch simuliertes abkühlen das ist ein ich habe eben gesagt wir werden später Algorithmen betrachten die aus der Biologie motiviert sind wir betrachten hier einen 1. Algorithmus der aus der Physik motiviert ist aus Gründen die ich mindestens siebenmal gelesen mindestens 11 mal vergessen habe heißt auch Mitrópolis Algorithmus das sich aber sicherlich leicht Wikipedia also sonst wo nachschlagen wenn jemand wissen will warum der mit Mitrópolis Algorithmus heißt so was ist hier anders das ist ein Beispiel für den 1. Punkt von Variationen nämlich wir erlauben auch wenn Springer von einer Lösung zu einer bei dem es eine Verschlechterung gibt aber natürlich ein Gut nicht beliebig willkürlich sondern nach einem kontrollierten Schema zurück zunächst einmal bei lokaler Suche haben wir uns den benachbarten Elemente mindestens so lange angesehen bisher das bis wir einen einen verbessern das Element eine verbessernde Lösung in der Nachbarschaft gefunden haben ja das ist ein Beispiel für die Freiheitsgrade wir haben nicht gesagt bei der lokalen Suche wenn es mehrere Elemente gibt die Verbesserungen erlauben welches wir davon nehmen eines der Beispiele für die Freiheitsgrade wenn sie im konkreten Fall großen wir mit dem müssen sich entscheiden welches genommen wird das kann sein wenn Sie durch die Liste aller Nachbarn durchgehen die 1. Verbesserungsmöglichkeiten sie fin- oder sie gehen noch weiter und nehmen dann die beste Verbesserungsmöglichkeit also die wo oder Kosten wird sich am stärksten reduziert oder was auch immer hier geht es müssen anders vor wiesen auf einer Lösung und aus der Nachbarschaft wenn wir eine zufällige andere Lösung denken Sie ans TSP wieder das bedeutet wir wählen zufällig 2 von den Kanten um um diese 2 Ort um Station zu machen dich jetzt hier schon mehrfach vorgetragen habe und dies auch den vor den Finnen so also beim Beispiel TSB wenn wir uns zufällig 2 Kanten beim Beispiel die die die richtige zu platzieren wenn Sie zum Beispiel ihre Nachbarschaft Austausch möglich zwischen 2 in haben werden Sie vielleicht auch 2 oder wenn ihre Nachbarschaft auch die Möglichkeit einer von einer Linse also gegen den sie Einrichtung drehen dann wäre das vielleicht auch eine Möglichkeit die sich jetzt raus bekommen so wenn sie zufällig wählen dann ist es offen ist dieses benachbarte man besser ist die benachbarte Lösung besser als Lösung auf der sie geworden sind oder sich schlecht auf beides kann passieren so wenn die neue Lösungen besser ist machen wir sehr bei lokaler Suche sie gehen einfach hin und fertig eine Iteration vorbei nächste Iteration beginnt wenn hingegen dieser diese ausgewürfelt der zufällige der benachbarten Lösung nicht besser als wenn sie gleich oder schlechter ist dann machen wir ein Münzwurf aber nicht einen typischen Männer bestimmen zu Fifty-Fifty sondern mit einer genau überlegten Wahrscheinlichkeit dafür dass wir entweder sagen ja wir machen diesen Schritt vorwärts oder wir sagen nein wir verwerfen diese Lösung Verfall sowieso mal der beiden auf dieser auf der aktuellen Lösung beginnt kann Schritt vorwärts nächste Situation wir versuchen es noch mal eine zufällige Lösung und dass er wieder also wenn dieser Münzwurf dieser nicht verjähren Münzwurf keine Fifty-Fifty man Münzwurf wenn der rauskommt ja denn immer Schritt vorwärts und ansonsten bleiben wird er nächste tration fängt wieder von vorne an auf der immer noch auf Lösung für wir immer noch sind vor so werden wir wieder ein zufälliges Element mit aus und ganz normal das ist der 7. Schlemmer aber es wird kommen etwas wir müssen noch einiges hier einen an Details einen Film in dieses in dieses Skeletts also wie bei lokale Suche und bei allen anderen Verfahren hier vom man mit irgend der zulässigen Lösung auch ein Freiheitsgrad der wie Sie diese zufällige wie diese nein diese beliebige dass keine zufällige unbedingt diese beliebige Arbeit war diese beliebig gewählt der zulässige Lösung mit der Sie angefangen sie können versuchen zum Beispiel mit einer möglichst guten zulässigen Lösung schon an so waren oder sie können versuchen mit einer zum wirklich zufälligen will zur Lösung anzufangen und die sie um die geworfen haben die Erfahrung sagt dass das sehr häufig wirklich sinnvoll ist nicht zu versuchen die die 1. Lösung gut zu machen sondern dass es häufig wirklich sinnvoll ist die 1. Lösung mit der man das ganze startet wirklich zufällig aus meines Wissens gibt es dafür keine keine plausible Begründung sonst einfach Erfahrungssatz also wir sind hier im Spannungsfeld zwischen mathematisch logischen Argumentationen und Erfahrungen so solange wie ihr nächster Freiheitsgrad solange wir nicht der Meinung sind dass das jetzt zu Ende sein sollte was das genau heißt wenn wir dann noch weiter ausdifferenzieren werden wir also aus der Nachbarschaft des aktuellen Elements 1 eine eine neue Lösung Grundwehrdiener lösen besser ist ersetzen wie sie ansonsten machen wir diese Münzwurf und je nachdem was rauskommt ersetzen wir sie gehen ein Schritt weiter oder nicht und natürlich merken wir uns im Ganzen auf der wir auch Verschlechterung haben können merken wir uns auch immer welches die beste Lösung ist die wir bis dahin gesehen haben das comma bei der lokalen Suche nicht bei der lokalen Suche wird sie immer besser besser besser besser das heißt die letzte Lösung ist die beste wir brauchen es nicht zu merken aber hier da wir hier Verschlechterung haben macht es wenig Sinn die letzte Lösung als er geht es raus zu gehen so ist es besser sich immer die Lösung zwischen ich zu merken die beste Lösung die man gesehen hat auf dem Weg weil die letzte muss nicht unbedingt die beste sein so wie sie die
jetzt aus dieser dieser Münzwurf das habe ich hier noch noch mein Englisch war jetzt kommen viele bin also ein unfairer Münzwurf nicht Fifty-Fifty beide ist heißt's im engen englischen so viel wie tendenziös in eine Richtung gehen nicht nicht neutral solche Dinge ist essbar ist spielt in der Statistik große Rolle dieses Wort weil man immer natürlich gucken muss dass die dass die Dell das experimentelle Setting nicht da ist ist dass man da keine systematischen vereinbart sondern nur zufällige wirklich zufällige Fehler in den in den Messungen drin sind so was machen wir dann Namen wäre wenn natürlich 1 ein Zufallszahlengenerator 1 in Schaber ist glaube ich etwas März ein 1 zu an hat und haben brennt und kann sein ich Dunkel kann ich mich daran erinnere sich damit mal rum gespielt habe also jede und welche Programmiersprache hat das eingebaut an so genau 100 Zeilen Generator eingebaut ja was sie machen würden zum Beispiel wenn der Zufallszahlengenerator manche die vorhandenen reale Zahl zwischen 0 und 1 und wenn Sie sagen mit 80-prozentiger Wahrscheinlichkeit soll ein Jahr rauskommen dann würde man sagen wenn diese Zufallswahl zwischen 0 und 0 comma decimal 8 ist dann ist es ein Jahr Mini zu soll zwischen 0 comma decimal 8 und 1 ist und das ist ein Nein ähnliches gibt andere Zufallszahlengenerator die beispielsweise der beliebige natürliche zahlt in die wie eine positive ganze Zahl alle nicht mehr diese ganze Zahl zurückliefern dann müssten Sie dann halt das Max ins mit dem er bis 80 Prozent vom Arzt in ist dann ein Jahr und darüber hinaus ist dann ein und so weiter so und warum sie das so komisch aus mit Exponentialfunktionen die Antwort finden sich in der Formate die Antwort finden Sie in der Physik in der statistischen Physik inne Thermodynamik darauf will ich hier nicht eingehen allein auch das hat schon mal weiter als ich das selber gelesen habe das schon lange her dass Sabine wie alles längst wie auch wieder vergessen wir nehmen uns das einfach zur Kenntnis dass die Physik nahelegt im Zusammenhang mit mit abkühlt Prozessen dass die worauf ich noch zu sprechen kommen werde was die Analogie zu Artkel Prozessen ist das er ist sehen macht als Wahrscheinlichkeit für ein Jahr viel für diese für diese und beißt Konflikt kommen für den für diese unfaire Münzwurf das hier für einen Temperaturwert T größer 0 1 zu 1 er herzunehmen die Wahrscheinlichkeit für ein Jahr und die Wahrscheinlichkeit für ein Nein natürlich 1 minus diesen wert was man zunächst mal klarmachen sollten hierbei ist was da unten so ein bisschen eingequetscht ist da durch dieser zu dieser der abgezogen wert gesehen wir machen ein Münzwurf nun der Situation dass wenn der neue wird von S größer ist als der von er Stern das heißt also hier oben im Zähler steht was Negatives in einer was positives also es insgesamt das Argument Exponentialfunktionen negativ und Sie wissen wie die Exponentialfunktion negativen aussieht ja wenn sie ins Unendliche gehenden dann konnte geht es gegen neue und wenn sie zu 1 gehen an einer Stelle 1 auch da ist hatte Exponentialfunktionen wird er ist also Leute da für sie ist das alles vielleicht 2 Jahre her für mich es 20 Jahre her so wie sie die Exponentialfunktion aus in also irgendwie an sind eigentlich die ganzen wir schon noch da die im Laufe der Zeit reingefallen sind nee also die Fischer haben sie alle wieder rausgeholt aber die Kreide sind noch alle da so x-Achse y-Achse also hier ist er auch X und TSX und hier ist der Nullpunkt so hier ist die 1 und die Funktion sieht so aus hier also Asymptote die x-Achse und so damals wieder ich immer zu Hause okay ich weiß es nicht wie ich das diese nicht Reaktion zu werden habe aber ich werde sie mal als Zustimmung so das bedeutet in diesem Bereich im negativen Bereich ist der zwischen 0 und 1 das heißt es ist tatsächlich eine Wahrscheinlichkeit so wie diese Temperatur definieren und wir haben noch offengelassen wann das Ganze terminieren soll die Antwort auf beides nennt sich in der Literatur der Culling Skerdi und das heißt also die Planung die vorab Planung wie jetzt das Abkühlen sein soll T das ist die heißt ist kein Zufall wir sie haben es auf der letzten Folie gesehen auf der vorletzten Tag Vetternwirtschaft wie Temperatur so wie sie zum Cullens Gewebe aus ist es nicht eine Temperatur das entscheiden wichtig sondern Abkühlung im Laufe der Zeit nimmt die Temperatur ab das heißt also der Teddy Wert Durchlauf mehrere im Laufe der Zeit T 1 T 2 T 3 und so weiter und für jeden einzelnen dieser T hatte diese Temperaturwerte es dieser ganze Temperatur wird gilt für die gewisse Zeit Liegewiese einfach Iteration ist dass der Temperatur wert bis dann nach nach dieser anverwandelt Rationen nach diesen ne vielen jeder Nation dann die Temperatur Wiedereinstieg absinkt von TI auf die E-Plus 1 das ist das Schema das heißt also Sie zählen mit so und so vielen Male sonst Federation war das mit dem aktuellen Temperaturwert und sie haben ein Schema das sehen sagt okay nach zu viel malen werden welche noch zu sprechen kommen nach so und so vielen Male mit dieser Temperatur gehen wir 1 tiefer zunächst tieferen Temperaturen hat so Terminierung Terminierung ist natürlich ist auf jeden Fall erst mal dann wenn sämtliche Termine der Temperaturwerte durchlaufen sind und wenn der Motor wird die Sequenz die Anzahl der Iterationen die wir dafür festgelegt haben das heißt wir haben damit automatisch einen Termin musste dem es allerdings natürlich sehr groß setzen sollten vielleicht damit wir nicht überrascht sind es hat eine Sekunde gedauert aber es hat nichts gebracht sollte er umgekehrt sein es sollte eine gewisse längere Zeit dauern aber dafür dann auch was bringen zu aber man wird typischerweise auch weitere Abbruch Bedingungen noch einsetzen zum Beispiel also hier steht einmal märchenhafter fix immer der CPU Time und man wird wahrscheinlich doch eher der Realzeit als CPU-Zeit an wenn das man sagt ok ich will das Ergebnis auf jeden Fall morgen um 15 Uhr haben und das andere ist was man auch oft einsetzt dass man sagt Wendezeit Land endlich sich gar nichts geändert vielleicht wirklich nichts geändert hat oder nur ganz ganz wenig sich geändert hat er hat mir eine gewisse Anzahl Federation hinweg die man vorher festlegt dann soll der Algorithmus stoppen weil die nicht mehr glauben dass da noch was passieren wird weil es einfach nur Verschwendung von Rechenzeit ist oder bis weiser und was 0 unnötig lange warten auf das Ergebnis so das heißt also wenn der Kulling es geht zum Land gewählt worden ist wieder um länger als wir es eigentlich haben als sie eigentlich geduldigste Geduld haben mit dem Ablauf des Algorithmus dann können wir also in im unreifen Zustand den Algorithmus beenden und dann diese Lösung die beste Lösung die wir bisher bis dahin gesehen haben dann hernehmen was natürlich sicherlich nicht eine verbesserte Verbesserung darstellt Bezug auf Qualität der Lösung erstrangig ist hier nach meinem Kenntnisstand kann man das so im Englischen nicht schreiben wie man es im deutschen schreiben kann man müsste schon schon ein lohnender zu setzen das aller so waren tust ab der russische oder so was und das aus der Juso tust aber sowas aber was nicht einfach das ist das Top keine Garantie aber noch meinem dafür nach meinem Wissen und Verständnis ist es so dass es so wie es hier formuliert ist äußerst und gutes Englisch ist so Konvergenz was bringt das alles vielleicht nochmal zurück simuliertes abkühlen ja noch mal drauf zu sprechen kommen da gibt es noch eine Folie dafür simuliertes abkühlen stellen sich vor Sie haben einen aber 1 großen irgendwas extremer aufgeheiztes einen großen großes Los etwa mit Halos etwa einem einer Stahlfabrik diesen typisches Beispiel massiv aufgeheizt und das müssen Sie jetzt abkühlen und zwar mit Herz mit einer Zielsetzung mit ein Optimimus wird wenn Sie das Schock abkühlen dann ist die Struktur dieses Materials gerade bei metallischen Materialien etwa schlecht ja bei Abkühlung haben Sie ne Menge risse und und und Frakturen in ähnlich ist drin wenn im schlimmsten Fall klar zerreißt es sie sogar wenn sie zu schnell Schock aber das Material nicht stark genug ist um diesen diese Schock Kühlung auszuhalten was sie haben wollen damit eine gute was sie machen müssen damit eine gute Struktur haben viel für das Endergebnis ganz abgekühlt ist ist langsam abkühlen das hat sehr viel mit Optimierung in unserem Sinne zu tun weil wir reden hier von potentieller Energie er Sichtung aus dem Physikunterricht und was mit vom komischen Formen und man halte vorstellt mehr Energie stellte man halt da vor weil wenn sie abkühlen dieses dieses diese die potentielle Energie die springt lokal hoch und runter es fängt an sich müssen abzukühlen aber durch die durch die dynamischen Prozesse geht's auch mal wieder ein bisschen an der Stelle müssen wir ja so dass also wenn es die Gefahr läuft dass hier ein Riss entsteht dass Herr Kraler sicheres abkühlt es immer noch eine große Chance dabei das ist das durch die hohe Energie die die herrscht in diesen in diesem Festkörper ist dass das noch nochmal mal sich ändert und dieses festfrieren eine so dass es dann noch mal verhindert wird und ihm je höher die Temperatur ist am Anfang umso und so weniger Gefahr besteht und und wenn die Temperatur langsam abkühlt man muss sehr langsam abkühlen wenn sich langsam immer mehr dass das Material in gewisser Weise friert also 4 falsche physikalische Wort aber immer mehr immer mehr eben durch Abkühlung in feste Strukturen reingeht immer noch meine aus als einen zu hohen Potenz einem Lokal aus Einnahmen aus einer Situation aus also eine Konstellation mit zu hoher potentielle Energie für Risse und so was sind ist ein Auto Potenzen Energie ja der eine 1 der Struktur ist ein lokales Stelle an der sehr Opole Energie ist so wenn die Struktur homogen ist ist es die Obristen Energie geringer aus ist also immer wieder auf auch wenn zum schon kurz vor der Abkühlung ist für Enkelin Abkühlung ist immer noch eine gewisse Chance noch genug Energie dar das das ich aus besteht aus einem Level von hoher potentielle Energie rüber zu sprechen auf andere von niedrigerer Energie durch Energie die der durch die Energie die da ist die Möglichkeit eben mal die potentielle Energie man Schritt hochzubringen und dann wieder hoffentlich tiefer zu bringen so und das konvergiert geben 1 dieses langsame Abkühlen konvergiert gegen einen Material Platz wenn man lange langsam genug abkühlt denn ein Maria Klotz der sehr sehr homogene Struktur hat natürlich wird man die das Optimum haben es wird immer kleineres oder ähnliches in der Struktur noch geben aber man ist dann schon sehr nahe dran an diesem Ort und in Analogie zu diesen zu den thermodynamischen Beschreibungen dieses Konvergenz Verhaltens kann man auch hier Konvergenz beweisen Cops Deutsch wir betrachten jetzt eine stark Zusammenhänge Nachbarschaft sie haben sich aus der Gediz oder sonst wo her war statt zusammenhängt heißt das heißt sie kommen wenn es wieder als Grafen betrachten die zulässigen Lösungen sind Knoten und Nachbarschaftsbeziehungen sind gerichtete könnten von einem von einer Lösung zu einer benachbarten Lösung statt zusammenhängt heißt sie kommen auf Fahrten von jedem Knoten so eben zu dem anderen und zurück so wir betrachten wir wir gehen jetzt ein bisschen in in eine unrealistische Welt die wir nicht wirklich in dieser Form in einem Algorithmus passen können aber der Algorithmus ist nicht weit weg davon so zunächst einmal mit einem Isolation die Kamera durch konstant und jetzt wird unrealistisch wir haben unendlich viele Iteration ja für Konvergenz Betrachtung im Sinne der Annales im Sinne der Mathematik haben wir brauchen was unendlich ist und die Anzahl sollen ist also was passiert wenn man ein Rhythmus bis alle Ewigkeiten laufen lassen so ich hier gebe ich Ihnen im Jahr schlage ich erst meinen Fakt um die Ohren denn sie fressen müssen weil nicht immer ganz kurz ein 2. weil der Beweis dieses Faktum nicht in unsere Vorlesung reinpasst sollten Sie sich in in der Mathematik vertiefen Richtung Wahrscheinlichkeitstheorie dann werden Ihnen Markov-Ketten und ergo guten Theorie er guten Satz begegnen und wenn sie gut aufgepasst haben in dieser Vorlesung über stochastische Prozesse wahrscheinlich jetzt stochastische Prozesse dann wird es für sie ein Leichtes sein aus diesem er guten Satz als Spezialfall eines als Anwendungsfall dieses Faktum zu beweisen aber ist nicht unser Thema hier um das zu beweisen müssten wir eine ganze Menge um wahrscheinlichkeitstheoretischen aber hat ja einführen das sprengt die Veranstaltung im Glück für Sie wenn Sie nicht so viel mit Mitte was am Hut haben soll ja vorkommen so war steht hier so was ist dieser dieser Wert für den wir den grenzt für den werden wir mit bilden des indiziert mit der Temperatur die wir als fest beliebig aber fest vorgegeben haben blieb ich aber konstant und Laufindex K das ist die Wahrscheinlichkeit für eine ist für alle irgendwer ich eine ausgewählte beliebig ausgewählte Lösung S das in Schritt grauer die die Lösung ist auf der die suchen gerade steht ja also wenn K 1 Million ist beispielsweise und ich habe als es irgendeine Lösung beim TSB Herne mehr und eine Rundtour her dann ist PKT es die Wahrscheinlichkeit dafür dass in diesem einen für ein für kann gleich eine Million dass dieses dass diese Lösung in einem millionsten Schritt gerade die Lösung ist auf der wir gerade stehen so diese Wahrscheinlichkeit können wir nicht angeben weil allein schon deshalb weil sie hängt natürlich nur von etwas absehen von erstarrte Lösung ab ja stellen sich vor K gleich 1 statt Lösung ja aber die Lösung die wir als Staat uns gewählt haben hat Wahrscheinlichkeit 1 alle anderen Wahrscheinlichkeit 0 also können wir diese Wahrscheinlichkeit überhaupt nicht bereichen irgendwie aber wir können ganz rechnen das kein Widerspruch auch wenn mir diese Wahrscheinlichkeit nicht wissen oder andersrum gesagt egal wie die jetzt genau aussehen egal wo wir gestartet sind damit unserer solche welches sich statt Lösung war im Grenzfall wenn wir unendlich viele Schritte machen könnten ist diese Wahrscheinlichkeit dass es das aktuelle damit ist konvergiert gegen diesen Wert das ist ein typischer wert ist ein Ausdruck geteilt durch die Summe dieses Ausdrucks über alle zulässigen Lösungen so dass sich diese Werte 1 zu 1 aufsummieren ja was sie oben in um den Zähler haben haben Sie und in einer wieder wieso mir dass sie für alle zulässigen Lösung auf und wenn sie es betrachten wenn sie jetzt alle zulässigen Lösung hier betrachten das aufsummieren Einkommen insgesamt 1 raus bei dir und mir schon die Summe steht also vielleicht damit das keine kein Missverständnis da übrig bleibt was ich damit meine die Summe über alle über alle zulässigen Lösungen vor diesen Ausdruck links bis gleich die Summe einfach eingesetzt was dabei steht wächst also Ines will ich ich weiß die Frage sehr spät aber ist diese Schreibweise vertraut dass man nicht I hoch schreibt sondern Ext von irgendwas von X ist oder andere Schreibweise für war er hoch x sie vertraut gut Exzess voranmarschiert da oben minus OBE Fjords S durch die geteilt durch diese Summe es auch nein ich muss sitzen einer Laufindex werden habe ich doch noch gemacht die aus F und E noch mal von diesen werden Ex von minus Objekte vermischen von T durch T und was kommt dabei heraus das Endergebnis ist 1 es handelt sich also tatsächlich um Wahrscheinlichkeiten weil jeder einzelne ist ist größer 0 und zusammen ergeben sie 1 ich bitte um Verzeihung dass ich so ein bisschen komisch laufe ich habe mich ich habe am Wochenende die man beim Umzug geholfen und das sollte man sich in meinem Alter genau überlegen so also dass man erst mal als Wahrheit Herr Sahin einfach so das ist die Wahrheit period wenn Sie's nicht glauben gehen Sie sprechen Lehrveranstaltungen sie sehen ja und was für falsch und es geht so das interessanter Punkt ist jetzt der das war ein bisschen genau sehen was das heißt es ist ein bisschen komplizierter interessanter Punkt den wir dann tatsächlich noch beweisen können mit unseren mit unseren mathematischen Kompetenzen ist der wenn wir jetzt egal wie egal wie der Collins Gebühr genau aussieht wenn wir's gleichzeitig unendlich viele Schritte machen unendlich viele Iteration dieses Algorithmus machen und dabei nicht TV in Konstanz aussieht dann wollte konstant lassen sondern egal wie gegen 0 konservieren lassen dann ist die Aussage die das die das die Wahrscheinlichkeit dass die Suche auf einem optimalen auf eine optimale Lösung ist tendiert gegen 1 ich ist es andersrum formuliert wenn der eine nicht optimale Lösung haben dann geht die Wahrscheinlichkeit dafür dass das die aktuelle Lösung nach K Schritten ist für Karin unendlich unter gegen 0 die geht gegen 0 das heißt also was haben wir hier ja meine konvergiert wir haben ein hartes Konvergenz der und anhatte Konvergenz Aussage wenn wir schaffen würden den Algorithmus unendlich lange laufen zu lassen dann ist der mit Wahrscheinlichkeit 1 zum Zeitpunkt unendlich groß also sei immer das heißen mag ist der mit Wahrscheinlichkeit 1 das noch auf irgendwelchen optimale Lösung und kann mehr optimale Lösung geben das heißt er muss sich einfach auf einer stehen bleiben was bedeutet das jetzt für die Praxis das bedeutet für die Praxis wir müssen lange laufen lassen und dann sind wir schon sehr nahe dran an diesen schönen Ergebnisse wäre es natürlich nie erreichen wenn niemals ein solches Konvergenz der er gibt es 100-prozentig erreichen aber wie er wir kommen demnach das ich es weiter vertiefen aber zunächst mal kurz den Beweis es wirklich nicht so lang wir betrachten 2 zulässige Lösungen sie können sich vorstellen eines wieder optimal ja was nicht optimal allgemeine betrachten 2 zulässige Lösungen mit unterschiedlichen sie Funktions- werden S 1 ist besser als S 2 jetzt weggucken und diesen Quotienten an denn ja die noch mal zurück was Städten da das ist ich hier oben dieser Termin unter und das konstanter für fest T ist das ein konstanter wird hängt nicht ab von eigenen Einzellösungen das hängt ab von Einzellösung S das hier ist für jede Lösung es dass derselbe Wert das heißt wenn ich jetzt hier den Konzepten nehmen wir kürzlich das raus und übrig bleiben die beiden Zähler die beiden Männer sind identisch so für K gegen unendlich gesagt war eben die Aussage bei Festen Temperatur T E für K gegen unendlich kommen bei fester Tomato T das raus in 10. weil sich die daraus kürzen was identisch sind da der kurzen der beiden Zähler nach bekannt war Umrechner bekannter auf Umrechnungsformel kann ich den Quotienten aus 2 exponential ausdrücken zur zur Aidid zu einer bisschen was in diesem Fall soll zu Differenzen machen das ist das selbe das ist nicht an uns als war im Grunde ist die Gleichung der der Funktionen der Exponentialfunktion also was dahintersteht ist einfach hoch X plus Glos Y gleich wie hoch x ihr auch y oder sie Könnens auch durch auch so haben die hoch X minus y wenngleich er hoch X durch ihr auch y mehr ist das nicht was da angewandt wurde und wenn dieser Ausdruck hier hier oben der obere der obere der zu denen ist positiv positiven einmal was 0 der Zähler was ist in der der ist ist der ist der 1. kann feste Konstante größer 0 genau so wie es richtig der er genau der Zähler nur feste Konstante größer 0 für 2 gegebene zulässige Lösung ist der Zähler fest und wenn ich jetzt die Temperatur nicht mehr festhalte sondern gegen 0 gehen lasse würde der aus wird das Argument geht das Argument gegen unendlich und das Argument für dich und seiner Funktion gegen unendlich geht geht auch der Bundesrat Funktionswert gegen unendlich so dieser Konzern geht gegen unendlich wären 2 Wahrscheinlichkeiten die gegen und in deren kurze entgegen endlich geht was heißt das sie an 2 Zahlen diesen 2. zwischen 0 und 1 und etwa 10 geht gegen unendlich das bedeutet jetzt dass ich nicht dass ich es nicht verkehrt rum sage das bedeutet das was im stellt das kurze diese Wahrscheinlichkeit geht gegen 0 anders kann der Konzern zweier Wahrscheinlichkeit nicht unendlich werden und genau und nur wenn wenn wenn für die weniger gute Lösung die Wahrscheinlichkeit gegen 0 konvergiert dann funktioniert das so für jede Lösung S 2 die nicht optimal ist kann ich eine bessere Lösung finden und kann aus dieser Folie ableiten deren Wahrscheinlichkeit geht gegen 0 Wahrscheinlichkeit dass das die aktuelle die aktuelle betrachtete Lösung ist diese Argumentation funktioniert nur bei den optimale so nicht bei einer Lösung die nicht optimal sind funktioniert diese Argumentation auf dieser Folie und für alle diese können über weil damit beweisen dass die Wahrscheinlichkeit dass diese Lösung betrat er das an dieser Lösung vorbeikommen gegen 0 geht im Laufe dieses unendlich lang Algorithmus was nicht aus bedeutet als dass dann die Wahrscheinlichkeit für die optimale Lösung gegen 1 gehen muss dann irgendwo muss ja die Gesamtmasse eines noch bleiben sie kann nur auf den optimalen Lösung bleiben so der das ist das was ich eben gesagt habe interessante Bemerkung es ist man kann nicht einfach nur Schienen nicht nur schließen dass die dass die optimale Lösungen sehr wahrscheinlich werden wenn wir nur langsam genug abkürzen sondern von diesen kurz sind hier wenn sich die noch mal genau anschauen wenn das gegen unendlich geht dann die dann dann bedeutet das im Laufe des Algorithmus werden bessere Lösung immer wahrscheinlicher und schlechtere Lösung immer weniger wahrscheinlich also es nicht 0 1 Sache auf den optimalen ganz am Ende nach unendlich vielen Schritten auf den optimalen Lösung Wahrscheinlichkeit 1 auf die nicht optimalen Lösung Wahrscheinlichkeit 0 sondern schon im Verlauf des Algorithmus trennt sich das je besser eine Lösung ist umso größer ist die Wahrscheinlichkeit dass wir an ihr vorbeikommen so schön oder und wenn man sie meldet Erwin gut implementiert wofür man vielleicht auch aber ein bisschen Erfahrung braucht und dann oder viel Kreativität wenn man einmal herum spielt mit den ganzen verschiedenen Freiheitsgraden die wir hier betrachtet haben dann kann man und ich gute Lösung damit rauskriegen für viele verschiedene Arten von Problemstellungen ich will ein Beispiel nennen wo sie mündet in D-Link erfahrungsgemäß sehr sehr gut funktioniert und zwar ist das das Zeichnen eines Grafen in die Ebene wenn Sie einen Grafen visualisieren möchten dann haben wir erst mal mit den Grafen gegeben als eine Menge von Knoten und eine Menge von Karten wie von ungerichteten Grafen ja als leider Cents Matrix oder irgendetwas sie wollen aber den Grafen so sie wollen aber den Grafen so zeichnen das war übersichtlich ist und das war Sprecher Aussagekraft hat zum Beispiel wenn sie Sohn so so eine enge Zusammenhänge Komponente da haben dann sollen die beieinander sein so vielleicht wenn das wenn wenn es mehrere Komponenten sind die nicht minder zu tun haben soll der müssen getrennt sein was was Sie da machen können ist zu sagen ok sind wir haben sonst wir sind physikalische Vorstellung 2 Knoten die sich berühren die ziehen sich ein bisschen an 2 lohne sich nicht berühren die stoßen sich ein bisschen ab und auch Knoten kannte die nicht zusammengehören so wie hier so in diesem Schema da auch eine gewisse Abstoßung beziehungsweise 2 Kanten die nächsten einer zu tun haben ist auch eine gewisse Abstoßung oder letzter Punkt die Karten die von einem Knoten ausgehen sollten eine gewisse Abstoßungskraft haben damit sie sich möglichst gleichmäßig verteilen und Optimierungsprobleme das so mir vor dem wäre dann die Energie also ein energisches Gleichgewichte kriegen 1 1 1 1 eine Zeichnung in die Ebene von minimaler enthaltene Energie noch wo die Abstoßung so Anziehungskraft im Gleichgewicht sind das ist etwas was mit 10 bis 7 Läden liegen von der einen ich ein Beispiel dafür was mit 7 retteten die Dinge sehr sehr gut geht es gibt natürlich noch mehr Beispiel aber das sicherlich das anschaulichste so was wir noch nicht gesagt haben ist wie wir diesen Colleges gelte definieren dass wir frei darin wie wir das machen wollen es gibt es gibt ne ganze Menge mathematischer theoretische Arbeiten über 7 redet in die legen und alles was damit zu tun hat aber es gibt Arbeiten die aus den kann man schlussfolgern dass es eine gute Idee ist auf die Art und Weise so wie hier Dennis Collins gelte zu definieren hat Konstante c und jeder Temperatur ist eben C durch durch den 2 wird muss oder natürlich noch wird muss es egal von von von von dem aktuellen Schritt so was zum Beispiel das heißt also dass ich tatsächlich auch in jedem Spiel nähe von von der aktuellen Temperatur das das egal ist ob die L zweier Logarithmus und will muss oder irgendwas stehe folgt aus den wird man Gesetzen ja das würde ich gern noch mal kurz als Erinnerungen anbringen ich nutze jede Gelegenheit um den Studierenden nochmal klar zu machen dass der Logarithmus keine Schikane von Lehrern und von Professoren ist sondern eine sinnvolle Sache sie kennen sehr sehr G 2 ja Bäume haben logarithmische wir und ähnliches und so wenn wir hier den bei mir hier C durch lag kann von einer Basis haben dann will wir sie wissen der Logarithmus sollten das wissen mit 2 Logarithmen mit demselben Argument oder und unterschiedlichen Basen das ist unabhängig vom Arguments das ist nämlich genau das diese Konstante in der das Argument nicht mehr vorkommt das heißt also Sie können das ersetzen durch durch das mit Basis wobei Zielstrich gleicht sehe es muss da irgendwie das mit reinkommen wir um muss das reinkommen muss ich das Multiplizieren oder muss ich das dividieren Sie können von relaxed sitzend davon von ferne besser jetzt als ich überblicken haben Zielstrich gleich dass Sie mal um stets B unten steht also Logarithmus wenn ich das richtig gesehen habe so um wir es auch oft auch hier Wiedererinnerung gleich 1 durch Umdrehung Austausch von Basis und und Argument so können ruhig stehen bleiben so diese Tiefe von der hier gesprochen wird das ist das was ich von versucht hatte anschaulich zu sagen mit mit die mit dem Gebirgs Tal wenn so der der und der Punkte von dem Gebirgsteil die Tiefe ist sozusagen der DDR die der Höhenunterschied zudem zum zu den Pass über den man kommen kann ja ich habe so viel für so zu formulieren Sie haben zum Paar Viertausender darum aber sie haben zwischen den wird aus noch mal so den ein oder anderen Pass und die Tiefe ist der passt der also der den der niedrigste Pass mit dem er die Ministerin die sie erreichen müssen um auf diesen Geburtstag rauszukommen so die Minimaltemperatur sollte so hoch sein dass uns das immer maximal das sind Argumente aus der Mathematik auf die hier nicht weiter eingehen will die ihn nur einfach zur Kenntnis geben und wenn man das so macht dann kann man der Mathematik einige also Konvergenz raten nicht nur einfach feststellen ja das komme geht sondern auch etwas über aussagen wie schnell es konvergiert wobei diese Aussagen ich 1 konvergiert mitunter dann doch nur bedingt für die Praxis hilfreich sind zum Beispiel das manches TSB-Damen dann beweisen kann für diese 2 ob Nachbarschaft die wir betrachtet haben das wird zu n mit mindestens Wahrscheinlichkeit three fourths einmal mindestens den optimalen Zustand gesehen haben also optimal Rundtour nach einer gewissen Anzahl von Iterationen die aber leider exponentiell in der Anzahl der Knoten ist ja so sehen die Mathematikern etwas darüber aussagen aber das ist für die Praxis doch auch das noch eine Lücke dran das ist für die Praxis nur bedingt hilfreich so Diskussionen Zimmer leitete in den es populär wird häufig verwendet warum es ist leicht implementieren ja locker ist es ist kaum nicht kompliziertes implementieren als lokale Suche im Gegenteil wenn sich vor es ist vielleicht sogar einfacher sein damit ja sogar so sehr man sich lokale Suche müssen wir alle Nachbarn durchgehen bisher einen Nachbarn gefunden haben der eine Verbesserung erlaubt beißt in allen Dingen suchen wir uns zufällig Nachbarn aus wenn sagte gesungen zufällig 2 Kartenhaus beim im Beispiel so weil ein war in gewisser Hinsicht implementieren die einfache lokale Suche der Programmierer muss keine großen mathematischem Background haben man muss verstehen dass Ex wenn hier Ex spät dass er dann die Funktion Messpunkt Exper anzuwenden hat das ist alles wenn man das einem mathematischen Hintergrund nennen würde ist ganz Orden der vom Provider liefert ja für viele Problemstellungen und recht gute Lösungen und was meinen Sie überall beobachten kann so auch sicherlich in Informatik je je cooler der Name ist und so erfolgreicher ist und was er sich vorstellen sie haben Sie wollen Chef überzeugen davon dass sie die und die Methode verwenden wollen ich es vielleicht auch gar keinen vormaligen schon ich Mathematiker sagen wir mal vorsichtig ein Betriebswirt oder ähnliches sie stellen sich dieser Situation vor sie kommen einmal hin und schlagen vor in ihrer Präsentation ihrer Vorstands Präsentation ich schlage vor Algorithmus blablabla mitunter besonderes über Plus zu machen oder ich schlage vor Sie mal in die Länge zu machen wird vermutlich zu unterschiedlichen Reaktionen führen solche Dinge mehr solche psychologischen Effekte gibt es also immer dran denken wenn sie irgendwas entwickeln immer ein cooler Name dazu sie sehen ja in der in der Industrie gerade auch in der IT-Industrie wie sehr dieser Ratschlag beherzigt wird so das ist aber natürlich noch den natürlich ist immer nämlich nicht die Lösung aller Probleme länger hier über endlich schwere Probleme wie es die SPD bei den wir nicht hoffen können das ist mal der einst eine das ist das ist ein Algorithmus gibt der die wirklich löst einer vernünftigen Zeit wir haben ihren Konflikt zwischen Laufzeit und Qualität wir können früher abbrechen oder in Kürze und Collins werde machen müssen aber dann riskieren dann aber dass die Lösung die wir Männer rausbekommen schlechter ist und was durchaus ein Problem ist sie müssen damit Sie müssen den also ein eigenes Wissen wird in den tunen er sie müssen sie müssen Experimente laufen lassen auf realen Daten mit verschiedenen zcu links gelte es mit frischen Abbruch Kriterien und so weiter bis sie dann eine Lösung haben die vernünftig gut läuft die müssen aufpassen dass sie keine Obertönen machen dass sie jetzt nicht für die paar Beispiele die Sie die sie zum Lauf auf den sie es laufen lassen super gute Lösung haben aber wenn das nächste Beispiel kommt ist alles wieder Murks haben das ist durchaus ein Problem aber es ist ein handwerkliches Problem es ist nicht ein Kreativität Problem sich in ganz neuen Algorithmus aufzudecken und das ein entscheidender Unterschied so ich hatte schon kurz angedeutet was sie milde den gelingt ein wollen was das ist wir haben ja alles was sie drauf steht habe ich schon gesagt können wir abhaken so da müssen wir schon durch mit 7 werden denn es gibt also man könnte locker die ganze Vorlesungsreihe hier ein Semester lang nur mit sie werde in den Gestalten insbeson- mit den ganzen mathematischen Arbeiten dazu aber das ist nicht in dieser Vorlesung wir gehen wir zum nächsten Über-Ich hat der heute am Anfang gesagt auf jeder bei jedem Algorithmus brieflich Touch Toppan kommt immer nur kurz an so jetzt kommen und zwar eine ganze Klasse von lokalen Suchalgorithmen an bei denen wir zusätzlich zur Nachbarschaft eine weitere Struktur erwarten die sehr sehr häufig gegeben ist nicht immer aber sehr sehr häufig und aus dieser Struktur leitet sich auch die Nachbarschaft ab so Beispiel denken Sie an die SPD wieder als ein schönes Beispiel haben die Features von den hier auf dieser Folie die Rede ist sind die einzelnen kannten die innerhalb und Tod und sein können oder nicht eine Rundtour ist eine bestimmte Menge von kannten nicht jeder kann es eine wenn ich dir kann man seine aber bestimmte kann man sehen und vor allem das und die Kanten sind die Features eine endliche Grundmenge die Menge der kann im Falle der SPD von Features und die zulässigen Lösungen sind Teilmengen dieser Grund mehr Selektions- Auswahlen davon genau das ist es ja wenn oder konstruieren wir wählen aus welche kann dazu gehören welche nicht Beispiele folgen gleich gerne können wir viel tschüss identifizieren mit Dimensionen im Raum wenn sie werden Sie wenn Sie aber wenn ihre Lösungen 0 1 Vektoren sind der Länge n da haben Sie n Dimension aber sie haben n Features nämlich sie werden das Feature aus bei einer Lösung die einen enden die 1 0 1 wirkte der Länge n ist also der sie Lösung die so aussieht können Sie sagen die mit Wert 1 sind die Features die ausgewählt wurden die mehr wert 0 sind die Features die nicht ausgewählt worden weder von Features und nicht von Dimensionen so Beispiele das 1. Beispiel hat mir schon die SPD ich hoffe mal dass das Beispiel genau dem entspricht was ich auch gesagt habe genau die für die Viecher sind ich habe von keinem gesprochen aber allgemein die Features sind die Paare I J die aufeinander folgen können so was das Matching Problem wir wollen eine Teilmenge der Gesamt kann man über bestimmen immer mitschwingt und damit sind natürlich die kannten das Eingabe trafen sie Features ZK wollen ist ein Beispiel was wir jetzt noch nicht betrachtet haben bisher wir haben wir haben eine eine Grundmenge von welche Art und wir haben Teilmengen auf dieser Grund man her also meine Intuition zur Z Karin ist immer so meinen die zu uns das hat Karin die sie haben diese Grundmenge so ohne hier endlich und sie haben Teilmengen die vielleicht so aus sehen die sich überlappen können beliebig viele beliebig Bilder natürlich im Allgemeinen will als dass man sie so mit schönen Klingelzeichen könnte aber das würde natürlich bisschen habe ich so was sie wollen ist eine Auswahl also wirklich alles überdeckt eine Auswahl von solchen möglichst wenige davon so dass jedes Element der Grundmenge in mindestens einem man diese Auswahl ist und Sie wollen die Anzahl der ausgewählten Mengen minimieren das kommt diese Problemstellung komme zum Beispiel der Lehre Gestik oft vor die die Gründe Mengen sind sind beispielsweise Versorgungs- Station Versorgungsmöglichkeiten und alle Elemente die von dieser nein die die Grundmenge sind Kunden oder so etwas ein der eine solche kleine Teilmenge ist eine Versorgungsmöglichkeit und diese Menge besteht aus den Kunde von aus versorgt werden können und sie wollen mit möglichst wenigen Versorgungsmöglichkeiten alle Kunden erreichen können so nur als grobe Idee warum diese Problemstellung in der Logistik eine große Rolle spielt so und das kann man natürlich noch weiter spielen ja die einzeln Versorgungsmöglichkeiten kann unterschiedlich teuer sein dann möchte man nicht die Anzahl sondern die Gesamtkosten natürlich es ändert sich aber nichts an an dem Buch über sprechen so die Elemente diese also die verschiedene Versorgungsmöglichkeiten die verschiedenen Teilmengen wären dann die Features Macs Skat willst ist das ein Plus von für und da ja wir haben jetzt ungerichteten Grafen mäht mit Kanten Gerichten ist ja nichts neues nicht das hat mir das schon mal um richten damit könnten richten in diesem Beispiel der oben habe er hat jede keine Gewicht eines aber allgemein muss nicht kann nicht alles haben hat Gewicht eines natürlich damit sie damit sie die das Gericht eine schwer zuvor durch Zählen der bekannten bekommen können so alles jede Teilmenge der Knoten Menge ist ein zulässiger Output und was wir wollen ist die Sonne der kalten Gerichte oder wir wollen eine eine Teilmenge finden so dass die Summe der Gerichte der kannten die von dieser Teilmenge rausgehen in der in die Komplement Menge Wasser wir die maximieren und dass das spielt in verschiedenen Kontexten oder auch wieder in der Logistik das ist da wo es am am teuersten ist dass man dann Schnitt macht und die beiden Teile jeweils für sich betrachtet spielt auch nicht etwa in der Verdrahtung von Mikrochips eine Rolle da werden solche Max Card Sachen auf solche G 3 Dinge seien die der Grafen angewandt sehr häufig angewandt was ich hier die Features das sind die Knoten ja die eine Lösung besteht aus diesen Knoten der mir noch Beispiele aber wir haben es auch langsam die Zeit 1 habe angefangen man 50 aber theoretisch angefangen aber so ganz aber ich glaube wir haben es die 90 Minuten in uns oder okay sie sehen aber zunächst einmal wir haben noch ein paar Beispiele nur noch ein Beispiel aber okay sie sehen daran dass das was jetzt keine dramatische Forderung an eine Problemstellung ist das das sie Viecher basiert ist das heißt dass er die zulässigen Lösungen Features aus einer grundlegenden endlichen Feature Menge ist und das ist eine sehr natürliche sehr häufig vor dem Situation ist und wir werden beim nächsten Mal nachdem wir dann das letzte Beispiel noch durchgegangen sind Algorithmen sehen die diese Feature Struktur also Nachbarschaft versieht Algorithmen wo die Nachbarschaft auf diese für die Struktur basiert und wo diese Algorithmen dann diese viel spezifische Feature Struktur stark ausnutzen so dann möchte ich für heute enden und wünsche Ihnen noch einen schönen Tag und noch eine schöne 2. Wochenhälfte
Loading...
Feedback
hidden