Descision-Based Approaches - Descision Trees / Preprocessing / Cutting Strategies / Branch and Bound

Video thumbnail (Frame 0) Video thumbnail (Frame 14534) Video thumbnail (Frame 21419) Video thumbnail (Frame 30472) Video thumbnail (Frame 37244) Video thumbnail (Frame 46687) Video thumbnail (Frame 56506) Video thumbnail (Frame 66325) Video thumbnail (Frame 68744) Video thumbnail (Frame 81870) Video thumbnail (Frame 94996) Video thumbnail (Frame 107199) Video thumbnail (Frame 119402)
Video in TIB AV-Portal: Descision-Based Approaches - Descision Trees / Preprocessing / Cutting Strategies / Branch and Bound

Formal Metadata

Title
Descision-Based Approaches - Descision Trees / Preprocessing / Cutting Strategies / Branch and Bound
Title of Series
Part Number
7
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...
Kante Root Point (geometry) Constraint (mathematics) Lösung <Mathematik> Variable (mathematics) Hausdorff space Plane (geometry) Solution set Network topology Partition of a set Physikalisches Phänomen Decision tree learning Series (mathematics) Slide rule Raum <Mathematik> Decision theory Neighbourhood (graph theory) Wurzelbaum Laufzeit Feasibility study Two-dimensional space Variable (mathematics) Subset Partition (number theory) Solution set Root Film editing Network topology Helmholtz decomposition Set theory
Raum <Mathematik> Höhe Decision theory Wurzelbaum Feasibility study Lösung <Mathematik> Set (mathematics) Subset Partition (number theory) Solution set Root Solution set Network topology Partition of a set Network topology Large eddy simulation Helmholtz decomposition Mathematical optimization
Kante Greedy algorithm Direction (geometry) Algebraic structure Maxima and minima Decision tree learning Zielfunktion Goodness of fit Order (biology) Degree (graph theory) Strategy game Network topology Iteration Canonical ensemble Object (grammar) Vertex (graph theory) Arc (geometry) Operations research Adaptive optimization Slide rule Laufzeit Set (mathematics) Element (mathematics) Binary number Root Estimation Function (mathematics) Network topology Strategy game Partial derivative Iteration Queue (abstract data type) Electric current Length
Kante Zahl Graph (mathematics) Algebraic structure Maxima and minima Lösung <Mathematik> Decision tree learning Matching (graph theory) Student's t-test Infinity Counting Physical quantity Network topology Vertex (graph theory) Polynomial Axiom of choice Matching (graph theory) Höhe Moment (mathematics) Feasibility study Set (mathematics) Enumerated type Term (mathematics) Transformation (genetics) Power (physics) Element (mathematics) Subset Function (mathematics) Network topology Strategy game Set theory Physical system Force Singuläres Integral
Kante Stress (mechanics) Process (computing) Physical law Set (mathematics) Order of magnitude Connected space Orbit Hausdorff space Zusammenhang <Mathematik> Agreeableness Universe (mathematics) Configuration space Wiener filter
Subset Twin prime Function (mathematics) Set theory Set (mathematics) Infinity Mathematical optimization Wave packet Physical system Element (mathematics) Reduction of order Subset
Computer programming Stress (mechanics) Greatest element Wavefront Similarity (geometry) Lösung <Mathematik> Decision tree learning Parameter (computer programming) Plausibilität Matrix (mathematics) Solution set Strategy game Sample (statistics) Decision tree learning Decision theory Compass (drafting) Optimization problem Moment (mathematics) Horizon Feasibility study Mereology Enumerated type Complete metric space Solution set Military rank Root Coefficient of determination Network topology Universe (mathematics) Strategy game Quote Mathematical optimization
Stress (mechanics) Zahl Constraint (mathematics) Direction (geometry) Analogy Lösung <Mathematik> Decision tree learning Bound state Focus (optics) Subset Boom barrier Causality Solution set Network topology Heuristic Supremum Length Arc (geometry) Chain rule Fundamental theorem of algebra Process (computing) Slide rule Decision tree learning Feasibility study Subset Root Symmetric matrix Network topology Strategy game Berechnung Heuristic Mathematical optimization Mathematical optimization Untere Schranke Local ring Supremum
Standard deviation Graph (mathematics) Weight Constraint (mathematics) Model theory Gradient Symplectic manifold Maxima and minima Lösung <Mathematik> Zielfunktion Bound state Variable (mathematics) Lagrange-Methode Mathematics Solution set Network topology Vector space Graph (mathematics) Valuation using multiples Divisor Vertex (graph theory) Length Arc (geometry) Linear map INTEGRAL Decision theory Optimization problem Drop (liquid) Feasibility study Linear programming Computer programming Similarity (geometry) Subset Fraction (mathematics) Vortex Root Symmetric matrix Gaussian elimination Function (mathematics) Travelling salesman problem Relation <Mathematik> Optimum Mathematical optimization Integer Untere Schranke Combinatorics
so genau sind die Änderungen der immer so seine Haftstrafe Lernmaterialien an der TU Darmstadt so nachdem es wieder mal zu
Schwierigkeiten gekommen ist bei der Einrichtung des Aufnahme Aufzeichnens setzt können wir jetzt etwas verspätet tut mir leid jetzt ist etwas verspätet starten ich möchte da wieder einsteigen wo wir beim Netz mal aufgehört haben Sie einen sich dunkel es geht darum wir haben den Lösungsraum wieder im Gegensatz Nachbarschaft basierten ansetzen wo wir den Lösungsraum auffassen als gerichteten Grafen auf den zulässigen Lösung als Knoten und die Kanten konstituierenden Nachbarschaften stattdessen gehen wir hier grundsätzlich anders vor Wir zerlegen schrittweise den Lösungsraum den wir gar nicht kennen werden wir gleich handhaben den zerlegen wir schrittweise in Hälfte also nicht Hälfte aber in jeweils in 2 Teile einen solchen Teil wieder in 2 Teile und so weiter haben beim letzten Mal gesehen was man sich darunter plastisch vorstellen kann zum Beispiel wenn sie ein Feature basierte Problemstellung haben wie etwa die SPD die Features sind in einfachsten Modellierung die Kanten dann können Sie den Lösungsraum in 2 Teile zerlegen in denen sie sagen ich betrachte einerseits alle zulässigen Lösung die ich alle noch gar nicht weiß und nie erfahren werde ich Betrachtung Seite alle zulässigen Lösungen die diese kannte dich festgehalten habe enthalten und ich betrachte auf der anderen Seite separat davon alle zulässigen Lösungen die diese kann der nicht enthalten wenn man diese Schema immer weiter fortsetzt dann den nächsten Schritt die nächste Kanther in die einmal so Seitz behalten andererseits nicht behalten und so weiter dann kommt man natürlich am Ende an den Blättern dieses Suchbaum ist hier kommt man natürlich da da heraus das die Blätter sind dann sämtliche Rundtouren da die Rundtouren ein bisschen viele sind wollen wir natürlich nicht diesen Baum durchsuchen sondern wir wollen möglichst häufig versuchen eine Entscheidung zu treffen also einen Knoten eine fundierte Entscheidung zu treffen ob es sinnvoll ist diesen Teil Baum der an diesem Knoten hängt wirklich weiter zu explorieren ob man es wirklich notwendig ist da weiter abzusteigen und mit viel Laufzeit noch weitere Knoten diesen Teil um zu durch suchen oder ob man sagen kann es gibt hinreichen Grund für die Annahme dass es sich nicht lohnt diesen Teil Baum weiter zu durchsuchen dass wir den also hier ab schneiden können das kann einerseits wirklich immer fester Erkenntnis sein dass es sich nicht lohnt das sich definitif nicht und weil man belegen kann die wenn es hier drin eine optimale Lösung gibt gibt es auch außerhalb einer von diesen Teil Baum noch in dem Bereich den wir noch betrachten eine optimale Lösung oder dass wir sogar belegen können in diesem Teil Baum den wir gerade auf den Prüfstand stellen gibt es definitif keine optimale Lösung dass wir sogar das belegen können das ist natürlich ideal dann haben wir eine Entscheidung gemacht bei der wir unmöglich einen Fehler gemacht haben können er Teil Bäume in dem es gar keine optimale Lösung gibt oder keine bessere Lösung als die diese noch verfolgen die können natürlich ohne ohne weitere Probleme ohne einen Fehler zu machen ausschließen von der weiteren Suche wird man im allgemeinen nicht immer so so fest haben so eine feste es soll eine feste festen Beweis dafür das ist dass es sich nicht lohnt diesen Teil 1 weiter zu durchsuchen oft genug wird man eher heuristisch vorgehen dass man sagt na ja ich bin mir nicht hundertprozentig sicher dass dieser Teil der Baum wirklich abgeschnitten werden kann ohne dass wir damit einen Fehler machen aber wir machen es trotzdem weil allem Anschein nach ist es so ist es sehr wahrscheinlich sehr plausibel dass dieser Teil Baum nicht ja es nicht wirklich wichtig ist für unser Ergebnisse zu erzielen wollen oder dritte Möglichkeit wenn wir auch noch betrachten das wir in einem Teil Baum umsteigen dass wir sagen wir haben absichtlich zielorientiert die die diese Zerlegung das Lösungs Raums in einzelne Teile und so gestaltet das einer er ab einer bestimmten Stelle plötzlich dieses dieses Teil Problemen von einer sehr viel einfacher Natur ist so dass es sich mit anderen Algorithmen ohne dem weiter denn den Suchbaum zu explorieren so dass sich dieses dieser dieser Ausschnitt das gesamte Lösungs Raums also die ursprünglichen Bedingungen zu sich mit den auf dem Weg im Suchbaum hinzugenommen wir Bedingungen dass diese dieses Problem sich als sehr viel einfacher darstellt an von einer anderen Struktur von einer einfachen Struktur haben sämtliche komplizierte Strukturmerkmale durch diese zusätzlichen Bedingungen rausgeschnitten ausgenommen und so dass wir dann einen eigenen einen Algorithmus anwenden können um die an um ein diesen Müll in diesem Ausschnitt des Wesens Raums die optimale Lösung zu suchen das werden uns alles der Reihe nach ansehen das haben wir schon beim letzten Mal gesehen dass brauche eben nicht weiter zu vertiefen 1. Beispiel ist etwa das was ich gesagt habe in man Beispiel TSP eine Kante ist drinnen oder eine kann das nicht Rillen das kann man auch auffassen als eine binäre Variable die entweder 1 oder 0 Gesetz ist haben das mal gemacht wenn Sie irgendwelche wenn und seine Songs kommen wir zum anschauen kann dieses Problem haben nehmen wir als einfachstes Beispiel was ich kenne her haben linear Gleichungssysteme lösen oder man auch einfach als Beispiel ist eine Nullstelle finden bei einer Funktion da ist es dann ganz offensichtlich wie das wie das ist wenn man das so legen wurde nicht man würde irgendwo also wir haben mehrdimensionale Funktion man würde vielleicht eine 1. Dimension mal an irgend einer Stelle Einschnitt durch legen und alles was kleiner diesen Schnitt werden also kann diesen Schnitt wird es jeweils für sich betrachten und würde vielleicht dann in der zweiten Dimension den nächsten Schritt auf der nächsten Ebene des Baums legen und so weiter und so fort und an jeder Stelle vielleicht können das mal gut als ein weiteres illustratives Beispiel hernehmen zu ja Sie haben in diesem Bereich eine zweidimensionale Funktion und sie wollen Nullstelle finden sie kennen diese Funktion nicht wirklich er sieht die Sie kennen Sie sie kennen sie können über diese Funktion nur etwas aussagen was häufig Platz passiert in den sie an einem bestimmten Punkt in diesem zweidimensionalen Bereich eine Maschine Fragen in der den einen Sensor ablesen lassen oder irgendetwas der Ihnen sagt die diese Funktion wird an dieser Stelle ist ja wenn Sie jetzt ist das hier zu leben zum Beispiel diese Bereiche können Sie zum Beispiel ja mal ein paar Stellen absolvieren wie das so aussieht wie der vom so aussieht natürlich nicht an so vielen weil das eine teure Operation ist und wenn sie verstellen na ja vielleicht an dieser Stelle steht noch nicht fest also zerlegt man das weiter geeignet jeden weiten Bereich und den Sir zum Beispiel feststellen ich das ist alles weit weg von 0 in diesem Bereich dann haben Sie natürlich bei weitem nicht bewiesen dass da keine Nullstelle ist aber vielleicht paar plausiblen Annahmen darüber was dieser für dahinter für dieses das in der Stimme der physikalische Phänomen ist was mit Sensoren gemessen wird können Sie da können Sie eine plausibel Entscheidung treffen Meyer wenn die alle so weit weg von 0 sind also alle Messpunkte die wieder eine Norm haben dann ist die Wahrscheinlichkeit groß das das das hier keine Nullstelle dass sie keinen von uns oder sie Könnens auch geografische welches anschaulicher stellen sich vor Sie wollen in einem geografischen Terhaar den den niedrigsten Punkt Finder da wo sich alles was aus sammelt wenn Sie hier sehr hoher Punkten sehr hohe Punkte fehlen im Verhältnis etwa zu hier dann ist die Wahrscheinlichkeit sehr groß dass in diesem Bereich nicht der tiefste Punkt des ganzen zu Hause sein würde dann würden Sie sagen an dieser Stelle an dieser Stelle das streichen wir die Wahrscheinlichkeit dir das Wahrscheinlichkeit dass wir hier einen Fehler machen ist sehr gering ich hoffe dass das einigermaßen anschaulich die das Grundkonzept rüberbringen wie es bei Conti gebe es bei stetigen Variablen aussehen könnte Fischer basiert habe ich eben gesagt dass er das Beispiel TSB einmal man zwar den Lösungsformen alle Lösungen die die Kant enthalten alle müssen die Kante nicht enthalten Entscheidungsbäume hatten wir beim letzten Mal schon mal aufgeführt war auch
das im Prinzip das was Sie hier sehen ich hatte gesagt immer binärer also er entweder kann den zu nehmen oder nicht aber das ist natürlich konzeptionell nicht unbedingt notwendig dass wir zu haben man könnte beispielsweise auch Entscheidungen haben die die 3 die Idee den Lösungsraum in 3 Teile oder nur noch mehr Teile zu legen so das ist alles das hatten
wir alles schon das hatten wir doch alles schon vielleicht noch mal zu Änderung Rungg wie das wir sind immer noch bei den Fohlen die wir beim letzten Mal hatten haben Sie das allgemeine algorithmische Schema aussieht wir wir stellen uns vor also die eine der wiesen diese Situation er wir wir haben den den gesamten Lösungsraum ja repräsentiert und wir das ist der kann der nur den gesamten Lösungsraum repräsentiert der was heißt das dass sie den Lösungsraum repräsentiert sollt ich vielleicht dazu machen sagen also insbesondere was heißt es dass ein nur ein Teil des Lesens Raumes repräsentiert wird das bedeutet das hier eine neue Bedingung hinzukommt ja dieser Teil des Lösungs Raums der durch diesen knuddel präsentiert wird bedeutet das ist der das ist der Raum der durch die ursprünglichen Bedingungen der Problemstellung TSB dass es noch unter ist beispielsweise die ursprünglichen Bedingungen der Problemstellung plus der Zusatz Bedingung definiert wird und wenn wir noch weiter hingegen kommt jeweils auch wieder eine Zusatzbedingungen rein ja jeder einzelne Knoten lässt der sich der Name bisher aufgefasst alten Repräsentant für einen Teil des Wesens Raums kann man auch genauso gut auffassen als eine als eine Menge von zusätzlichen Bedingungen auf jeder Stufe kommende Bedingungen kennt zu die jeweils den Lösungsraum im am 1 Zweig so aufteilen einen Zeugen so aufteilt so was heißt es jetzt hier im 1. Schritt das der Wurzel Knoten dass auch das ursprüngliche Problem modelliert repräsentiert das bedeutet diese Menge einzusetzen wird das leer an diesen Knoten merken uns eine leere Menge von zusätzlichen Bedingungen an jedem anderen Knoten denn wir in Spielen mit rein im Schritt 2 nach und nach merken wir uns entsprechend eine nicht leere Menge von zusätzlichen belegen das ist das was wir als Datenstruktur praktisch in die Hand in die Hand nehmen so das hatten wir beim letzten Mal schon er kurz angedeutet sie erinnern sich für mich sind Bäume jetzt wollen im Sinne von wozu Bäume er immer so was dreieckiges was unten ausfranst weil ich alle Blätter auf derselben Höhe immer sein müssen so und wir haben dann einen Freund auf der oberen oberhalb dieser Freund sind die Exploit nutzt die die wir schon betrachtet haben und auf der unteren Seite sind die ein Exploit Notz und natürlich gibt Haufen kannten unter und in jedem Schritt nehmen wir irgendeinen zunächst mal völlig beliebigen an Exploit Nauth zum Beispiel den hier und bei dem machen das selbe Spielchen wieder wie entscheiden lohnt es sich so wie wir das hier hatten ja dieser Alex von Notz entspricht jetzt einer einen neuen Zerlegung das entspricht einem Mainzer Lebens L er Mängel nennt und wir entscheiden lohnt das lohnt es sich den Knoten Spiel zu behalten und später dann wieder weiter zu zerlegen oder lohnt es sich das nicht und wenn sich das nicht lohnt dann schneide den ganzen Teil Baum der hier drunter an diesen Knoten anlegt und man sieht das wenn wir nicht sagen wollen wir geben diesen Knoten auf weil wir uns die sich hier genug sind dass es sich nicht lohnt dann lassen wir den Knoten als Experten und im Spiel
alles nichts neue Täter wir so stark ist weil ich es haben wir auch schon
betrachtet Tiefensuche breiten suche besten suche
ist nichts Neues so ja mehr ok die Frage war das Protokoll für die Aufnahme wenn wir schon und welche Bedingungen haben also die würde man dem großen Wunden zu führen die kann man sich natürlich und Busse Knoten zu denken also wie man das das organisiert ob dem wozu Knoten dann tatsächlich schon als 1. Grundmenge von Bedingungen drin sind oder ob man das alles separat macht und sich und und mit der Semantik das an jedem Knoten immer die Zusatzbedingungen dran stehen das will die SP ist auch ein Beispiel wo es ja schon Bedingungen vorher gibt nämlich dass die Features die ausgewählt werden kann die ausgewählt einer und 3 geben müssen ob es jetzt Sinn macht das jetzt ein Nebengebäude noch redundanter Weise noch zusätzlich zu markieren die er nicht nur Musik hören sondern auch an jedem anderen ja die Idee ist ja immer die Gesamtlänge aller bis dahin aufgelaufenen Bedingungen an jedem Knoten anzupacken damit wir diese Gesamtmenge sofort griffbereit an diesen Knoten haben ob es sich lohnt das da hineinzupacken oder ob das separat das Wissen darüber was das TSB eigentlich ist was über den deren sind und man musste parat hält also wahrscheinlich sollte man sehr sehr bereithalten ich würde da was ist die Frage okay so wenn wir tiefen Suche machen wenn wir also weit runter gehen dann finden natürlich relativ Leeson habe ich hier geschrieben wird sie natürlich sehr sehr schnell eine 1. zulässige Lösung und diese 1. zulässige Lösung gibt es schon mal sehr Information vor allem dann wenn wir sie vielleicht gezielt versucht haben einen möglichst guten vor zu sehen sie gibt uns die Information die optimale Lösung der der der Ziele Funktions- ob dem Werte optimale Lösung kann nicht schlechter sein als der Zielfunktion dieser Lösung das werden später wichtig sein weil wir später im Brandtschen bauen Verfahren teilbaren ausschließen indem wir belegen können die optimale Lösung die sich hier vielleicht in diesem Teil Bombe findet es kann nicht besser sein als die beste Lösung die wir bisher gesehen haben bestem Westphal Search kostet ne Menge Laufzeit natürlich pro Iteration muss man sich genau überlegen prallten suche na ja Sie wissen wie schnell ein Baum ein vollständiger binärer Form in die Breite geht nullter Stufe hat 2 hoch 0 1 Knoten die Wurzel 1. Stufe hat 2 2 Euro 1 2 10. Stufe hat 2 auch 10 sogar schon bei Tausend 20. Stufe hat 22. war schon bei einer Million 3. Stufe 2 auch 30 in den 30 Stufe 2 Uhr 30 sind wir schon bei einer Milliarde und so weiter das geht so ohne weiteres nicht das heißt wenn wir wir werden oder Sie werden sehen dass wir auch auf breiten Suche arbeiten können das wird sich dann dynamische Programmierung nennen er aber wir werden sehen dass man eine Menge tun muss damit eben möglichst viele Knoten ausgeschlossen werden von der weiteren Suche weil die Suche Freund der dann wirklich horizontal hier durch den Baum durchgeht bei breiten Suche weil die einfach zu breit wird bei dieser Suche ist die größte Suche von kein Problem das einfach der aktuelle vor Ort bei breiten Suche vielleicht das noch mal er sollte vielleicht auch nochmal visualisieren bei tiefen Suche ist die Situation immer so dass sie einen aktuellen Fahrt haben der muss sich bis ganz unten sein ich sehe ich es war vielleicht doch bis nach unten und die Kanten die rechts in den noch nicht betrachteten Bereich rausgehen von diesem Fahrt das ist die aktuelle Frontiers alles schon besucht worden wir gehen vor vielleicht die Frisur von links nach rechts durch es egal wie aber das ist dann natürlich anschaulicher ich sage wir gehen wir gehen Sie so in einer Richtung durch während das ist die Suche während breiten suche ist das Bild genau entgegengesetzt die Freundes ist im Prinzip horizontal mehr zum Kleinkrieg drin so wir werden sehen dass wir bereit sind dann da aber trotzdem tatsächlich anwenden können wir müssen nur dafür sorgen das eben die überwiegende Mehrheit sämtlicher Knoten in ihren Schritt wieder rausgeschmissen wird bevor sie jetzt weitere Laufzeit kosten kann man kann auch über kombinierte Strategien nachdenken zum Beispiel am Anfang BFS noch denkbar ist also wenn man das noch nicht unseren Speicherplatz sprengt das wir erst mit PFS so weit wie möglich durch gehen und dann wenn das wenn das zu viel wird das wird dann gezielt an wird das wir dann DFS aufbrechen und mit breiten Suche gezielt bestimmte Bereiche tiefer ist früher tiefer explorieren und andere Bereiche erst später in der Hoffnung dass wir die gar nicht mehr dass wir diese später auf später verschoben und Bereiche dann später gar nicht mehr explorieren müssen weil wir wissen weil wir inzwischen genug gesammelt haben um zu wissen diese Bereiche brauche ich würde zu durchsuchen
so also wir können uns nicht leisten steht hier den gesamten Baum Exhaust aus der erschöpfend zu durchsuchen üben sich weil damit das gesagt es gibt für erschaffen 2 Begriffe im englischen Haus das Lee und Ex-Frau Stanley X aus dem ist wirklich ermüdend und Ex Harste flehe ist erschaffen in dem Sinne etwas erschaffen durchsuchen so wenn wir die E die Lösungen sämtliche optimale Lösungen haben und nicht nur einen mit einer zufrieden sind und alle haben wollen dann würden sich daraus übrig bleiben als den ganzen Baum zu durchsuchen was natürlich dann gegen solche Innovations- Probleme spricht sie werden sich vielleicht fragen er unter welchen Umständen will man denn sämtliche optimale Lösungen wir haben es reicht doch typischerweise wenn man eine optimale 7 bekommt und die dann in die Praxis umsetzt ein Beispiel etwa ist Fahrplanauskunft Systemen wo verschiedene optimale Lösung gibt eine für den eiligen Geschäftsreisenden einen für die alte Dame mit 2 Koffern ein für den armen Studenten und so weiter und diverse Mischformen ja es gibt da das mehrere Kriterien gibt Fahrzeit Fahrpreis Bequemlichkeit der Fahrt gibt es eine ganze Menge von optimale Lösungen und man wird vielleicht nicht alle optimale Lösungen haben aber zumindest eine Innovation von optimale Lösung so dass für jedes Kunden Profil immer eine gute Lösung dabei ist also in Amazons Probleme meistens reicht es einmal eine optimale Lösung zu haben aber in manchen Situationen vor allem dann wenn mehrere Kriterien Spiel kommen zwischen den man nicht von vornherein die Balance setzen kann wo man sagen muss in einem nachgelagerten Schritt müsste niemand anders entscheiden wie die Kriterien zu gewichten sind da will man dann die frischen ob denn Mann Lösung haben zählt Probleme wie viele zulässige Lösungen das ist manchmal auch in manchen Kontexten wichtig ist es aber ein bisschen zu kompliziert vielleicht nur ein Hinweis in dem Moment wenn das ganze stochastischer Natur ist wenn wir mit Wahrscheinlichkeiten zu tun haben dann in denn er die Anzahl der optimale geteilt die Anzahl aller Lösungen oder so etwas da kommt CC Problem Endspiel aber mal will man nicht wissen wie viele zulässige Lösung es gibt gut wie soll man jetzt bei Informationsproblemen vor normalerweise würde man wenn man wirklich alles durchsuchen will würde man tiefen Sucher implementieren 1. Mal einfach implementieren klar haben Sie vielleicht schon mal gemacht und hat keine großen Anforderungen Speicherplatz Sie Sie dürfen nicht vergessen dass dieses Dreieck nicht so schön aussieht wie sie gezeichnet haben zwischen 3 schändlich in Wirklichkeit geht dieses Dreieck extrem in die Breite das heißt die Höhe die Sie hier als als als Speicheranforderungen bei tiefen Suche haben ist viel viel kleiner als die Breite die Sie hier bei bereiten Suche als Speicherplatz Anforderungen haben so vor kann man meistens nicht anwenden Ende dort wo heißt er sehe sie gehen wirklich ganz brutal daher Brot voraus mit mit brutaler Gewalt gegen sie den ganzen Baum durch das können Sie bei kleinen Instanzen sich leisten und das ist auch sinnvoll dass sie sich das leisten weil weit wenn schon die Chance haben wenn es dann so klein ist dass sie dass sie wirklich durch Brot voraus die Optimallösung kriegen dann sollten sich diese Chance nicht ungenutzt lassen aber natürlich es allgemein K keine gute Lösung so wir sollten einen Punkt dabei nicht auslassen das ist ein sehr sehr wichtiger Punkt in der Praxis theoretisch ist da nix dahinter ist glaube ich auch nicht sehr schwer zu verstehen aber wir sollten einen wichtigen Punkt für die Praxis nichts ich gucke mal weiter nach ja genau ein
ich ihn darum nicht auslassen nämlich wie wichtig es ist Vorjahr formalen überhaupt irgendeine rückerstattet egal ob diese Nachbarschaft eine basierten Algorithmen die wir vor hatten wir hier noch wichtiger solche Algorithmen oder auch ganz andere Algorithmen die wenig betrachten das wir vor dass wir vorher zunächst einmal jede Möglichkeit wahrnehmen in einem Politprozess sinkt die Problemgröße die Größe eines Instanz deutlich zu reduzieren ich will das ganz kurz es meine einem einführenden Beispiel machen und dann einen etwas ausführlicher an einem Beispiel aus meiner eigenen Praxis aus den 90er-Jahren also dieses führende er ja illustrative theoretische Beispiel Sie kennen das Thema mitschwingt sie wollen eine Sie haben eben ein ungerichteten Grafen ja sich das Matching heißt sie haben einem ungerichteten Grafen wo vielleicht im muss wie üblich nicht planar seien deshalb vielleicht nicht der bewusst auch meine Kreuzung sein und sie wollen ein Kardinal Vitez maximales Matching wir haben das heißt sie wollen eine möglichst große Zahl von könnten haben in diesen Grafen die sich paarweise nicht berühren ich habe das jetzt so spontan aus der freien Hand gezeichnet ich glaube das ist nicht optimal denn wenn ich das richtig sehe diese kannte diese kannte ja diese kannte diese kannte nee nein die nicht diese kannte diese kannte diese kannte und diese Kante sind auch Ahmed Schenk mit Größe 4 und ich glaube das ist jetzt optimal so so wie was machen wir hier einfach eine ganz primitive Regel wirklich so primitiv dass man so sagt sagte selbstverständlich und alles klar und was was redet der da wozu belästigt der uns mit sowas es wird aber häufig genug in der Praxis nicht auf solche primitiven Regeln beachtet was ist die primitive Rede nehmen Sie an Sie haben den Knoten von gerade 1 Sundown daraus zeigt wenn Sie diese könnte zu Mertsching kann machen und alles hier rausschmeißen das Zimmermädchen kannte vielleicht sollte nicht das wir bitte Aufnahmen noch mal ein kleines bisschen nochmal weil es jetzt doch ein bisschen alles durcheinander wird sie haben die Situation hier haben Sie einen Knoten von gerade 1 das ist der hier und hier geht es irgendwie weiter in dem Grafen egal wie so sie können nichts falsch machen wenn sie diese keine zu mit Schinken zu nehmen und alles was sie rings gezeichnet ist rausschmeißen so dass dann leicht ich mal jetzt ganz gut damit klar ist und die gut worum es geht so dass das was übrigbleibt nur noch das hier hinten ist was bleibt übrig so ja Sie können nichts falsch machen sie können sich gut überlegen werden Sie ein maximales mit haben das einer von diesen 3 Kanten enthält und diese kann der dann natürlich nicht den können Sie diese Mädchen kann der Nebenkosten welchen rausschmeißen und die Kante stattdessen einem dann ist immer noch maximal das Match in das heißt sie können nichts falsch machen wenn Sie sah von fordern sagen diese kann der gar zu maximal mehr Kinder zu dass ich berechnen will und fertig Sohn wie sie jetzt sehen geht das weiter jetzt ist hier plötzlich hier unten eine ein Knoten entstanden vor können gerade als hat aber jetzt für sich gerade satt das heißt sie keine Spielchen weiterführen können diese könnte zu mit Schindler nehmen sie können dass sie rausschmeißen und was dann noch übrig bleibt ist das hier oben und jetzt ist keiner kann damit gerade 1 mehr da in diesem Beispiel jetzt auf dieser deutlich reduzierten werfen müssten sie dann ihr ihren Algorithmus für maximal mit den anderen so ich will Ihnen jetzt ein Beispiel zeigen aus meiner eigenen Praxis und was mich wirklich so selber überrascht hat dass sich Wochen damit verbracht haben nachzuprüfen ob man einen Algorithmus wirklich korrekt ist oder nicht weil ich das nicht glauben konnte
ich überspringen mal hier ein paar dpa früh 1. Mal kommen darauf zurück sie wollen für eine gegebene Menge von Zugläufen ja Anzug laufe es eben ein Zug der von Heidelberg nach Frankfurt fährt und um 9 Uhr 6 in in Darmstadt ab 4. Einzug auf also ein physischer Zug wenn eine Stunde später nochmal einen Zug da lang fährt ist es ist ein neuer Zuglauf muss auch als Sonderzug genommen werden denn es gibt häufig setzt selbst wenn sie getaktete Verbindungen haben bei der Deutschen Bahn gibt es häufig doch kleine Auslastung dass der eine Zuglauf einen bestimmten Bahnhof wie Darmstadt Süd anläuft und der andere eine Stunde später läuft den es in welchen gründlich an das heißt also Sie müssen da schon als einzelne Zugläufe betrachten so die Aufgabe ist jetzt zugelassen zu überdenken das heißt also für jeden einzelnen Zug Zuglauf in der betrachteten Menge eine zwar Station zu bauen wo dieser Zuglauf auf jeden Fall hält wo dieser Zugewinn verhält und natürlich wollen sie so wenig wie möglich zu Station haben wenn sie nur das ICE-Netz vernehmen dass ein veraltetes ICE-Netz Frauen schön wir müssen schon 15 Jahr ungefähr als sein das Bild ich bitte um Entschuldigung dass ich das nicht abgedichtet habe aber es geht ja hier ums abstrakte nicht ums konkrete also ich habe die Rally Abstraktionsvermögen dass sehen dass die Vorlieben in dem mit dem ICE-Netz von vor 15 Jahren und Sie sehen Sie sehen hier auf den 1. Blick dass diese Stationen die der Algorithmus ausgeliehen hat auch das ist was man sich wahrscheinlich mehr der wir selbst überlegt hat ungefähr das Berlin Hannover Köln Frankfurt Stuttgart München so jetzt betrachten sie alle Züge nicht nur die ECE ist sondern sämtlich auch die kleinen Bummelzüge die an jeder Milchkanne halten was Sie hier sehen sie sehen hier als damaliger Schienennetz in grau unterlegt sowie Links auch was Sie hier auch sehen sind ein paar führt verschiedene Punkte einzelne isolierte Punkte und sie sehen noch einzelne Konstellation die zu kleine Zusammenhangs Komponenten die nicht isolierte Punkte sind sondern sondern einzelne bestehen aus wenigen Knoten und Kanten das ist das Ergebnis das Preprocessing S wie ist das mit Prozessen ganz einfache Regelung dass Preprocessing wenn ich 2 Bahnhöfe habe wie beispielsweise Darmstadt Hauptbahnhof und Darmstadt Süd da kann ich dann startet rausschmeißen aus meiner Betrachtung warum ich kann Darmstadt Süd rausschmeißen aus meiner Betrachtung weil alle Züge die in Darmstadt Süd halten halt noch in Darmstadt Hauptbahnhof das heißt sollte Darmstadt Süd aus irgendwelchen Gründen aus in meiner optimale Lösung drin sein der König auch Darmstadt Südost man optimal rausnehmen da stattdessen Darmstadt Hauptbahnhof reintun habe dieselbe Anzahl von Stationen und habe alle Züge die ich vorher mit am Schatz überbelegt habe auch mit Darmstadt Hauptbahnhof überdeckt das ist die eine Reduktion träge das primitiv die 2 3. zu uns Rede ist sie betrachten 2 Züge die von Darmstadt nach Frankfurt gehen da eine hält in Darmstadt landen und Hauptbahnhof und der andere die S-Bahn S 3 glaube ich ist das und sie ist 3 nicht die hält nicht nur in Darmstadt Langen und Hauptbahnhof sondern die hält also ziemlich halt dazwischen dann können Sie diese S-Bahn die S 3 aus ihrer Datenmenge rausschmeißen weiß den andern Zug gibt es nur in Darmstadt Langen Frankfurt hält durch diesen zugesetzt um das Darmstadt Langen oder Frankfurt Hauptbahnhof zu diesen zur Station gehören wird einer von den dreien und damit es sie S 3 natürlich auch überdeckt so und die Sie jetzt an diesem Beispiel auch gesehen haben es lohnt sich auch hier also hier hat es sich gelohnt nicht einfach nur ein Schritt zu machen alle kannten die im alle Knoten Ursprungs Grafen gerade 1 zu haben zu behandeln sondern nachdem man die behandelt hat noch mal zu schauen ob es dich neue Knoten im Grafen gibt die gerade 1 haben dieser behandelt werden können so dass es noch weiter reduziert werden kann genau dasselbe kann man hier machen dass man einen Rutsch alle Bahnhöfe rausschmeißen des dominiert sind dann im nächsten Wunsch alle Züge rausschmeißen die dominiert sind dann wieder schauen vielleicht 10 neue Bahnhöfe Vereinschef standen die in diesem Sinne dominiert sind die rausschmeißen dann wieder alle Züge rausschmeißen und so weiter und so fort egal in welcher Reihenfolge bis es keiner ist diese Regeln keiner der beiden Ringe mehr anwendbar ist und das Ergebnis sehen Sie rechts was heißt das Ergebnis und wenn Sie da einen ein isolierten Knoten sehen ein isolierter Knoten steht für ein Bahnhof natürlich dass der Bahnhof der in diesen geografischen Kurdin Daten steht wo dieser Globe gezeichnet ist und steht auch für einen Zug komisch vielleicht noch mal was bedeutet das wenn da mehr als Insel wird der Knoten ist zum Beispiel so Konfiguration das sind dann Bahnhöfe 1 2 3 ohne oder ich mal die man mit ABC Bahnhöfen mit dem Namen ABC und dessen 3 Züge der 1. Zug 2. Zug 3. Zug eine solche Konstellation lässt sich mit diesen Reduktion zu die beschrieben habe nicht weiter
auflösen sie können keine 3 Bahnhöfe nach Hause nehmen keine dominiert den anderen und Sie können keine 3 Züge rausnehmen wie kommt das der zustande 1. Mal dass solche isolierten Bahnhöfe mit jeweils einen Zukauf der reduziert wurde ist der schrittweise reduziert wurde zu einem einzigen Bahnhof ja der hat im Original vielleicht fahren die Bahnen 1 gefahren er schrittweise durch dieses Preprocessing reduziert worden auf einer einzigen Bahnhof wie kommt das 1. Mal dass zustande wie kommt es zustande das ist ganz überhaupt zerfällt in ins einzelne kleine Zusammenhangs Komponenten dass es nicht mehr zusammen ist denn das grau unterlegte ist hat mit dem Bild ein wenig zu tun dass die nur ihrer Orientierung dass das Schienennetz nochmal unterliegt die bei ihrer Orientierung im bevor wo wir da eigentlich gerade sind ich hoffe mal dass sie so viel Orientierung haben mehr als ist es gibt manchmal so Umfragen in im Fernsehen in einer Fußgängerzone ich weiß es so was schon mal gesehen haben auf einem für der Umriss von Deutschlands und die fragen Passanten wo sind wir hier ist teilweise niederschmetternd zu sehen wie wie die Leute mit dieser Frage umgehen gut wenn ich vielleicht dann noch keine Exkurs machen darf einer Mann ist ist der hat mir berichtet 1 von einem von einem Freund von ihm der bei SAP mit der aber er mit gewirkt hat Einstellungsgesprächen also eher als Fachvertreter und dazu noch ein Personalvertreter und der Personalvertreter hat jeden einzelnen Bewerber im Gefühl spricht gefragt man sie doch mal 5 europäische Hauptstädte das war für sehr viele dieser Verträge für diese dieser Bewerber wohl eine unüberwindliche Hürde wobei die was wir am häufigsten genannt wurde war Barcelona ich hoffe sie verstehen was ich damit sagen will obwohl es kann ja sein wenn es weitergeht in Katalonien wie bisher das passt oder vielleicht demnächst möglich zur Hauptstadt wird kann er sein so wie komme Gesetze zustande ich will das an einem künstlichen Beispiele mal versuchen darzustellen und ich mal so mal so das sind 4 Bahnhöfe wir haben einen Zug einen 2. Zug 1. Zug 2. Zug und einen 3. Zug der die 4 Bahnhöfe anläuft so jetzt kann ich erst einmal Bahnhöfe reduzieren das sind die oberen beiden A B C D das ist sozusagen A und B in einem Bahnhof C und D in dem 2. Bahnhof und was noch übrig bleibt ist hier drauf der Zug 1 reduziere zu einem Bahnhof der Zug 2 und der Zug 3 ist reduziert auf 2 Bahnhöfe so und jetzt eben wie das Beispiel der eine Zug der Darmstadt Langen Frankfurt mein anführt und die S 3 die sowohl diese 3 Bahnen weiter als das Wissen anfährt wir können die 3 jetzt die 3 wird sowohl von dem also von dem dominiert das heißt was übrig bleibt sind 2 isolierte Knoten hier ist der Zug 1 drauf dieser Knoten aus A und B Gegenstand dieser kann sonst C und D entstanden und die es zu 2 drauf und zu zu 3 ist wegrationalisiert sozusagen also sehen Sie durch solche einfachen Schemata wie kommt es zustande dass man erst am Ende so ein Bild dabei hat was ist die Moral aus der Geschichte noch krasser als eben bei diesem Beispiel bei Mirtschink wo sie eigentlich schon krass war ja wir sind hier mit Sonnenaufgang Sklaven gestartet und haben das gestellt wir müssen auf diesem kleinen Grafen hier eigentlich das Problem lösen noch viel krasser ist in diesem Beispiel das wir jeder einzelne Knoten wenn wir eine Wiener sind oder so wird es wenn wir einfach so unbesehen zu optimalen Mengen zu und in jedem einzelnen dieser dieser kleinen zusammen es Komponenten machen wir das was wir eben gesagt haben gut voraus einfach alles ausprobieren können und leisten jede zusammen Gemeinde ist klein genug dass wir da einfach jede Möglichkeit ausprobieren und damit insgesamt 7 optimal Lösung zu kommen zwar das Problem die Problemstellung bis in die schwer zu wissen was das heißt für jeden Algorithmus als auch für diesen für jeden Algorithmus findet man Instanzen von moderater Größe also von Vieh kleineren Größe auf den dieser Algorithmus mehr Zeit benötigt als das Universum zur Verfügung stellt diese Instanzen gibt es natürlich für diesen Algorithmus aber sie kommen hier in dieser Problemstellung dieser konkreten Anwendung nicht vor ja sie müsse unterscheiden zwischen dem der abstrakten Problemstellung dies endlich mehr und der konkreten Anwendung in der Lage bestimmte Instanzen vorkommen oder Instanzen bestimmten Taten Profil und wenn Sie geschickt sind und ihren Algorithmus so gestalten dass er dieses dann Profil geschickt ausnutzt dann können Sie auch endlich schwere Probleme in gewaltigen Größenordnung der von 1 comma decimal 5 4 1 comma decimal 5 Millionen einzelnen Einzug halten können wir können wir das machen vielleicht noch dazu sagen denken das optimal sogar lösen allerkürzester Zeit für noch dazu sagen ich habe das ausprobiert auf den gesamteuropäischen schien in allen möglichen Variationen alle möglichen verschiedenen Auswahlen von Ländern alle möglichen falschen Ausmalungen von Zug Gattungs- Arten die größte Zusammenhangs kommen die mal unauflösbar stehen bei natürlich 1 mit 29 Knoten wovon er nur Freunden 6 Knoten insgesamt die optimale Lösung gebildet haben setzt das war noch ein period lösbar und eine Größe zusammen es kommende da habe ich nie gefunden so nochmal zurück worum geht es
hier das ist das sogenannte Dings Problem wir haben eine Grundmenge das sind die Bahnhöfe in unserem Fall und wir haben Teilmengen davon das sind die Zugläufe ja wenn sich das genau überlegen und Interessierte an einen Zugriff interessiert uns nur eine einzige Information in dieser Problemstellung nämlich welche Bahnhöfe sind müssen Zuglauf drehen oder andersrum gesagt wir können Zuglauf auch einfach interpretieren als die Menge der Bahnhöfe dieser Zug als alles andere sieht uns also ein Zuglauf überhaupt nicht so jetzt wollen wir eine Menge von Bahnhöfen haben eine Teilmenge von Bahnhöfen so dass jeder einzelne Zuglauf einen dieser Bahnhöfe trifft also der Zuglauf geschnitten mit der ausgewählten mit den ausgewählten Servicestation ist nicht mehr und die Zielsetzung ist dieser Station comma die Menge der Service Station zu minimieren
so ich hoffe das konnte ihn einen guten Eindruck gewinnen als ich das mal vorgestellt hatte auf der Konferenz 97 98 glaube ich habe ich als 1. gefragt die im Laden Audi im Auditorium wie würden Sie das machen wir wenn Sie das lösen alle möglichen Überlegungen auch Sachen die wir schon gesehen haben die genetische Algorithmen Shary aber niemand es auf die Dinge comma Zusagen es immer erst Abend bevor oder bevor ich alles andere mache gucke ich mal an ob man die die Daten in dem Preprocessing reduzieren kann denken Sie daran dass das einfache
Preprocessing da oft genug unlösbare Probleme in lösbare überführen kann auch in anderen Kontexten zum Beispiel bei allen Angleichung System und ähnlichen Line Optimierung hat hatte schon viele gegeben wurde ich Samples die Prozession auf Basis von Überlegungen mit mit dem Rang der Matrix durch will ja alle eine Matrix vieljährigen Rahmen hat sie einen Sie was das ist die die maximale Anzahl von unabhängigen Sch Zeilen oder Spalten wenn deren viel viel kleiner ist als die ok ich bin dann mal diesen Gedanken noch fertig wenn dann viel viel kleiner ist als die die Matrix dann können Sie erst einmal anfangen die Matrix zu verkleinern zu verkleinern und ich kann mich aus dem Bereich die Optimierung ändern dass das einer der der wirklichen Crex der den sie Algorithmus entwickelt weil ich weiß nicht ob das in das sagt aber es ist jedenfalls für den mehr Optimierungen das Tool schlechthin der Ball davon berechnet dass der Apple berichtet dass aus einer Cent Tausenden Kreuz Millionen Matrix durchaus überlegen eine 17 kurz wenn 20 macht das gemacht hat so ihre Frage ist ach so Sie fragen sondern schließt unsere Station statt nein es muss schon eine der angefahrenen Stationen sein der zu können sich keine sonder Strecken erlauben weil der wird dir die typische ist auch die dass der Zug in dem Moment wenn er beispielsweise in Frankfurt Kopfbahnhof einfährt noch mit seinem wartet und dann wieder gleich zurück fährt da es keine Zeit für irgendwas was es genau aber ich glaube es ging mehr um um Putzeinsatz oder so was ich weiß ist nicht mehr ganz genau was der Hintergrund dabei war so auf jeden Fall wir sind alle Universitäten immer immer darauf genormt immer große komplexe Lösungen zu bauen nicht gerade Informatikers sind dafür berüchtigt dass sie eine die einfachsten Probleme dadurch lösen dass sie ein Jahr lang eine große komplexe Softwarelösung bauen die dann am Ende gar nicht funktioniert anstatt es einfach mal sehen wir zu lösen ich hoffe das Beispiel konnte ihn noch mal illustrieren dass man die einfachen Dinge die man tun kann nicht übersehen sollte so wir gucken uns das an was Tuning aufs Haupt ist den Begriff hatten dabei messen eingeführt was der eigentlich jetzt konkret heißt das war also was was sie erst mal abstrakt das hieß wir wollen einer jeden über ein Knoten in diesem Entscheidungsbaum diesen abstrakten Baum wollen wir bevor wir da weiter absteigen noch zu sein in seinem abfliegen einsteigen dann diesen Bon hängt wollen wir erst einmal überlegen ist es wirklich sinnvoll ist es wirklich vielversprechend da ab 5 weiter abzusteigen oder ist es gibt es genug Plausibilität Argumente dafür dass wir sagen können wir tun diesen diesen zappt wie wir schneiden ihnen praktisch ab und wir werden uns jetzt erst einmal verschiedene Techniken ansehen die auf der sicheren Seite sind wie ich das vorhin gesagt hatte nämlich dass nur dann einen Teil Baum abgeschnitten wird an einen Knoten wenn garantiert dieser Teil warum deffinitiv nutzlos ist wenn wir ihn nicht brauchen um unser Ziel zu definitif nicht brauchen um eine optimale Lösung zu finden was heißt das einen definitif nutzloser Teil bauen jetz unterscheiden wir vielleicht erweisen bisschen in der Sprechweise das hätte ich jetzt hat ich jetzt ein bisschen unterschlagen ich habe es immer nur von Optimierungsproblem geredet aber auch wenn die Vorlesung Optimierungsalgorithmen heißt ist es immer instinktiv auch Probleme Problemstellungen mitzunehmen bei denen es nur darum geht eine Lösung zu konstruieren und nicht um den Optimallösung so überhaupt eine Lösung zu haben siehe Beispiel Stundenplan Erstellung einer Universität da ist man ja froh angesichts der vielen Rahmenbedingungen wenn man es überhaupt schafft eine Lösung zu generieren soll das so dass möglichst wenige Studierende zumindest die dämmrige Stundenplan sind dann keine Überlappungen haben bei ihren erfahren Stein keine zeitliche Überlappung haben oder was in den meisten Fällen hier natürlich betrachten sind Optimierungsprobleme sie können natürlich das Stundenplan Problem auch als Optimierungsproblem auffassen zum Beispiel dass die Bequemlichkeit der Dozenten optimiert wird dass ich mit meinem Büro Herrn Pilote die Gebäude auch tatsächlich zu einem Hörsaal in die Leute Gebäude gehen kann und ich auf der ich diesen was vermutlich für Sie auch bequemer ist dass wir im 3. Gebäude sind und ich auf der nicht wisse nehme ich mal an ob so was bedeutet das wenn wie bei einem Konstruktionsproblem wenn wir einfach nur um Lösung haben wollen keine optimale dann wäre es schön wenn wir wüssten dass in diesem Fab Three gar keine zulässige Lösung drin ist das heißt also dass die die Bedingungen die wir auf dem Weg und da von der Wurzel zu diesen Knoten zu dieser Wurzel ist habe ist mit den zugenommen haben das die dafür sorgen zusammen mit den ursprünglichen Bedingungen das Problem ansieht werden das der Lösungsraum der ist das so zu das die Bedingungen zusammen über bestimmt das System in geben also entweder das wir sank wenn wir wenn wir verstehen können das ist das gar keine zulässige Lösung gibt da drin sind auf der sicheren Seite dann kann denen den Baum abschneiden oder alternativ wir können feststellen wir wissen nicht genau ob es dort unzulässige lösen geht aber wir wissen definitif wenn es da drinnen zulässige Lösung gibt gibt es auch andere zulässige Lösungen die wir noch nicht abgeschnitten haben also können wir diesen Teil Dom abschneiden weil außerhalb gibt es noch zulässige Lösungen die wir noch nicht abgeschnitten haben er klingt alles wie schwarze Magie aber so schwarzes diese die denke ich jetzt auch nichts wenn wir dann etwas genau betrachten natürlich Optimierungsprobleme wann können wir bei einem Optimierungsproblem wie etwa dem TSB einen Teil Baum abschneiden natürlich auch wieder wenn der wenn der Dateibaum Kai überhaupt gar keine zulässigen Lösungen teilte ein Teil der natürlich keine optimale Lösung das geht natürlich nicht oder wir Fälle stellen fest dass es es Situation die beim TSB nicht auftreten kann ich zum Beispiel bei kürzeste Wege taucht dieser Situation auf kürzestem Wege mit negativen Zyklen sie wissen was das bedeutet aus der GD 2 zumindest sollten Sie das noch kennen was bedeutet das und das das wär negative Zügel haben in einem Grafen wohl kürzeste Wege finden wollen sie wollen jetzt einen Staat Noten in den Christen als gekürten kürzesten Weg von den Staat und sind sehr Knoten und sie haben irgendwo mittendrin einzige negativer länger er dann wissen Sie das sie in Probleme reinkommen weil einmal rumgelaufen er gibt mir Verbesserung so vielleicht 2. Mal rumgelaufen ergibt wieder Verbesserung 3. Nahrung Laufwege wieder für Verbesserung die ganzen Algorithmen dieser G 2 gelernt haben funktionieren nicht können auch nicht funktionieren weil es gar keinen kürzesten Weg gibt diese Prout in diesem Fall wenn
das negativer Zirkel ist ist diese Instanz das christliche Problemen unbeschränkt dort auf der Folie Englisch anbauen wird weil es gibt keinen Minimum für jeden Fahrt denn sie finden von ist noch die finden Sie einen Pfad der noch einmal mehr geht um diese negativen Züge und der nochmal ein bisschen kürzer ist und in diesem Sinne wenn Sie feststellen in in einem Teil Baum das dort in diesem Sinne dass das die wenn sie minimieren wollen sehr Minimierungsproblem haben doch die Lösung nach unten und beschränkt sind ja ohne eine unendlich viele Lösungen und und für jede Lösung die sie finde wenn sie noch eine bessere und noch eine bessere dann können Sie natürlich nicht nur den alle in diesem Teil Baum abschneiden sondern sie können Algorithmus auch lassen weil wer die Problemstellungen diesen Sinn und beschränkt ist gibt es keine optimale Lösung so jetzt gibt es aber noch andere Situation beim Optimierungsproblem wo sie in Taiwan abschneiden können nämlich das mindestens eine optimale Lösung gibt außerhalb von allem was sie bisher abgeschnitten haben und außerhalb von diesen Fortschritt also diese dritte dash hier für Optimierungsprobleme der besagt Folgendes vielleicht nochmal illustriert sie haben ihren großen Entscheidungsbaum wie üblich ein bei mir ein Dreieck das interpretieren Sie mehr als 3 bitte so und sie haben schon jetzt fleißig im Laufe des Algorithmus Teil Bäume abgeschnitten hier sind Hallbaum abgeschnitten und diesen Knoten hier sind Hallbaum abgeschnitten hier und jetzt wollen sie hier noch meinen Teil Baum abschneiden ja also ist natürlich auch jeweils einen wozu Quoten dran so was dieser 3. dash sagt es gibt mindestens eine optimale Lösung die irgendwo außerhalb von diesen ganzen Teil beim liegt die zum Beispiel hier lebt als als bleibt natürlich also außerhalb aller bisher abgeschnitten Teil und auch außerhalb das Baumteile Baumes gehen Sie jetzt gerade vielleicht abschneiden wollen ja wenn sie wissen auf magische Art und Weise das ist hier noch optimale Lösung geben muss außerhalb von diesem Teil Baum und aus von einander abgeschnitten bohren denken Sie diesen Treiber umlegen question mark belegt habe auch abschneiden sie wir haben immer noch eine wir haben immer noch eine optimale Lösung gerettet vom vom Abschneiden oder wir stellen fest wir haben schon eine zulässige Lösung vielleicht keine optimale Lösung und haben schöne zulässige Lösung gefunden und können wieder auf magische Art und Weise nicht summarisch wie es jetzt klingt auf magische Art und Weise können wir sagen ok es gibt in diesem Teil brauchen keine einzige Lösung die besser ist als die bisher gefunden der das muss nicht die optimale Lösung sein aber wenn es hier keine besser als diese gefundene Lösung gibt gibt es insbesondere keine optimale Lösung werden also können wir nichts falsch machen also wir können nur schlecht ist wenn es also schon gewohnt haben also gemäß falsch machen in dem mit diesen Teil Baum abschneiden so jetzt haben uns die ganze Zeit vor dem Einfall der eigentlichen erscheinen Frage gedrückt also ich habe mich getraut sie nicht wie kriegt man das denn aus wie kann man diese Magie entwickeln die eben wie gesagt keine Magie ist sich will keine Sohn Erwartungen wecken die Sachen sind sehr viele auf ich mal einfacher verständlich als also wird es aussieht also wir brauchen haben keine dass er uns wir brauchen irgendeine Art von ja was wir sollten im deutschen von Beleg oder sogar Beweise dass dieser Teil bauen definitive nutzlos ist so ich habe Ihnen gesagt aufeinander von denen vor dem wir werden es 3 Techniken angucken wie das aussieht und noch mal einen Schritt zurück wir haben mal kurz soll doch mal wiederholt aber beim letzten ausführlicher besprochen dass es verschiedene W Möglichkeiten gibt durch diesen Baum durchzugehen BFS also in horizontaler Wellenfront DFS in vertikaler Wellenfront bei der besten suche oder was auch immer und wir werden sehen dass diese 3 Tech verschiedenen Techniken die man jetzt Junis Vesna ist wie man Nutzlosigkeit von Teil wollen bestimmen kann dass die mit diesen verschiedenen das Durchlauf Strategien durch den Baum korrespondieren so wir müssen sie aber im Klaren sein dass wir nicht beliebig weit damit kommen werden dass wir haben endlich ihre Probleme werden immer eine Lücke wie gesagt für jeden Algorithmus auch für diese die über die Wert spricht für den Algorithmus kann man Instanzen Sommer war das größte finden so dass dieser Algorithmus länger braucht auf diesen Instanzen als das Universum im zur Verfügung stellt war also wenn wir wirklich eine vollständige Entscheidung Ketten wenn wir wirklich ein Leben wenn man es wirklich möglich wäre an jedem guten Knoten hundertprozentig zu entscheiden ob der nutzlos ist oder nicht dann könnten wir zum Beispiel nur mal so gesprochen dann könnten wir zum Beispiel die Ruhe bei der Wurzel für die früher hundertprozentig entscheiden ob die nutzlos ist oder nicht was heißt das wenn die Wurzel nutzloses gibt es gar keine zulässigen gar keine zulässige Lösung also wir könnten entscheiden ob der Lösungsformel ist oder nicht aber das ist natürlich jenseits unserer Möglichkeiten so der findet der Filius meines das wir eine konservative Strategie fahren das halt ist kein politischer Begriff 4 konservativ heißt in dem Kontext auf der sicheren Seite sein das bitte ich nicht auch nur irgendwie in Verbindung mit Politik zu bringen was heißt konservativ 4 es gibt 2 Möglichkeiten entweder ja dieser Teil warum ist definitif nutzlos wir wissen's definitif oder die andere Möglichkeit ist wären keine Ahnung wer wissen ich Oper nutzlos ist oder nicht die dritte Möglichkeiten einer ist definitif nicht nutzlos die Klinge nicht raus nur diese beiden Möglichkeiten kriegen wir und wenn wir noch rauskriegen und auf der sicheren Seite bleiben wollen müssen wir diesen Teil Baum weiter mit im Spiel lassen natürlich sollte die Methode die wir an wenn die Technik die wir noch funktionieren ja was bedeutet das dass sie funktioniert wann immer es der findet Willius lasse rauskommt alte geben der Technik dann sollte es das sicherstellen dass dieser Teil Baum definitiv nutzlos ist sollte man mal erwähnt haben was es heißt dass ein Algorithmus korrekt ist in diesem Fall so wir wollen also versuchen Techniken zu entwickeln so dass möglichst häufig tatsächlich wenn ein Teil Baum definitive nutzlos ist das dann tatsächlich als Ergebnis dieser Technik herauskommt ja dieser Teil Baumes definitiven aus aus so jetzt kommt der
1. dieser Techniken weiterbauen wenn sich die Zeit ja wir noch ein bisschen Zeit bei den Bauern den sie sich da geht es vor allem um Optimierungsprobleme da geht es weniger um um um Probleme bei dem es nur irgend darum geht irgendeine Problem stehe er irgendeinen Lösung zu generieren sondern da Bondone typischerweise wirklich wie es sich hier in den ab dem sei ohne vor gehört unmöglich Optimierungsprobleme lösen bei anderen Techniken wenn wir sehen dass man sie sowohl auf Optimierungs- Alterung auf Konstruktionsproblemen anwenden kann so der Einfachheit halber die ja optimieren kann Minimierung oder Maximierung heißen Minimierung der Kosten Maximierung des Profits sind 2 spiegelsymmetrische sichten derselben Sache wir sagen einfach nur damit wir nicht immer beides mitschleppen müssen Minimierung und Maximierung immer wieder mit erwähnen müssen sagen wir einfach das ist wäre betrachten Minimierungsproblem also wie das die SPD wollen die Länge der Rundturm minimieren so bald umbauen folgt diesen allgemeinen Schema dass wir mit dem wir eigenen sie gestartet sind heute und arbeitet mit oben und dann Schranken ist auf den wird in denn die optimale Lösung hätte und mit diesen oder und unteren Schranken die werden angewandt um möglichst häufig Teil Bäume zu tun also abzuschneiden weil man weiß dass sie die lief nutzlos sind so was ist die fundamentale Idee von Bahn scheinbar und ist uns allen aber zu sehr häufig eingesetzte Technik und durchaus erfolgreich eingesetzte Technik nehmen wir mal an wir wüssten zu während sich ist ist ein Minimierungsproblem wir wollen möglichst kleine 1 möglich eine zulässige Lösung mit möglichst kleinen sie Funktionswert haben nehmen wir mal an wir wüssten eine obere Schranke also eine Zahl von der wir wissen dass der optimale wert nicht schlechter ist als nur besser sein kann das die beste Lösung nur billiger sein kann als als der Welt dies das kriegen wir ganz schnell solle also obere Schranke weil die jede zulässige Lösung diese irgendwie konstruiert haben jedes für Sie gelesen gehören wie konstruiert haben deren Kosten wert ist so eine obere Schranke ja der optimal wird kann nicht schlechter sein als der Wert einer beliebig hergenommen zu Lösung gerade die Vision eines optimalen ist dass er der Beste ist und zulässigen Lösung so jetzt immer noch einen Schritt weiter wenn die Nummer 1 wir sind jetzt in der Situation nur um die wir die ganze Zeit über die wir die ganze Zeit reden in der Situation wir sind an einem Teil Baum hier wir haben vielleicht schon Partei beim ausgeschnitten das ist jetzt hier dabei neuen weniger relevant wir sind jetzt dabei einen neuen Teil Baum zu betrachten sind an diesen Knoten für wollen denn tun wenn Geld und wir nehmen mal an jeck wir wissen eine untere Schranke wir wissen eine untere Schranke dafür wie gut die beste Lösung da ist ja wir haben hier drinnen in diesem Teil bauen um den es geht haben wir eine Lösung die das ist die beste in diesem Teil bauen und dafür nehmen wir mal an wir wir wüssten nicht wir wissen nicht wie die aussieht wird es noch nicht was was Sie genau für einen für einen C Funktionswert hat aber was wir wissen ist sie ist garantiert nicht besser als dieses 11 von 11 von Frau von diesem Knoten V ja ja V auf dieser Folie ist dieser Knoten hier um die beste Lösung hier drin hat keinen besseren wird als er von Frau ich glaube dass man langsam mal wieder die Kralle zurückbringen jedes mal welche die Tafeln dir bringe ich immer ein Stück Kreide nach da vorne hier wieder zurück zum zum Tisch so was hilft uns das wir machen wenn wir das wüssten es gibt natürlich noch den Fall dass das Ganze nicht zulässig ist das das ist gar keine zulässige Lösung gibt in diesem Teil Baum dann können wir ja dann können wir natürlich unbeschadet auch die oder schon auf plus unendlich setzen das ist ein Sonderfall denn wenn nicht weiter betrachten dass das Konzept die grundlegende Idee ist hier wenn dieses LV größer ist als dieses dann können wir diesen Teil Baum unbeschadet abschneiden was heißt das dass ist eine obere Schranke für den optimalen wert da optimal das ist garantiert nicht schlechter als das L von ist eine untere Schranke für den besten wird innerhalb von diesen Teil brauche ich glaube diese Kette diese ungleichen es Kette soll dich etwas erweitern um damit das kann klarer wird ja also der das Ziel viel Funktions- von irgend einer Lösung im Tal bauen der ist größere gleich mehr im Teil Baum mit mit Wurzel mit wozu Frau der ist größer gleich 11 von Frau das ist gerade Definition von 11 von vor das ist größer echt größer ja echt größer das entscheidend und das ist nach Definition von größer gleich wieder den optimalen es wäre Funktions- wert das heißt also dank
diesen echt größer hier kann unmöglich eine optimale Lösung in diesem Teil Wochen und sein das das Grundkonzept wenn wir so ein L von Frauen und so ein haben wir bekommen das haben wir eben gesehen das ist dass das ist das peinlich ist überhaupt wenn eine zulässige Lösung wäre vielleicht ein möglichst gut gewählte zulässige Lösung vielleicht mit irgendwelchen Heuristiken basteln wir uns möglichst gute nicht optimal aber möglichst gute Lösung zusammen so so gut wie wir sie halt mal so eben schnell hin Gefrickel bekommen die große spannende Frage ist dann natürlich wie wir denn diese untere Schranke dieses L von Frau hinkriegen können die den Zügen Funktionswert jeder Lösung in diesem Teil Raum nach unten abschätzt wir sind auch noch nicht ganz fertig wenn wenn wir im Laufe des Prozesses eine ja wenn wir wenn wir einen wenn wir eine wenn diese unter schauen wir wie wir berechnen gleich einen der dem Ziel Funktionswert einer Lösung ist die wir schon gefunden haben also im Laufe des Bornemann und des Finnen auch immer mal wieder löst zulässige Lösungen was machen wir hier aber genau wenn wenn diese unter Schranke gleichen sie Funktionswert eine Lösung ist die wir schon gewohnt haben brauchen wir auch nicht mehr weiter durchzugehen weil wir haben wir wissen es gibt nichts Bessres hier drin ist das was schon gefunden haben so wir müssen 2 Dinge berechnen für Son Schirmer einerseits das das ist global andererseits das das Lokal das ist für jeden Einzelnen Knoten Entscheidungsbaum unterschiedlich so wir wollen natürlich nicht und und obere Schranke für den optimalen wird also dass der optimal wird gerade die schlechter ist als das war nicht irgendeine obere Schranke finden aber sondern eine möglichst gute wir können zum Beispiel anfangen etwa 1 mit einer schlechten einfach eine schlechte obere Schranke aber in Aachen nach kriegen wir dann das obere schon wir können zum Beispiel eine ganz schlechte oben schon der Anfang nehmen sie in dem sich die Rundtouren her dass die SPD in dem wir einfach alle kannten die dann vorkommen alle kannten die wir potenziell als Kandidaten haben er deren Länge aufsummieren das nur sehr sehr schlechte obere Schranke aber es ist erstmal mal obere Schranke hat die würden im Laufe des allgemein sehr schnell besser oder wir können was anderes machen wir können uns eine ganz primitive Heuristik überlegen für den Anfang immer wieder TSB als Beispiele aber wir nehmen uns nun besonders billige könnte mehr die Katze finde was zu dieser billig konstruierten Rundtour nehmen sie zweitbilligste kann der Herr wenn die jetzt kann wenn es keinen so Züge schließt dann nehmen sie auch mit dazu und muss tritt billigste sie könnte er so lange sich das Ergebnis immer noch zum und erweitern zu lange nicht mit solange nicht auf eine Teilmenge der Knoten Einzüge geschlossenes machen wir so mal weiter damit Krieger keine optimale Lösung in dem allgemein aber schon typischerweise mit keine ganz schlechte und deren länger deren Gesamtlänge ist unser 1. unser 1. obere Schranke wo wir wissen die optimal wird es garantiert nicht schlechter als das so und dieses das wird im Laufe der Zeit immer mehr verbessert wann immer wir in unserer Suche also wir machen hier tiefen Suche das heißt wir kommen öfters mal und zwar schon ziemlich schnell bei Blättern an und wann immer wir eine zulässige Lösung finden also ein Blatt da das wir geradezu lösen Lösungen die 1 zu 10. die ein Element liegen Teilmengen der Lösungsmenge dann immer wieder zulässige Lösung finden deren Kosten Wert besser ist als unser aktuellen wert setzen wir natürlich diesen Schritt runter auf den Kosten der dieser neu gefunden zulässige Lösung so wollen genau diese unterscheiden Berechnung der gibt es eine kleine Chance dabei werden ich dazu kommen wie die schon Berechnung aussieht Nägel wenn nicht gleich dazu kommen wir einmal ist man dazu kommen diese unterstanden Berechnung kann zufällig auch mal als einen als 1 1 1 bei Prada hat es ist Zeit dafür ist glaube ich hier nicht das beste Wort hier dicht beitrat hat eigentlich geschrieben oder mit einem Mann geschrieben glaube ich ich dem Beitrag ist das Wort als ein Nebenprodukt eine kann es sein dass eine zulässige Lösung auch mal generiert und wenn die denn das Unwetter 13 wert dann werden wir den wird natürlich auch entsprechend heruntersetzen so wenn wir jetzt die Durchsuchung des Grafen das geeignet wären also wie schon sagte tiefen da finden wir sehr häufig sehr schnell schon Blätter und wenn wir vielleicht gucken dass wir tendenziell heuristisch uns von Anfang an versuchen in möglichst in gute Richtungen als 1. unter so gehen vielversprechende Richtungen nativen sowas 1. durchzugehen und weniger viel versprechende Richtungen später durch zu durchzugehen dann sind die dann dann würde das würde ein Effekt bei sein dass dieses sehr häufig zu guten immer besseren werden reduziert sein so dass die obere Schranke im Laufe des Algorithmus ziemlich bald schon sehr scharf hat also schon nicht mehr so unendlich weit weg ist von der von der optimalen von dem Werte der der optimale Lösung dass man sagt die optimale Lösung kann nicht schlechter sollen dass Sie die Definition von aber sie ist auch nicht mehr sehr viel besser das ist wirklich die ihre Situation so jetzt kommt der schwierige Teil für den muss immer noch gedrückt haben wie können wir diese 11 von Frau Wert hier berechnen also diese werde damit sind wir durch das Dorf dessen wurde gesagt wie man das macht und fertig ich wüsste keine Alternative Strategie die irgendjemand mal ausprobiert hätte also das was wir auf der letzten Folie gesehen hätten gesehen haben jetzt 11 von vor und da gibt es einen Riesenhaufen von Literatur untere Schranken für die verschiedensten Problemstellungen für TSB und was da so alles gibt an in beschweren Problemen da gibt es ein Riesen Bereich von Literatur wie man geeignete unterer Schranken definieren kann die mehr geschafft sind wir haben aber im Prinzip 1 gemeinsam ich will schließen nur mit zum Paar einleitenden Worten dass wenn dann beim nächsten mal genau anschauen wir werden wir werden und wir werden die Problemstellung Relax ihren an TSP wird das glaube ich ich glaube TSB müsste irgendwo vorkommen
ja schon wieso wo ja
ja das ist aber gar nicht mal die die ich
meinte dass schon der fortgeschrittene
okay vielleicht nur ganz kurz sie können das TSP Relax ihren das heißt der Lösungsraum erweitern indem sie sagen nicht nur die Rundtouren sind zulässige Lösung sondern alles was so ähnlich aussieht wie Rundtouren nämlich alles was auf und touren und in kleinere und ja Sie haben hier 4 Knoten auf den Gipfel kleine Rundtour sie haben mir nochmal 3 Knoten auf den gibt es eine kleine Rundtour hier funktioniert nicht nur die echten Rundtouren sind sind zulässig sondern auch solche zerfallende Rundtouren ja das Öl Erziehung Relax Zeichen hier auf der Folie das bedeutet sie das noch Lösung zu die sie eigentlich nicht haben wollen auf kontrolliert Art und Weise dieses Problem dieses Optimierungsproblem lässt sich viel einfacher lösen lässt sich sehr effizient lösen es keinen Befehl schweres Problem ist ein Bulle mehr lösbares Problem und die Optimalwert hierfür ist eine untere Schranke für den optimalen Wert für das ursprüngliche Problem eine Rundtour kann nicht besser sein als die beste so vielleicht oder auch nicht zerfallen und war bei aller Rundtouren sind hier natürlich noch drinnen Lösungsmenge das heißt also wenn wir wenn wir den Lösungsmittel Raum erweitern wir das jetzt getan haben und dann dann kann der Optimalwert nur besser werden natürlich ja weil bisher so war drin aller des kommen um bei Lösungen zu da kann es vielleicht bessere Lösung geben offensichtlich den hier es offensichtlich dass man besser lösen als jede Rundtour kommen sich das an über den sich in Ruhe bin optimal Rundtour aussehen würde die kann ich der mit denen sich die 3 Cluster nochmal vielleicht 1 Million Kilometer weit auseinander um ganz deutlich zu machen warum die Rundtour sie warum das Optimum hier sicherlich nicht auf der echten unter angenommen wird und diese optimal wird immer leicht brechen kann es untere Schranke für für die Länge der war und das ist eines der beiden Grundprinzipien wie man die Optik Lehmann D R wie wie man eine eine untere Schranke zum L von vor gewinnen kann es aber Grundprinzip ist dass man an der Zielfunktion bis zum Rumpf regelt dass man Bedingungen Aust raus nimmt und in die Zielfunktion reinsteckt so aber das wenn wir beim nächsten Mal genau betrachten bei den zweiten Fall soll die noch dazu sagen da kommt ein alter Bekannter aus der Mathematik wieder auf sie zu und nämlich der lag Rausch sie erinnern sich vielleicht am anderer das Rauschen wurde Multiplikatoren oder ähnliches das verbauen sie wieder eine Rolle spielen was sich nicht alleine ist nicht weiter schlimm man kann das was wir hier betrachten auch ohne diese Vorgänge seiner Mathematik verstehen soll möchte mich für heute bedanken tut mir leid dass ist hier wieder mal eine Technik ein bisschen oder sagen also an meinem Vermögen mit der Technik umzugehen gehapert hat möchte ich ihn dann noch einen schönen Tag und schöne Woche wünschen trotz das angekündigten wird das
Loading...
Feedback
hidden