Descision-Based Approaches - Descision Trees / Branch and Bound / Constraint Programming

Video thumbnail (Frame 0) Video thumbnail (Frame 12479) Video thumbnail (Frame 15591) Video thumbnail (Frame 20934) Video thumbnail (Frame 23526) Video thumbnail (Frame 26277) Video thumbnail (Frame 36116) Video thumbnail (Frame 49325) Video thumbnail (Frame 62534) Video thumbnail (Frame 75743) Video thumbnail (Frame 88952) Video thumbnail (Frame 102161) Video thumbnail (Frame 108211) Video thumbnail (Frame 110309) Video thumbnail (Frame 112321) Video thumbnail (Frame 114559) Video thumbnail (Frame 116377) Video thumbnail (Frame 128257) Video thumbnail (Frame 130374) Video thumbnail (Frame 136012)
Video in TIB AV-Portal: Descision-Based Approaches - Descision Trees / Branch and Bound / Constraint Programming

Formal Metadata

Title
Descision-Based Approaches - Descision Trees / Branch and Bound / Constraint Programming
Alternative Title
Descision Trees / Branch and Bound / Constraint Programming
Title of Series
Part Number
9
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 Stress (mechanics) Computer programming Graph (mathematics) Model theory Constraint (mathematics) Zielfunktion Function (mathematics) Equation Inequality (mathematics) Mathematical structure Variable (mathematics) Lagrange-Methode Mathematics Matrix (mathematics) Network topology Zusammenhang <Mathematik> Vector space Supremum Valuation using multiples Vertex (graph theory) Nichtlineares Gleichungssystem Summation Length Linear map Addition Standard deviation Decision theory Spanning tree Drop (liquid) Set (mathematics) Variable (mathematics) Numerical analysis Symmetric matrix Travelling salesman problem Function (mathematics) Network topology Relation <Mathematik> Mathematical optimization Untere Schranke Relaxation Combinatorics
Constraint (mathematics) Decision theory Constraint (mathematics) Model theory Optimization problem Symplectic manifold Maxima and minima Feasibility study Drop (liquid) Insertion loss Zielfunktion Function (mathematics) Zielfunktion Lagrange-Methode Variable (mathematics) Term (mathematics) Function (mathematics) Vector space Valuation using multiples Mathematical optimization Factorization Linear map
Kante Computer programming Graph (mathematics) Symplectic manifold Maxima and minima Linear programming Lösung <Mathematik> Variable (mathematics) Calculation Mathematics Symmetric matrix Network topology Travelling salesman problem Relaxation
Kante Graph (mathematics) Symplectic manifold Maxima and minima Linear programming Incidence algebra Set (mathematics) Zielfunktion Variable (mathematics) Symmetric matrix Network topology Travelling salesman problem Network topology
Kante Stress (mechanics) Graph (mathematics) Symplectic manifold Moment (mathematics) Spanning tree Maxima and minima Linear programming Variable (mathematics) Symmetric matrix Network topology Travelling salesman problem Network topology Vertex (graph theory) Untere Schranke Combinatorics
Kante Computer programming Stress (mechanics) State of matter Constraint (mathematics) Graph (mathematics) Direction (geometry) Symplectic manifold Maxima and minima Lösung <Mathematik> Zielfunktion Lagrange-Methode Energie Network topology Vector space Valuation using multiples Multiplication Compass (drafting) Optimization problem Laufzeit Feasibility study Linear programming Rounding Symmetric matrix Grand Unified Theory Logic Travelling salesman problem Network topology Mathematical optimization Untere Schranke
Kante Standard deviation Greatest element Direction (geometry) Lösung <Mathematik> Bound state Variable (mathematics) Subset Strategy game Summation Octahedron Decision tree learning Decision theory Optimization problem Laufzeit Integral element Variable (mathematics) Fraction (mathematics) Algebra Heuristic Plane (geometry) Constraint (mathematics) Real number Maxima and minima Decision tree learning Zielfunktion Number Solution set Network topology Valuation using multiples Ganzzahlige Lösung Spacetime Set theory Linear map INTEGRAL Raum <Mathematik> Maximum (disambiguation) Polygon Feasibility study Linear programming Set (mathematics) Subset Solution set Logic Travelling salesman problem Network topology Ecke Iteration Optimum Mathematical optimization Untere Schranke Relaxation Local ring Force
Ramification Kante Standard deviation Computer programming Greatest element Operations research Diagonal Constraint (mathematics) Direction (geometry) Maxima and minima Lösung <Mathematik> Bound state Variable (mathematics) Time domain Hausdorff space Mathematics Plane (geometry) Strategy game Network topology Ganzzahlige Lösung Supremum Vertical direction Codomain Gebiet <Mathematik> Game theory Motif (narrative) Adaptive optimization INTEGRAL Decision tree learning Duplex (telecommunications) Optimization problem Feasibility study Variable (mathematics) Fraction (mathematics) Logic Network topology Ecke Berechnung Iteration Finite set Diagonal Linie Mathematical optimization Integer Untere Schranke Force Combinatorics
Kante Computer programming Link (knot theory) Direction (geometry) Optimization problem Feasibility study Lösung <Mathematik> Variable (mathematics) Weight Variable (mathematics) Time domain Platte Plane (geometry) Symmetry (physics) Strategy game Network topology Ecke Diagonal Integer Absolute value Combinatorics
Zahl Link (knot theory) Strategy game Direction (geometry) Network topology Variable (mathematics)
Network topology
Commutative property Decision theory Laufzeit Lösung <Mathematik> Variable (mathematics)
Network topology Heuristic Variable (mathematics)
Decision theory Network topology Feasibility study Electric current Number
Zahl Consistency Constraint (mathematics) Graph (mathematics) Optimization problem Moment (mathematics) Feasibility study Set (mathematics) Variable (mathematics) Time domain Variable (mathematics) Number Time domain Mathematics Matrix (mathematics) Plane (geometry) Sheaf (mathematics) Codomain Electric current Reduction of order
Kante Consistency Constraint (mathematics) Graph (mathematics) Modulform Set (mathematics) Binary file Variable (mathematics) Equation Variable (mathematics) Time domain CW-Komplex Integral domain Graph (mathematics) Circle Vertex (graph theory) Electric current Hyperplane Arc (geometry)
Consistency Integral domain Graph (mathematics) Constraint (mathematics) Graph (mathematics) Modulform Vertex (graph theory) Binary file Variable (mathematics) Electric current Hyperplane Time domain
so genau sind die anderen immer so seine Haftstrafe Lernmaterialien an der TU Darmstadt so Lola Seitz
diese Folie ist nicht die letzte die wir bei der wenn es mal gestoppt haben sondern ein paar vor dem früher es ist auch ein Thema das eigentlich schon abgeschlossen haben ich muss nur noch ein kleiner Nachtrag dazu machen sie ändern sich vielleicht ich hatte einst Bäume eingeführt und ich hatte gesagt und 1 Bombe ist im Prinzip einen Baum mit einer zusätzlichen kannte oder anders formuliert ein Zügel mit baumartige Struktur noch dran ja das ist das Zusagen entzücke mit züge freien Strukturen noch dran gehängt alles zusammenhängt oder umgekehrt sagen ein Baum wo man einen Züge schließt in dem man noch eine weitere Kante zusätzlich hinzufügt so was sich aber dabei übersehen hatte was jetzt in dem wichtig ist wo wir stehen geblieben sind ist hier auf dieser Folie 1 wo immer etwas restriktiver definiert worden sind wir betrachten die Knoten nicht als austauschbar sondern wir in Betracht insbesondere den Knoten V 1 ist egal welche Hauptsache festgehalten und Sie sehen hier wie hier 1 Baum definiert wurde nämlich 2 Kanten sind der Zensur V 1 und auf dem Rest das des Grafen auf den Rest der Knoten die zum Spannen bauen das ist willkommen Äquivalent aussah das hier noch zusätzlich gefordert ist dass der Knoten V 1 auf diesen Titel ist also ein 1 Baum der den Knoten V 1 auf seinem Züge hat ist gerade 1 1 1 Bonn im Sinne dieser Folie wenn Sie sich denn vor 1 weg denken und sich nur noch den Rest betrachten diese anderen Knoten hier alle dann sehen Sie dass es ein spannender Baum auf den also dieselbe Definition nur etwas restriktiver eingeführt weil wir jetzt bei dem Thema bei dem wir stehen geblieben sind weil es dort uns die Arbeit das Leben deutlich erleichtert so wo waren wir stehen geblieben nicht weit weg von dem Thema Ballack rasch Standards Nationen worum geht es dabei die Idee ist also zunächst mal noch mal als Hintergrund worum geht es überhaupt es geht darum untere Schranken zu finden für Minimierungsproblem er sehr meine Instanz eines Minimierungsproblem das The wollen wir versuchen eine möglichst präzise untere Schranke für den Optimalwert dieses Minimierungsproblem dieser Instanzen des Problems zu finden aber das natürlich möglichst schnell das ist der Sinn der Sache bei Branchen Bau und schnell gute untere Schranken zu finden und die Grundidee ist auf der einen Seite haben gesehen die Zielfunktion für wenn die Zielfunktion komplex ist komplexer als hier hier sehr einfach es ist einfach eine längere Zielfunktion Summe der gewichteten Variablen Werte aber wenn in Situationen in die Zielfunktion komplexer es in den die Funktion der Punkt ist der uns das Leben schwer macht bei der Lösung des Problems das wir dann die Zielfunktion ersetzen durch eine einfachere Zielfunktion deren wert niemals größer ist als der Wert der eigentlichen Ziel Funktionen das gibt da natürlich eine obere Schranke wenn wir das mit dieser 90 und lösen oder was der Fall ist und was wir hier auch intensiver betrachtet haben noch einen sehr betrachtet wäre werden das wäre schon die dadurch generieren dass wir einen dass wir Bedingungen die die uns das Leben schwermachen dass wir die fallen lassen ja wir hatten zum Beispiel beim 1 Baum Relaxation hatten wir die Bedingung fallen gelassen dass dieser Cykel alle Knoten und er das Grafen enthält sondern wir lassen zu Zügel plus baumartige Strukturen muss alle muss alle Knoten des Grafen und aufsparen das ist eine Relaxation dieser scharfen Bedienung ersetzt durch eine schwächere Bedingung oder sogar ganz fallen lassen Sie einen sich die BR das hat den Fall auch betrachtet die Bedingung dass der Züge alle Knoten umfasst hat fallen lassen um den Preis dass solche sub Zügel dann möglich sind solche Strukturen die aus mehreren einzelnen sind separaten Zügen bestehende ja das ist immer wieder die Grundidee mehr hat man bisher nicht entdeckt aber das reicht auch damit kann damit ich denke ich übertreibe nicht wenn ich sage dass es Tausende von Publikationen geht die auf dieser Grundidee basieren die verschiedenste Problemstellung für der verschiedensten algorithmisch Ansätze so lagen Rausch der Name sagt schon das ist eine sehr klassische Vorgehensweise ist finden Sie auch wenn sie sich in Mathematik in Optimierung weiter vertiefen Dandridge falls Sie das machen würde Wirkung steuert auch eine große Rolle spielen auch im Zusammenhang mit ganz anderen Anwendungsgebieten wie beispielsweise also mit dem man mit Numerik mit Anwendungsgebieten der mehr weg so was ist die Idee die Idee ist wir lassen die Bedingungen zwar fallen in diesem Fall also insbesondere wenn wir bei der war lag sationen fahren wenn ja Bedingungen die wir immer als eine Matrix zusammenfassen ohne Einschränkung der Allgemeinheit können wir von Gleichungen reden müssen nicht unbedingt von Ungleichungen Gleichung können wir durch Einführung von neuen Variablen so Gleichungen machen Ungleichungen zugleich und vielleicht noch mal ganz kurz warum das geht wenn Sie A 1 X 1 plus bis n x n kleiner gleich des haben dann können Sie das zu einer Gleichung machen indem sie eine neue Variable für einführen 1 x 1 Plus in x im Fluss kleiner gleich wie diese Variablen bis man typischerweise mit es ab wollen weil sie im Englischen das Leck Variable heißt und dem deutschen Schlupf ich weiß nicht ganz genau was sich im deutschen hinter dem Wort Schlupf dabei verbirgt aber ich kann mich an eine mündliche Prüfung der genau 2 mündlichen Prüfungen enger mit 2 Studierende noch damals als ich in Bonn war als es um den komplementiert satt über den komplementären ging die beiden waren jetzt Fremdsprachen soll ich dazu sagen und die beiden haben der mündlichen Prüfung jeder hätten da immer permanent von komplementären Schlumpf gesprochen und dabei Sätze und ich wir mussten sie kann zurzeit das lachen verhalten weil er keine gute Situation ist ein Brief und Beisitzer plötzlich anfangen über das was der Prüfling der sagte zu lachen auch wenn das etwas ist was was mit der Sache mit den Prüfungsstoff eigentlich nichts zu tun hat so wir lassen Sie nicht ersatzlos fallen sondern wir bestrafen die Abweichung in dem wir sehen die Zielfunktion reinsetzen mit nur so genannten Rauschen Multiplikatoren das heißt jeder einzelne wir das letzte Mal schon aufgedröselt für jede einzelne Bedingungen kann der ursprünglichen Menge der Bedingungen ihren ursprünglichen Ihnen gleich ins System haben Sie hier einen Summanden drin der eine Multiplikatoren multipliziert mit mit der Differenz von einer dieser Art von einer dieser Zeilen in gleichen ist so und die sie bekommen das haben wir beim letzten Mal auch schon
gesehen egal welche welche Multiplikatoren wehrte sie hier
einsetzen das was Sie herausbekommen bei diesen Optimierungsproblem wo die Nebenbedingungen eben nicht mehr mehr so aus so ärgerlich stehen oh wo Sie wo sie die über geführt haben in einer immer noch genau so ein letzendlich gemacht genau so einfach strukturierte Zielfunktion wie vorher das entscheidend wichtig dass die Struktur der Zielfunktion ist sich nicht jetzt stattdessen verschlechtert verkompliziert hat denn wenn sich das mal in Gedanken alles vorstellen letztendlich wenn Sie das mal auseinander dröseln der zusammenfassen alle Terme mit X zusammenfassen und alle Terme ohne X zusammenfassen dann ist das nichts andres wieder als eine als eine Funktionen erst einen hier Funktion von dieser Struktur minus einem konstanten Thermen den können Sie aber nicht rausschmeißen bitte fragen ach so Beschuldigung der sie am von ganz recht hier sollte ein gleichstellen genau das war der Sinn der Sache vielen Dank so vielleicht noch mal ganz kurz das was da steht ist da nichts muss als für die transponiert Verlusten lahmender transponiert was wir minimieren wollen mal x minus lahmender transponiert und wenn Sie anschauen dieser Term hängt nicht von X ab der ist für alle x Werte die sie finden können der selber das heißt den können wir einfach streichen ersatzlos und dann sehen Sie die Struktur der Zielfunktion hat sich nicht verschlechtert haben sich nur die vor Faktoren für Ex geändert dafür sind sind sie aber die diese Nebenbedingungen los geworden sowohl
das hatten wir alles schon bitte sprochen brauche ich noch mal rüber zu gehen hier waren wir stehen geblieben und hier ist es jetzt noch mal wichtig das wir den eines warum exakt so diese Begriff so verwenden wir auf dieser Folie definiert wurde was ich eingangs nochmal erläutert hatte so sich sind diese früher auch schon mal durchgegangen das ist eine Formulierung dass die SPD als ganzer nicht länger Optimierung ganze so ging es wohl gibt Ihnen einen Eindruck zu dem womit wir uns ausgiebig im nächsten Semester wieder eine algorithmische Modellierung befassen nämlich Modellierung von Problemstellungen formalen Sprachen die die dafür gedacht sind aber auch in anderen Problemstellung wie hier ganz heiß wie als ob die Währungsprobleme in gewisser Weise kann man sagen ihr P ist eine Sprache und das ist der Ausdruck mit dem wir dass die SPD in der Sprache modellieren Mathematik ist immer auch eine Sprache es ist nicht nur einen Lösungs Tool ist nicht nur Rechnen oder ähnliches ist nicht mehr beweisen es ist immer auch 1 eine Möglichkeit um bestimmte Sachverhalte präzise und unzweideutig ausdrücken zu können und wenn wir es schaffen sie die eine einer eine Sache in einem bestimmten Form auszudrücken einer bestimmten eingeschränkt vorgegebenen Form so wie hier durch die Sprache ihrer P dann hat es noch den zusätzlichen Vorteil dass wir dann Löser für die die diese eingeschränkte Sprache verstehen und damit und mit ins Dorf mit Problemstellung muss in dieser Stadt in dieser Sprache formuliert werden können umgehen können dass wir die darauf anwenden können so sehr man sich was was die Bedeutung war ich hier die die diese 1. dieser 1. Satz von Bedingungen sagt letztendlich dass wir keine 2 kann er das das die dass sie dieses wird so nicht haben können die hier ja den eine der man in diesem Satz von Bedingung ist die hier und hier ist es Kompliment und die Bedienung sagt das ist mindestens eine Kante nein die Bedingung sagt umgekehrt dass innerhalb von S nicht so viele kann enthalten sein dürfen die Knoten und sind und das ist genau bei so Tour Verletzten der auf einer solchen so Tour 3 Knoten 3 Kanten das ist für für dieses S hier ist durch die durch die entsprechende Bedingung im 1. Satz von Bedingungen ausgeschlossen 2. Bedingungen sagt ja dass das irgendwie so rund oder jeder Knoten ist mit genau 2 Kanten Änderung unter Incident 3. Bedingungen sagt es sollen insgesamt er könnten diese unter seinen dass man schon gesagt ich glaube diese Bedingung 3 ist redundant ich glaube nicht dass man sie wirklich braucht es meines achten schon durch diese Bedingung 4 erzwungen durch die bedient den Satz von Bedingungen arabisch 2 und am Ende sagen wir noch die x-Werte sollen alle 0 1 1 1 bedeutet die Kante ist im darunter drin 0 bedeutet sie ist nicht rein so
jetzt machen wir hier drauf und überrascht Relaxation und was wäre was wir sagen ist wir nehmen
diese Bedingung 2 er die Saat für jeden für kannte für den Einstellung für jeden Knoten jeder Knoten muss mit genau 2 Kanten endet Tour Inzidenz sein das ersetzen wird
dadurch also erst mal teilen wir das auf das 5 und 6 nichts anderes als eine Aufteilung arabisch 2 hier ist eine
Menge von Bedingungen nämlich für jeden Knoten eine Bedingung und wir haben
jetzt den Knoten eines ausgesiedelt in die Bedingung arabisch 6 und alle anderen Knoten so noch eine Bedingung arabisch 5 drin und Arabisch streichen wir raus das ist die Bedingungen die wir rausschmeißen die wir fallen lassen um sie dann in der Zielfunktion mittlerer schmallippiger aufzunehmen und wenn wir das haben das wir genau wieder bei der Situation von dem eines Baum mit dem wir heute gestartet sind sie haben die bitte wissen dass sie wieder bei dem mittleren wird sie haben für den Knoten mit der Nummer 1 die Bedingung dass genau 2 Kanten Inzidenz sind nur Bestecks ist ja weiterhin Teil des Bilder der das der Erde Bedienungs- Menge und für die für die anderen Knoten ansonsten was haben Sie da noch für Bedingungen diese Bedingung dass genau 2 keinen Sie denn das ist fallen gelassen worden für den roten was haben sie noch für
Bedingungen sie haben weiterhin die Bedingung dass das Ganze hier zusammenhängt ist an dieser Stelle wir das jetzt plötzlich nicht mehr redundant das ist der Punkt hier in dieser Formulierung auf dieser Folie ist meines Erachtens die Bedingung 3 redundant aber in dem Moment wenn wir jetzt 2 für fast für alle Knoten bis auf den den 1. Knoten rausschmeißen ist diese Bedingung nicht mehr dran sondern die wird jetzt wichtig dafür zu sorgen dass tatsächlich so wie sich das Fehlen eines bauen gehört hier die Anzahl der nach der kannten ja sie das meinem spannen Baum ist die Anzahl der Kanten eines weniger die Anzahl der Knoten und wenn Sie also gelogen haben das heißt eine Kante zusätzlich zum Spannen Baum ist bald beides identisch mit dem so das heißt
also wenn wir diese belegen fallen lassen dann sind aber genau bei der Situation die wir vorher auch waren nämlich dass wir bei einem 1 baut dass wir einen 1 Baum als untere Schranke haben wollen vielleicht ich habe noch einen Punkt vergessen immer noch mal hier zurück
ich habe diesen dash hier vergessen nämlich es ist wenn wir wirklich uns nur die 1 wollen wir daher nehmen bei den vor 1 offen Züge drauf ist dann ist es sehr einfach einen optimalen 1 Baum zu er er es zu berechnen sie berechnen einen optimalen spannenden Baum auf einen anderen Knoten wie sie wie das geht wissen sie aus der geht es 2 und dann gucken Sie die beiden billigsten kannten die Vereins 1 mit Knoten hier mit anderen Knoten verbinden dann haben Sie ihren optimalen 1 bauen so der entscheidende
Unterschied ist jetzt der ja dass wir jetzt allgemeiner geworden sind wir haben zunächst einmal nur gesagt wir Galaxien das die SPD die Bedingung dass alle auf einem Zirkel drauf sind alle nur noch Anzüge Galaxien wir dahin gehend dass wir ein Gebilde fordern wollen das zusammenhängt ist ein enthält und genau 1 enthält und hoffen dann für das Beste dass wir damit sehr gute Lösung hier hier sind Sie aber einen Schritt weiter gegangen wir nehmen das wieder in die Zielfunktion auf mit einer raschen Multiplikatoren welche Multiplikatoren das sind das ist erst mal völlig beliebig und wir haben ich in dem es genau nach dieser in dieser Logik auf und haben andere Ziele Funktion mit modifizierten Kosten werden dass nicht mehr die Kosten Werte in den 1. Ansatz mit 1 beim sondern plus diese Werte was haben wir dadurch gewonnen wir haben mehr Flexibilität in der Optimierung gewonnen denn diese Land Rauschen Multiplikatoren sind so etwas wie Steuer uns wert sie können was sie zum wenn Sie ändern sich wir haben jetzt das Problem umgekehrt wären das Vorbringen auf etwas anderes reduziert nämlich dieser Branche Multiplikatoren so zu bestimmen das ist hier eine möglichst gute Schranke rauskommt und jetzt kann herumspielen jetzt gerne zum Beispiel sagen ich übertreibe mal hier sind Knoten mit großen gerade es macht Sinn Daniela gar schon Multiplikator wurde die Karte für diesen Knoten also sehr sehr mehr einen Multiplikator für letztendlich für jeden Knoten außerdem 1. Knoten es macht Sinn denn er rasch Multiplikator hier für besonders hochzusetzen sowohl das also hier eine große Bestrafung vorliegt oder dass es dass man heuristische Aussage vielleicht stimmt sie auch nicht das ist erst einmal eine Überlegung wie sie sein könnte ein Knoten der weit weg ist von von den ganzen Züge vielleicht ist das sogar die bessere holistische Herangehensweise da macht es Sinn vielleicht das zu fordern dass das Gefahr 2 da ist hier bei über solchen weit entfernten Blätter um etwas mehr dahin zu kommen das wir dass wir da dass sie um diesen Zügen möglichst groß zu machen also letztendlich heuristisch gesprochen worauf das hinausläuft ist wir wollen jeder Groschen Multiplikation Toren so bestimmen das möglichst viele Züge in der Lösung ist mit der Zielsetzung möglichst mit der unteren Schranke die hier durchbrechen sollte der optimale wert ist ja immer eine untere Schranke egal wie die mal Multiplikatoren gesetzt sind darum müssen uns nicht kümmern möglichst diese Runde schon wir möglichst nah an die an die mehr an diese diese größeren zu ersetzen an Anne an die tatsächlichen 1 zu 1 zu bekommen eine tat sich abgemagert eine und war wenn sich das vielleicht hier noch mal vorstellen ich stoße man richtig weg man das etwas exzentrischer ist wenn das weit weg voneinander entfernt ist sei es auch nicht schlimm das haben Sie in ein schönes haben Sie ja nicht sie haben vielleicht als optimale Lösung wenn das weit voneinander entfernt ist könnte es zum Beispiel so aussehen das ist natürlich noch keine so gute untere Schranke weil ihnen hier wenn sich vorstellen dass die beiden Teile sind eine Million Kilometer auseinander wollen wir Ihnen noch hier die Kante fehlt die also so dass sie noch mal eine Million Kilometer um drauf oder müssen also macht es Sinn die man kaufen die die Karte und so zu definieren dass zum war er das nach Möglichkeit dann in eine optimale Lösungen diese kann der mitgespielt kommt es nur heuristisch Überlegungen die Algorithmen mit dem man das optimiert wir sind dann wesentlich abstrakter das so die versuchen wirklich dann Sie gucken man guckt sich wirklich an der 4 Staaten ist wirklich lokale Suche wie wir sie ganz am Anfang der kennen gelernt haben so als Grundprinzip wir starten mit einem Satz von der komischen Multiplikatoren und gucken uns an in welche Richtung müssten wir die dieser deutschen Multiplikatoren ein kleines Stück weit ändern so das ist so dass wir zu einer Verbesserung der unteren Schranke kommt also zu einer Verschärfung zu einer Vergrößerung der und und schon Schritt für Schritt immer weiter und das schön Sache ist dass man wenn man immer der Meinung ist dass ein das viel viel zu viel Zeit kostet nun so Unterschrank an irgendeinem Knoten Branchen bauen Baum zu berechnen da kann auch jederzeit abbrechen und sagen dass es eben die untere Schranke mit der wir zufrieden sind und Hintergrund ist die Erfahrung ja wenn wenn sie doppelt so viel Laufzeit reingeben kriegen Sie keine doppelt so gutes Ergebnis hin sondern sie kritischen Hälfte der Laufzeit schon schon 90 Prozent gutes Ergebnis hin und wenn Sie die Laufzeit verdoppeln kann bei 95 Prozent gutes Ergebnissen 1. allgemeiner Erfahrung bei allem was sie machen auch bei dem was im täglichen Leben war sei es zum Beispiel Ford Optimierungsproblem Vorbereitung auf Prüfungen ja aber ich will sie nicht davon abhalten viel Energie und Zeit zu investieren in Prüfungen aber sie kann das ja selber mit doppelt so viel Zeit kriegt man nicht doppelt so gute das Ergebnis aus so
damit sind wir eigentlich eher mittlerer und schaue mir die Begattungen fertig wie gesagt allein zu diesem Thema nach schon Multiplikatoren gibt es mit Sicherheit Tausende von wissenschaftlichen Arbeiten aus den verschiedensten Bereichen verschiedenen Anwendungsgebieten aber wir wollen hier über eine ich will sie nur über alle einführen dass es keine vertiefend Veranstaltungen zu bestimmten Methodiken sondern ich will ihn mehr Überblick ist artig möglichst viele verschiedene Ideen und Ansätze und Umsetzungen der Umsatz uns denn hier vermitteln dafür dass wir das Thema hier so ist haben ein paar Beispiele gesehen man muss aber noch mal Folgendes klar setzen bisschen verlorengegangen ist nämlich dass sie wenn wir irgendwo im Entscheidungsbaum drin sind immer noch mal ganz zurück sehnen sich nach dem Bau und warum Entscheidungsbaum so und in typische Art und Weise nach links und rechts zu gehen ist das Design beispielsweise variable 1 hat den Wert 0 variable 1 hat den Wert 1 typisch nicht notwendig so aber typisch variable 2 hat den Wert 0 hat den Wert 1 hat den Wert 0 hat den Wert 1 so dass also diese 4 Ausgänge ich das mal da Nummer 1 Summe dann steht hier dann ist dann haben wir hier den Lösungsraum die Menge aller aller Lösungen implizit repräsentiert für die noch zusätzlich zu den Bedingungen des der Problemstellung hier steht x 1 gleich 0 x 2 gleich 0 hier steht X 1 gleich 0 x 2 gleich 1 hier steht X aus ist das jetzt x 1 gleich 1 2 zweimal und hier steht x 2 gleich 0 x 2 gleich 1 und wenn Sie beispielsweise wieder ans TSP denken dann ist das dann ist das ein sondern Knoten keine TSB mehr sondern gesucht ist eine Rundtour unter ein optimal runter und der zusätzlichen Bedingungen dass die Kante 1 und die kann der 2. 1 ist oder hier dass die Karte eines drin ist aber die kannte zwar nicht anders das heißt wir haben nicht mehr dieses ursprüngliche TSP und haben damit das Problem wenn Sie jetzt die in diesen Knoten also einen Knoten März schauen rächen wollen wer hilft Ihnen einer Galaxie und des SPD alleine überhaupt nichts was Sie brauchen ist eine Platzierung der Problemstellung TSP unter Bedienung dass bestimmte kann unseren Sohn oder bestimmte gar nicht um satt und das muss das ist die das die Problemstellung hier an die an dieser Stelle dass diese beiden kann man diese kann ist wenn diese kann das nicht sein diese Problemstellung die SPD mit solchen Zusatzbedingungen als zusätzlicher Import diese Problemstellung müssen Sie Relation und ich das ursprüngliche TSP vom 1. bis unterschlagen aber man am Beispiel wieder 1 mehr bei der 1 Baum Relaxation optimalen 1 bauen zu finden ist sie kennen beispielsweise den Algorithmus von Kruska für minimal spannen Bäume wenn sich daran erinnern können Sie sich vielleicht und dass sich jetzt als viel darüber sagen muss vorstellen dass groß kann auch mit solchen Bedingungen funktioniert er dass sie sagen dass sie eben paar kannten von vorne rein als gar nicht in dieser sortierten Liste da drin haben sollen von vorne rein Set gesetzt angehen und alle anderen und bestimmte kannten aus dem Grafen rausschmeißen das ist ja das geringste Problem mit jetzt kannten die gar nicht Grafen drin sind kann Grüß Gott natürlich sehr gut umgehen ignoriert also 6. den einfach nicht und und alle anderen kannten für die noch Wahlfreiheit besteht die werden wie sie das wie Sie das kennen sortiert und dann in sortierter Reihenfolge durchgegangen nach demselben Schema wenn die kann der einzige schließt wird sie nicht eingenommen wenn die keine keine zu beschließt wird sie eingenommen das Endergebnis der bevor ich sagen dass einfach das können Sie mir glauben oder kann es auch selber nachprüfen durch Literaturrecherche oder durch mich fragen das Endergebnis im sie keinen Beweis für die Korrektheit von Kursker sofort tragen auf diesen Fall und und können damit beweisen was rauskommt ist ein minimal Spanner vom unter der Bedingung dass die und die Kanten drin sind die und die Kanten nicht ernst und genauso können und in Bremen Weltpremiere dann müssen schwieriger also vergessen weil Prämisse die die sie fangen mit einem Knoten an und in jeder Iteration wenn sie einen Knoten eine kann den Sohn lassen da von einem Samenkorn sozusagen lassen Sie schrittweise der eben den Grafen wachsen in dem sie immer wie gesagt ein eine kann den zu nehmen ich denke man kann das man kann auch Primm entsprechend umändern aber es ein bisschen komische Logik aber es gibt ja schon ein paar könnten anders wird und es passt nicht zur Logik von Bremen das irgendwo anders weit weg von dem bisher Erreichten Gesichtsfeld da schon kannten sind die unbedingte reingehören also Micus funktioniert auf alle Fälle ein Beispiel für das was sie auf dieser Folie steht dann dass man immer schauen muss und aber das ist doch auch eigentlich meist gute Möglichkeiten gibt so wie hier beim TSB wenn das SP Relax ihren Bedingungen also eine Relation zu formulieren bei der ein und Ausschlüsse von einzelnen Features tatsächlich schon tatsächlich auch möglich sind mit zu optimieren so besonders gut funktioniert das bei ihr PS weil die Bedingung bedienen wie die wir hier haben das eine Kante nicht drin ist also der X ja gleich 0 es dass eine Kante drin ist Ex wird also gleich 1 ist das in den Jahren den Bedingungen das ist kein Problem es war vorher das Feuer LP war ist in in der auch Pläne zur sie zu diesen Bedingungen so wenn wir eine Problemstellung als IP formuliert haben dann ist das sehr sehr würde sehr sehr häufig sowohl in der Wissenschaft also in der Praxis dann so gehandhabt dass diese unteren Schranken der brechen wollen LP durch RP Relaxation berechnet werden was ist Apple Relaxation nochmal sie lassen die Bedingungen fallen das die Variablen ganzzahlig sind das bedeutet ganz konkret bei seinem Beispiel wie hier was und wie über sie dem Beispiel wird dann die SPD sie haben hier im ursprünglichen Problemstellung die Bedingung dass jeder Kanton Wert x 0 oder 1 ist also sie haben ursprünglich die Bedienung die X von einer Kante ist 0 oder 1 das ersetzen sie durch die Bedingung XE ist aus dem Intervall aus dem abgeschlossen damals nur oder 1 was heißt auf eine beliebige reelle Zahl sein also natürlich das natürlich dass ich darauf hinaus dass man beliebige Maschinen zu als sein im im Format Double oder was auch immer so warum macht man das das 1. Mal seit sehr schnell dafür gibt sie haben sich was ich dazu gesagt habe wie man sich das vorstellen kann der Lösungsraum
wenn wir Raum eines Liga Optimierungsproblem der Lösungsraum eines längeren Optimierungsproblem es kann man sich im dreidimensionalen so halbwegs noch vorstellen dass es immer so mein Lieblingsbeispiel dass ich dann immer zeichne ich muss es halt sind Schutzrechten so nicht nur und hinten gibst auch dann auch wieder ein Punkt wo die alle zusammenführen so war es also das ist jetzt ein Oktaeder wo ich jetzt noch diese Facette zusätzlich abgeschnitten habe lassen und sollt sinnvoll sein und ich habe ihn kurz skizziert wieder Lösungs Algorithmus vorgeht das ist im Prinzip lokale Suche wenn das die die die Richtung beispielsweise zum Optimum hin ist je weiter sie in die Richtung gehen umso besser sind die Lösungen so können sich das immer bei den Jahren Zielfunktion ja vorstellen dass Kinder sowie Algebra und irgendwo zufällig mit und einer Ecke an und wann dann irgendwie zufällig immer in Richtung Optimum und kommen einer bei Pin an theoretisch ist die Laufzeit dieses Algorithmus die was gilt Laufzeit katastrophal exponentiell praktisch muss man sagen die Erfahrungswerte ist typische die Anzahl der der also es kann es kann exponentiell viele viele der von solchen Ecken durchlaufen werden schlimmstenfalls man keiner Beispiel Producer ziehen wo das der Fall ist aber praktisch läuft es darauf hinaus das ist eine sehr kleine typischerweise nur sehr kleine Anzahl von Ecken die in diesem Polittalk die man durchlaufen muss bis man zu optimalen Ecke gekommen ist das ist der eine Grund warum man gerne LP Relax nutzt der zweite Grund ist der die wir vielleicht noch mal ins ins eindimensionale da ist so Lösungsraum eben nicht mehr ein dreidimensionales Polito sondern zweidimensionalen Polygon ja dass sie zweidimensionale Variante von demselben Konzept was Sie hier dreidimensional sehen vieldimensional kann ich ihn leider nicht anbieten ja wenn sich jetzt auf das Vereinen geht der die Menge der ganzen ganzzahligen Lösungen hier noch rein denken also so wie hier beispielsweise das ist der 3 das ist der Welt 4 wird 5 und so weiter und hier auch das ist vielleicht der wird 300 57 das ist der wird 358 und so weiter dann sehen Sie im Normalfall wenn das Beispiel nicht extrem pathologisch ist ist die optimale ganzzahlige Lösungen nicht gar so weit weg von der optimalen Ecke so dass man also gute untere Schranken hier bekommen kann das sind die Gründe warum man das warum man sehr intensiv insbesondere der Praxis sehr intensiv mit LG Relax Ehrungen hier arbeitet als untere Schranken bei solchen Verfahren die Branchen Bau und etwa auch bei anderen Verfahren die ebenfalls basieren auf auf und brechen und kann so es kann auch mal der zufällige Fall passieren das ist der dritte dash das sagt es kann auch mal Zufall vielleicht passieren so das ist die optimale Richtung Richtung Optimalität das kam natürlich passieren dass die optimale ganzzahlige Lösung ist wunderbar da das eine Erziehung ist heißt das die Wände die ganzheitliche Ecke gefunden haben wenn ich wenn wir optimal eckige von haben und dies zufällig auch ganz ehrlich dann ist das auch eine optimale Lösung für unsere ursprüngliche ganzzahliger Problemstellung wird aber im Allgemeinen nicht der Fall sein soll so leicht wird es einem nicht gemacht sondern im Normalfall das ist die optimale Ecke nicht ganz so ich das heißt also wir bekommen eine untere Schranke raus so und diese untere Schranke und wir wissen wenn wir und wenn diese unter schon geht es an diesem Club nicht greift wenn diese untere Schranke nicht das Kriterium er erfüllt mit dem wir diesen an diesen Knoten abschneiden können ja sie dass diese untere Schranke für diesen Knoten für diesen darunter liegenden Teil warum nicht höher ist als die bisher beste Gebühr von gefundene Lösung bisher dann müssen wir bahnen und die Frage ist ob es wie machen wir wie nie gehen wir da am besten vor welche Strategien verwendet er und was sich so im Laufe der Zeit wir reden wir hier von Ansätzen die schon ich denke mal Minimum 40 Jahre alt sind eigentlich eigentlich noch mehr und die schon seit dem Minimum 20 Jahren sehr sehr intensiv angewendet und erforscht werden was sich hier im Laufe der Zeit herauskristallisiert hat sind solche heuristischen regeln wenn es wenn wir wenn wir einen Schritt weiter gehen Entscheidungsbaum kann man denn noch da ja sie haben jetzt eine ganze Menge von von Zahlen also Xtra jetzt x 1 x 2 sind hier schon verarztet X 3 bis X Ende irgend so was oder XM sich an seine Knoten ne ganze Menge von Zahlen die nicht ganzzahlig sind nicht 0 oder 1 unserer irgendwo dazwischen und einer von denen man sie zum Beispiel um zunächst etwas dazwischen ist und Brandtschen darüber einmal seine gleich 0 oder 1 gleich 1 ja die die schon ganzzahlig sind die es keine zufällig einzelner Variablen einzelne kannten beim TSB ganzzahlig seinen schon das heißt also das sozusagen hundertprozentig geklärt ist ja die kann das ohne Busse mit den Weise die kann das hundertprozentig nicht drin wenn der Wert für x jetzt irgendwo zwischen 0 und 1 ist also bei 1 comma decimal 6 beispielsweise nur um einen ein konkretes Beispiel zu nennen so dass man also sollen wir aber sagen kann die Kante ist in dieser Lösung zu 60 Prozent drin was immer das heißen mag dann werden wir so eine so eine variable hernehmen die irgendwo zwischen 1 und 1 ist und wenn wir in der eine Richtung weiter Brandtschen dann setzen wir sie knallhart auf 0 und Inneneinrichtung weiter war dieses Signal auf und jetzt ist die Frage welche variabel wie viel und eine Rede die die sich als als ganz gut herauskristallisiert hat ist die am Maximum in für bildet die Rohre nämlich wir gucken uns die Variable an der Gewinn in die Variable die die die am nächsten bei 50 Prozent liegt bei 0 comma decimal 5 also am weitesten weg von der von der zulässigen Werte 0 und vor und auch am weitesten weg vom zuletzt wird 1 und die wenn wir uns jetzt mit dem nächsten Schritt wenn wir Anwenderbranchen sie 1 auf 0 und 1 auf 1 und dann 2 Teilmengen des aktuellen der aktuellen Teilmenge des Wissens Raums zu bekommen eine weitere Patches zunehmendes Lösungsraum warum das was ist was ist die heuristische der rassische Gedanke der dahinter warum das ganz gut funktioniert in der Praxis das natürlich mit Begleit- heuristische Begleit Überlegungen mit den mehr in der Psychologie nennt man das sekundäre Rationalisierung man macht irgendwas und hinterher überlegt man sich dass das wohl begründet ist rational begründet ist also ich will das jetzt nicht weiterspielen aber ist es nicht es ist natürlich ein bisschen mehr gegründet als als andere Fälle
von sekundärer Rationalisierung aus der Psychologie na ja wenn wir eine Variable Herrn in dieser Nabal bei 0 comma decimal 5 ist und wir sitzen Sie einmal auf 0 und 1 auf 1 dann haben wir einen sehr krassen Unterschied bis zu bisher erzwungen ein möglichst krassen Unterschied in der Hoffnung dass wir dann auch daran dass das dieser unterschied sich auszahlt dass wir dann vor möglichst schnell weg kommen von der Situation wie wir sie bisher konstruiert haben hin zu zu einer zu einer passenderen Situation zu unserm auskommt Probleme ganzheitlich ist dann gibt es aber auch um die genau das umgekehrte dem Minimum in für Visibility die wohl nämlich dass wir eine variable werden deren wird entweder möglichst nah bei 0 oder möglichst nah aber 1 ist auch wenn es wieder 0 und noch 1 ist dahinter steckt die Überlegung wenn wir immer dann als nächstes weiterverfolgen also beispielsweise die Variable der Wetterlage haben ist einer bei 0 dann verfolgen wir als nächstes den Fall weiter das wir das die war ja wie gehen Sie denn darunter inne in die Richtung wo diese Variable auf 0 gesetzt ist und dann immer die nächste variabel ist vielleicht der Name eines setzen die auf 1 gehen gehen Sie es in die Richtung und kommen dadurch vermutlich relativ schnell zu ganzzahlige Lösungen allerdings ist da die Erfahrung dass das dann doch eigenen er im Normalfall nicht so schnell voranschreitet weil der mehr den anderen Zweig wo das X er wurde überdeckt wird weit entferntes wenn X werden aber nur ist es eben sehr weit weg von 1 also die Hoffnung hierbei Maximen für billige wohl die sich nur Praxis durchaus häufiger mal erfüllt ist die wenn wir hier das das X möglichst der wegreißen von seinem jetzigen optimal wert dass wir dann auch viele andere Variablen mitreißen in die richtige Richtung die über die wir dann nicht mehr beherrschen müssen so Frauenbranchen das ist hier nur ganz ganz knapp erwähnt will ich auch nichts weiter groß aber ich würde vielleicht noch paar Worte sagen nur damit Sie wissen was wovon hier die Rede ist der Chor die Idee ist wir gucken uns die ganzen Kandidaten an vor vor Ort bevor wir Brandtschen bevor wir entscheiden über welche dieser nicht ganzzahligen war ja wenn wir den ersten mal die nächste Verzweigung definieren verzweigen definieren indem wir diese Variablen wird einmal nach links gehen auf 0 1 und rechts gehen auf einsetzen wir kommen uns die alle an und versuchen zu Hause zu schätzen je nachdem für jede dieser Variablen wie gut für die nächste ein Schritt tiefer die nächste untere Schranke und auf dieser Basis werden wir dann aus das wäre viel zu viel auf jetzt diese untere Schranke jetzt jeweils tatsächlich zu berechnen im Normalfall wäre das viel zu viel Aufwand deshalb ist die übliche Strategie das waren die untere Schranke dann nicht berechnet nicht bis zum bitteren Ende berechnet indem man wirklich den Simplex Algorithmus bis zur optimalen Ecke durchführt sondern man macht eine gewisse begrenzte Anzahl von Iterationen begann eine sehr begrenzte Anzahl von Ecken durchläuft und das ergibt das was man das dann erreicht hat das nennt man eher als Kriterium dafür welcher dieser verschiedenen Branching Möglichkeiten welche dieser Variablen vielleicht der beste Kandidat ist um jetzt auf die nächste Ebene zu verzweigen ist das Entwickler geworden oder gibt es da noch Verständnisprobleme gut ist auch jetzt hier für unsere Zwecke nicht so wichtig so wie er sich noch mal wir hatten ganz Anfang als wir über solche Ansätze generell gesprochen haben auch Strategien gesprochen dieser Siege die 2 kennen wie man durch einen Grafen durch einen Baum insbesondere hier durchlaufen kann von der Wurzel bis zu den einzelnen Blättern eine Möglichkeit das ist natürlich tiefen Suche ist sehr interessant für Bahn schon war und weil sie mit tiefen suche ja immer wieder sehr sehr frühzeitig zu zulässigen Lösungen kommen also zu blättern und jeder dieser zulässigen Lösung es eine Chance sie ihre obere schauen wir globale obere Schranke zu verschärfen ja aber jeder zulässige Lösung ist eine obere Schranke und wenn die besser ist also deren vom zitieren wird es eine Oberfranke für den Optimalwert bei Wahrnehmungsproblem wissen der mal bei minus minus Problem und wenn dieser dafür Funktionswert diese gefundene Lösung besser ist als die bisher gefundenen bist du der obere Schranke dann haben wir Verbesserungen erreicht was noch ist wenn Sie das im Felde so Brand im entschieden zu zubereiten Suche vergleichen breiten Suche ist überhaupt nicht geeignet für Branchen Bau und war ganz am Ende wenn Sie ganz unten angekommen sind kommen sie zum allerersten Mal zu zulässigen Lösungen das heißt also bis zum Ende der bis zum bitteren eines Algorithmus Sandsäcke hätten Sie wenn die beiden so an wenn keine schaust die die globale obere Schranke gegenüber der Initialen die sie ursprünglich irgendwie berichtet haben zuverbessern weiter period bei tiefen Suche nicht zu vergessen ist wenn sie gerade hinsetzen Kontrast setzen zu breiten suche ist der Speicherplatzbedarf es geringer breiten suchen Sie wissen dass ein Baum in die Breite massiv in die Breite geht das heißt also wenn sie viele will immer den ganzen runter gehen dann explodiert in ziemlich nahe der der Speicherplatz aktiven Suche da ist der der ist im was ist der der Speicherplatzbedarf proportional zur Tiefe des Bauens ist natürlich gewaltige weniger wir werden noch Beispiel sehen in Algorithmen bei denen es Sinn macht breiten Suche zu verwenden weil in Situationen bei algerische Ansätzen bei denen man dieses in die Breite gehen des Baumes verhindern kann oder sagen wir so das wird jetzt keine Trauerweide dieser Baum sondern so Bonsai-Bäumchen so dass man sich also tatsächlich auch leisten kann breiten suche zu machen ohne dass ein Gespräch um die Ohren fliegt das wird dann beim Thema dynamische Programmierung der Fall sein hier aber für für Brandtschen bauen des tiefen Suche besser oder sie ändern sich werden 3 Grundstrategien betrachtet Paar aktiven Suche breiten suche und besten suche das heißt also Sie haben wie Freund die ist wieder breit und auch tief nur allein im Allgemeinen und sie wir jetzt die am besten erscheine Möglichkeit um diese Front um einen Knoten zu zu weiterzuführen und das macht Sinn hier im im bei Brand Bauens was man als Kriterium welche in dieser Knoten immer die die Unterfamilie die man dafür berechnet hat je besser die ist und so umso so aussichtsreich ist dieser Knoten dass man in dieser Reihenfolge vor man kann natürlich auch beides miteinander variieren ja man man ist nicht gezwungen Motiven suchen zu machen oder nur dessen Suche oder nur breiten Suche sein man kann auch variieren man kann vielleicht am Anfang mit der breiten Suche beginnen das ist durchaus nicht falsch bis das 1 zu viel wird das ist eine der Baum so breit wird und dann Anfang mit besten so oder mit tiefen so weiterzugehen man kann auch zwischen tiefen Suche und besten suche in der hybride Verfahren verwenden und so weiter also nehmen Sie diese 3 die grundlegenden Ansätze jetzt nicht als 3 verschiedene Welten was man als Dinge die man durchaus miteinander kombinieren kann so jetzt immer mehr Branchen Bau und fertig jetzt kommen wir zu einer ganz anderen Situation Barbara Schon war und ist es in
der Hand dass wir ein Optimierungsproblem haben denn sie reden ja wir reden ja hier von oberen und unteren Schranken auf dem Ziel Funktionswert damit ist die geben es muss Optimierungsproblem sein hätten selber keine Ziele Funktionswerte wir werden jetzt eine andere Technik auf dem Entscheidungsbaum betrachten die in der nennt die zu auch auf Optimierungsprobleme anwendbar ist aber von der Logik her eigentlich er gedacht ist für reine Lösbarkeit Problem das heißt also wo sie nicht eine optimale Lösung finden wollen sondern einer sondern wo Sie zufrieden sind wenn sie wo sie glücklich sind wenn sie überhaupt eine zulässige Lösung Beispiel wieder Stundenplan Erstellung für ich für eine Universität wann und in welchen Raum wird welche Veranstaltung platziert da kann man ja schon froh sein wenn man überhaupt eine zulässige Lösung gefunden hat oder eine möglichst wenig unzulässige Lösung da brauche man über Optimierung gar nicht mehr groß nachdenken dass wir sagen da das Sahnehäubchen dass man sich dann wenn gar nicht mehr leisten kann so aber lässt sich auch auf Optimierungsprobleme genauso durchaus anwenden haben aber wir betrachten das vor allem hier als so wie es gedacht ist sowie seiner Natur wolle man spricht für einen des Probleme so kann es vereinzelt ist erkennbar CSP das ist aus der künstlichen Intelligenz heraus aus diesem Fachgebiet Informatik ebenfalls 1 für sich eine große wissenschaftliche Richtung was ihnen gesprochen habe Brandt Unbound hat seine ursprünglich er in Bereichen gar nicht mal um den Informatik in Mathematik und Ökonomie Stichwort berichten Research das ist das Gebiet Unternehmensforschung was sich was versucht er dir optimale Lösungen für Planungsprobleme mehr aller Art zu zu berechnen daher kommen solche Ansätze gebrannt und der historische Hintergrund für solche Problemstellungen wie hier es ist er künstliche Intelligenz wo wo dieser Ansatz ursprünglich entwickelt worden sind ich weiß nicht im Studium kommt mindestens einmal pro Loch glaube ich vor mich oder in DKE glaube ich an DKE seit dem das was okay ist es nur mit denen die nicht weiter wichtig ist aber für den von Ihnen die sich da man mit Prolog aus eingesetzt haben oder demnächst vielleicht auseinandersetzen werden Prolog ist ein anderes ist die die Natur von Prolog ist es ist eine Programmiersprache allein für dieses Wort würde ich von der Prolog Advokaten schon geprügelt werden sich das alte Programmiersprache benennen nenne mehr es ist ein nicht Sprache in der versucht wird letztendlich eine Lösung zu finden durch Berechnungen von Widersprüchen Teile der Lösungs immer er zur Erde zu entdecken dass Teile der Lösungs Räume nicht dass die dass die leer sind und so weiter sodass am Ende man dann natürlich auch mit relativ wenig Aufwand Lösung findet das ist das ist unqualifiziert was ich sage ich versuche eine gewisse Brücke zu schlagen zur um zu erklären was das mit gänzlich in die gern zu tun hat wo lag er auch herkommt als als ein Beispiel das Ihnen vielleicht geläufig ist nur Männer Vorstellungen zu geben sofern sie meine Prolog zu tun haben worum hier eigentlich geht ansonsten vergessen Sie diesen Kommentar wiederfinden beschäftigen ist jetzt hier mit so wie formulieren wir so ein also ganz Schwänze ist Action heißt Bedingungen dafür nicht man sagt im Englischen von für um Bedingungen zu erfüllen und man sagt auch dass er das Vereins Bedingungen befriedigen über den befriedigen nach gut sollte man vielleicht in Deutsch noch besser bei erfüllen bleiben so was wir generell abstrakt haben wir den gleichen Beispiel sehen aber wissen ja nicht an diese abstrakte Sichtweise denke ich schon einigermaßen gewöhnt wir haben Variablen jede Variable hat eine endlich hier man eine endliche Domäne haben wie sagt man im in der Mathematik es gibt in den den Wertebereich das ist die und einer Funktion bitte Definitionsbereich in werde Bereich nicht so so so der also die hier die Domäne ist der Definitionsbereich wenn wir in dieser Begriff aus der Mathematik geläufiger ist Verena hier von er erfahren endlichen also zum Beispiel beim TSB die Variablen sind die 0 1 Variablen auf den einzelnen kannten das waren eine endliche Menge von Variablen jeweils mit einer endlichen und so und dann haben wir nehmen Bedingungen das ist Ihnen jetzt auch nichts Neues bei dem ganzen Thema Linie ob denen ganze ich die Optimierung hat mir auch Bedingungen die einschränken dass bestimmte Kombinationen von von Variablen Werten zulässig sind und einer Kombination von meinem werden sie nicht so dass ich einmal beim TSB beispielsweise oft genug gesehen die Belegung von der von den einzelnen kann variabel mit 0 1 werden die insgesamt eine Rundtour ergeben sind zulässig die also nicht zulässig oder werden das andere Beispiele Mertsching weich oder wenn noch mehr Beispiel aber denen man mich in immer die Kanten Werte 0 1 so dass keine 2 Kanten mit 1 wert ein gemeinsam in gelogen haben dass die zulässigen Lösung für das Mädchen Problem das in die das Nikons eines dafür so eine Lösung ist dann eben eine eine Belegung der einzelnen Variablen mit werden so dass die Bedingungen allesamt erfüllt sind und wir betrachten uns hier sehen Sie das Wort Reue ahnte dass es wirklich ein Spielzeug oder ein Spiel Beispiel kein Mensch will diese Problemstellung möglich Praxis irgendwie lösen aber es ist so etwas wie ein Arbeitstier Arbeits- Arbeitspferd Flut frei da die Fruchtfliege also Menschen hat man oft für Arbeitstier Arbeit für Arbeitswelt für der Flut Flamme weil weil in der Biologie die Fruchtfliege für alles mögliche verwendet wird ohne dass man sich für geführte die vor 4 interessiert haben worum geht es da das hat nix mit Sudoku zu tun auch wenn es vielleicht offen Anfang so aussieht sie haben ein Schachbrett das muss nicht genau 8 Calls 8 sein kann auch viel kurz wir oder eine Million Kreuz eine Million ist egal Hauptsache quadratisch so ja also das soll sein und Sie wissen wenn Sie eine Dame irgendwo platzieren eine Schacht Dame das sehe in dieser in den in der horizontal in der Vertikalen und den beiden Diagonalen sie nun schlagen kann und das heißt also für das Chris Problem für das Darmproblemen also das ist die Dame sein sind diese Felder alle wenn ich die Damen platziere verbrannt das gilt nicht mehr ich kann aber beispielsweise
hier eine zweite Dame hinsetzen ohne dass sie sich gegenseitig schlagen können und genau darum geht es dass sie möglichst viele Damen hinsetzen auf diese Schachbrett haben so darf die jetzt auch alle verbrannt so dass sie sich gegenseitig nicht schlagen können jetzt würde zum Beispiel hier was gehen und hier würde noch was gehen beispielsweise ist es mal so und so und hier und vor das war es reiner Zufall dass ich das so hingekriegt habe dass ich wer 40 die oberste und die zweit und musste der Autor ist aber blöd ich muss die beiden also umsetzen so heißt das jetzt nein das waren sie waren okay also sie wissen wir 2 aufs dahinläuft ich hab's jetzt essen Optimierungsproblem formuliert möglichst viele Damen zu platzieren traditionellen werden gerade eben gesagt solche Ansätze die Idee solche Ansätze ist wißt Packeis Probleme zu zu lösen und dass das Packeis Problem ist wir wollen wirklich viele Damen aufnehmen N Kreuz enden Schachbrett platzieren und sie werden jetzt wenn wir wenn uns denn dem des über mehr setzt Ansätze näher betrachten werden können Sie gleich immer mit denken das was hier Lösbarkeit ist ist automatisch auch Optimierung Jahr die Kiel Sie kriegen automatisch bei diesen Ansätzen sieht auf der einen Seite die Information alles klappt mit das gerade nicht aber sie kann automatisch auch die optimale Anzahl dabei mit raus nämlich da wo sie möglichst weit gekommen sind so hier und dazu dash ist nochmal formalisiert was das heißt also wenn wir Lösbarkeit Problem haben n Damen zu platzieren heißt es wir haben ja auf jeder mehr auf jeder Spalte in jeder Spalte dann eine Dame sie müssen wir es genau eine Dame in jeder Spalte wenn der eine zulässige Lösung haben das heißt also wir können für jede Spalte sagen in welcher Zeile er von II für Spalte die können wir sagen in welcher Zeile als will als als Lösungs Ergebnis in welcher Zeile diese Dame in in dieser Spalte die in dieser Spalte ist dann zu platzieren ist und die zulässigen Lösungen also dadurch dass wir eine Variable für jede Spalte haben wo die Dame hat in dieser Spalte steht habe keine Bedingungen mehr innerhalb einer Spalte ja das haben wir von vorne rein dadurch ausgeschlossen dass wir für jede für jede Spalte sowieso nur genau 1 1 1 2 dort einen einfällt also also allein durch die Formulierung der Problemstellung haben wir von vorne herein ausgeschlossen dass 2 Damen in derselben Spalte sind wir müssen ausschließen das sie in derselben Zeile sind 2 Damen dass es hier und das hier das wollen wir hier nicht durchgehen das können Sie sich wenn Sie es nicht sofort sehen kann sich das mal selber überlegen dass diese Bedingungen Kieler Betrag von ihnen ist wird der Betrag von den beiden erwerben und der Betroffenen beim er werden das ist genau die verschiedenen Felder abdeckt wie 2 Damen diagonal zueinander stehen könnten so so so und so also 4 Fälle gibt es und Sie sehen es sind auch 4 Fällen möglich jeder Betrag steht ja ein positiven oder negativen Wert 2 Beträge sind für Fälle sowohl das einfachste Beck Trekking der gehen wir mal hin um das gleich zu sehen was damit gemeint ist mehr als was auf diesem Bild zu sehen steht jetzt hier auch nicht unbedingt drinnen sie von einem mit mehreren Schachbrett und Fairness verschiedene Strategien an wie Sie wie Sie diese Dame platzieren und eine wichtige Beobachtung 4 die nicht in die in dem Bild implizit drinsteckt oder auch nicht also die ich in Wasser drin sehe ist bedenken Sie immer dass sie Symmetrien ausnutzen können ja sie könnten natürlich ich hier von dem leeren Schachbrett als Wurzel Knoten verschiedene Knoten haben verschiedene Nachfolger die eine Platte die 1. Dame links oben 2. Platz die er zwar an andere Knoten er einen anderen Knoten platzte die 1. Dame rechts oben rechts unten links unten macht natürlich überhaupt keinen Sinn es völlig symmetrisch zueinander ja wenn es reicht eine es reicht einen Nachfolger Knoten Wunderwuzzi zu haben wo die Dame in einer Ecke Platz die 1. Damen an Ecke platziert ist sie brauchen keine weiteren wurden so als nachfolgenden und die 1. Dame in eine in eine geplatzte das wir das völlig identisch ist wenn sich eine Lösung finden wenn Sachen im Anhang eine Lösung und genauso hier sie brauchen nur einen Nachfolger von der Wurzel wo die 1. Dame auf einem der Reinfelder platziert ist die nicht Ecke sind nicht und das reicht auch wieder Sie brauchen jetzt keine weitere und keine weiteren Nachfolger Knoten wo wo die 1. Dame hier irgendwer der Mitte platziert ist dort wozu wir können genauso gut sagen die in der zweiten Spalte ist die zweite und ich die 1. platzierte Thomas eine andere drinnen für den Fall dass die dass die Damen der zweiten Spalte hier oder hier platziert ist der kommt dann automatisch dann im Inland die von ihm dabei und wir nicht auf dieser 1. eben noch mit zu betrachten was ich jetzt gesagt habe ist in diesem Beispiel offensichtlich ist in anderen Kontexten auch also die Suche nach Symmetrien Doktorand hat bei mir mal ja vielleicht nicht die ganze Promotion aber die halbe Promotion damit verbracht sie mitreden zu entdecken in Problemstellungen also ich was sie so offensichtlich ist existiert auch in anderen Problemstellung den sie uns des geht es vollkommen wurscht welche Kommune 1. Knoten ist ja also Sie brauchen nicht der Fall zu betrachten dass dieser Knoten da der 1. bluten ist und dann noch zu sich derweil dass der 1. und so weiter ist und und ist auch wurscht ob die Tour suchen oder so umgeht solange die Kanten Gewichte mit bestand ein anderer Fall von Symmetrie sie kann sich den Besuchern deutlich reduzieren indem sie eben die Richtung vorgeben den 1. Minuten vorgehen und fertig noch ein offensichtliches Beispiel aber es gibt in Schweden weniger offensichtliche Beispiele so jetzt haben sie beispielsweise im linken Know-how Dateibaum haben Sie die Dame in in die Ecke platziert jetzt haben Sie verschiedene Möglichkeiten wo sie die 2. Damen platzieren können gleich daneben schlecht das steht hier ein rotes X Ende das ist wirklich enden Buchstabe X kein Kreuz diese Wirklichkeit bringt auch nicht viel es sofort auch ein rotes X N der diese Möglichkeit und diese Möglichkeit bleibt noch übrig und auf den gehen wir wieder weiter hier eine ist das hier ein Exil wächst das heißt nicht dass wir WDR diesen Baum so durchgehen weil Sie wissen ja auch diesen oder sie offensichtlich auch dieser Baum geht es massiv in die Breite das ist zunächst einmal ein abstrakter konzeptioneller Baum denn wir uns aus abstrakten konzeptionellen Grün erst mal ansehen um zu verstehen worum es überhaupt geht ich denke es Bildungsprinzip wird damit klar entweder stellen wir sofort fest es geht nicht weiter wir haben schon Widerspruch wenn wir die Dame dann platzieren ich noch weiter verfolgen ist bekomme Ähnlichkeit Zugang dazu dass in Lösung mehrmals hier schon ein Widerspruch gibt oder wir stellen fest hier wie zum Beispiel in diesem Knoten hier die da haben die bisher bis zu dieser Ebene platziert worden sind schlagen sich alle nicht gegenseitig also können wir hier weitergehen stellen aber dummerweise fest was immer wir dann jetzt weiter tun es funktioniert nicht und hier ganz rechts haben wir eine tatsächliche zulässige Lösung gefunden wie die der 4 Damen platziert werden können ohne sich zu schlagen so und was
passiert jetzt bäckt Link Beck gelegentlich im Prinzip ist der Krieg in tiefen Suche hier drauf auf diesen Baum ja zum Beispiel in dem der von links nach rechts durch gehen muss sich aber bietet sich an wir gehen runter und da bäume klappt nicht Bräune klappt nicht hier und da klappt nicht klappt nicht klappt nicht klappt nicht und so weiter und so fort immer weiter und so weiter so machen was natürlich nicht wir laufen natürlich nicht den ganzen Baum durch sondern was wir natürlich wir wollen so schnell wie möglich da hinkommen zu dieser L wussten zulässige Lösung gibt da wir nicht wissen wo das ist können nur versuchen das so ein bisschen zusteuern in die Richtung aber wir können wir uns natürlich nicht innerhalb der König von von nur sagen ja ich komme zum zulässigen Lösung wenn ich erst mal mit der Dame beginne die dorthin zu platzieren dann die dort zu platzieren dann die dorthin und wo war ich habe man solle sie Lösung so gezielt comma das natürlich nicht angehen ich wissen in jedem Schritt wo wir am besten weitergehen das heißt also wir werden nichts im Allgemeinen nicht zielstrebig diesen Weg finden als 1. sondern wir werden irgendwo anders landen und hoffentlich mit entsprechender Strategien dass wir versuchen möglichst immer möglichst immer eher in die Richtung zu zu Schauern und möglichst nicht in diese Richtung zu schauen wenn wir versuchen möglichst nahe daran zurück zu landen wie der Strategie aus sehen die die tatsächlich dafür Sorge dass wir tendenziell eher in so eine Richtung gehen ja wir könnten zum Beispiel durch zählen hier wie viel was machen wir uns alle 4 kaputt sein sollen und in auch nur eine die Anzahl passt nicht ist die Anzahl der Fälle die wir uns kaputtmachen es immer dieselbe nicht 1 3 3 3 was immer so spontan eingefallen ist als Möglichkeit funktioniert nicht die Anzahl der Felder das die wir uns kaputtmachen im 1. Schritt funktioniert das nicht im zweiten Schritt kann man kann man dann schon Anfang zu argumentieren wie viele Felder machen wir uns damit Geburt nicht oder das ist dann nämlich nicht mehr immer dieselbe Zahl wird also müssen irgendwelches Wissen einbringen was was uns diesen Richtung hier verlockender erscheinen ist als diese Richtung nach Möglichkeit das ist ein Thema das dann aber meinen Bereich überschreitet ich denke der Bereich von führen Kranz der viel mit Computerspielen auch macht da würde helfen kannst dann an dieser Stelle dann übernehmen mehr zu sagen haben zu der Frage wie man wie man jetzt das hinbekommt was wir Kriterien man berechnen sollte damit einen diese Richtung hier verlaufen erscheint als diese Richtung China so jetzt sind aber irgendwo gelandet hier geht nicht wenn man die kamen sind wir sehr eine Zwischenlösung gelandet bin habe ich haben das er bei Welt zu lösenden gelandet Wir sind aber irgendwo gelandet und jetzt gehen wir zurück so wenn wir an dieser Stelle zufällig gelandet sind hier ganz rechts unten und ein Schritt zurück gehen und weitergehen und das war gut Sonderrechte getroffen hingegen aber beispielsweise hier gelandet sind im 1. Schritt diese zulässige Lösung in diese also diesen dieses Ende von wir dieses platte getroffener muss immer weitergeht und wir machen jetzt diese Strategie okay geweint zurück gehen das nächste und machen es immer weiter dann sehen Sie schon das geht nicht das ist keine gute Idee so wir wir müssen dafür
sorgen das viel größere Sprünge zurück
machen finden und das können werden kann mir dadurch sorgen das ist die Idee auch von der nächsten Folie dass wir die Situation genau analysieren das eben nicht einfach nur den letzten Schritt rückgängig machen der letzte Schritt war wahrscheinlich gar nicht verantwortlich dafür dass wir jetzt hier in einer Falle eingelaufen sind wahrscheinlich ist was haben wir den Fehler haben wir offensichtlich schon vorher gemacht jetzt endlich wissen wir dich drauf sich dass der Fehler schon gemacht worden ist die 1. die 1. Dame hier zu platzieren wir sehen ja deutlich dass wir uns diesen Baum diesen Teil bei mir ansehen dass danach nicht mehr möglich ist okay diese Draufsicht wird Algorithmus sich haben und die auch nicht mehr wenn das Beispiel größer geworden ist aber der Versuch zu analysieren wo der Fehler viel früher passiert ist und dann so weit springen von da aus zu weiter zu weiterzugehen ist natürlich dann fiel er viel erfolgversprechender weil die Warschauer Obst
über die Wahrscheinlichkeit sehr viel größer ist dann irgendwo werde zu zu gehen wollen Teil Baum dann immer noch die zulässige Lösung ist im schlimmsten Fall hier oben Mensch wenn der Algorithmus tatsächlich erkennt dass das die schon der Fehler war so das ist der
1. Punkt die kommen nicht mehr weiter wir wir bleiben irgendwo in den unzulässigen Lösungen hängen weil wenn wir einen Schritt zurück gehen oder vielleicht sogar Meeresspiegel 1. zurück zurückgehen wie gehen zurück gehen dann haben wir vielleicht den die sind wir haben ja vielleicht immer noch durch das zurücknehmen von dem von den letzten Entscheidungen immer noch den nicht die wahre Ursache des Konfliktes wieder rückgängig gemacht sondern wir müssen größere Schritte zurückgehen um nach möglich diese war war Ursache zurück das das das Problem ist rückgängig zu machen und den Einrichtungen weiterzugeben auch Redundanz wenn sich das mal
anschauen in verschiedenen unteren Stufen passiert immer wieder dass er über die Situation sind nicht so weit unter voneinander wir versuchen immer wieder dann nochmal jetzt hier sehr ähnliche Probleme zu lösen auch das kostet natürlich
unmöglich Laufzeit das wollen wir und ich haben mehr also die Idee ist hier bei dieser zweiten ist ein Spiel comma bei Methoden die Beck'sche oder Beck markigen oder Traktor genannt werden dass wir uns solche
lokalen Konstellationen wo schiefgegangen ist hier merken und immer wenn es dort nur so aussieht als ob wir dann demnächst wieder in diese lokale Consolation reinlaufen gleich von vorn herein mutig beherzt und wieder zurück gehen wir können hier wir haben das ist eine heuristisches Verfahren wir können wir werden nicht den ganzen Baum durchsuchen und mit Sicherheit eine zulässige Lösung zu finden also können wir auch beherzt Fehler machen in der Hoffnung dass dieses beherzte diese der sie der zur Risiko Fehler zu machen uns zu bessere Lösung führt sie ändern sich bei Sachen die bis wird in den haben sicher sehr gemacht mit einer gewissen Wahrscheinlichkeit machen wir etwas was mein Fehler ist nämlich akzeptieren eine schlechtere Lösung in der Hoffnung dass uns das zu wesentlich besseren Lösung führt und die Sorgen es der Praxis durchaus auch in vielen Situationen berechtigt so der dritte
Schritt den den dritten period in den und setze genau betrachten bei der auch die die die die 1. beiden Punkte sind sehr Problem spezifisch ja man könnte schon die ganze Vorlesung denn ich darum weiterzuführen wie man beim N Darmproblemen diese 1. beiden Spiegelstriche realisieren kann der dritte dash S allgemeiner und ist auch vielleicht mit der wichtigste deshalb werden wir uns dem hier etwas näher auf den nächsten Folien widmen so als ich mir
diese Folie der Vorbereitung an geschaut habe wo da bin ich mir nicht sicher also doch wieder ich dachte zuerst dass die dass diese Zahlen hier falsch sind aber das stimmt nicht die Zahlen ich glaube ich habe mich verguckt die Zahlen sind schon richtig also hier hier steht eine rote 1 drin weil die Dame in der Spalte 1 dieses Feld überdeckt hier stehen eine rote dran eine rote 4 drin weil sowohl die Dame in der Spalte 3 er hier unten dieses Feld diagonal überdeckt als auch die in der Spalte 4 horizontal überdeckt und so weiter also hier haben wir die verschiedenen Konflikte in diesem Feld trennen und stellen fest das wir hier dass wir hier in der Spalte 6 nicht mehr weiterkommen so einfach Respekt richtig ein Schritt zurück würde bedeuten dass wir die Entscheidungen Spalte 5 zurücknehmen dass wir versuchen die Dame anders zu setzen das heißt im Baum würden wir aus einer
dieser eine als einem dieser Konfliktfälle rausgehen und in der benachbarten Geschwisterteil Baum rüber
gehen diese Dame hat anders so platzieren aber das bringt uns gar nichts weil egal egal wo wir diese Dame platzieren Sie sehen dass in diesen roten Zahlen über Alter wo die 5 steht steht auch noch eine andere Zahl dabei das heißt also die 5 hier zu verschieben bringt uns gar nichts ist ist hielt andere Dame es ist es andere fällt in der Spalte 5 1 Spalte 6 immer noch überdeckt durch eine der Damen 1 bis 4 so deckt Yanping heißt dass wir versuchen tatsächlich er den Konflikt aufzulösen die wahre Ursache zu weit und zu gehen dass die wahre Ursache aufgelöst ist und das was hier wirklich den Ärger macht es nicht die Dame 5 sondern die Dame 4 das heißt wir würden zurück auf Ebene 4 gehen diese Dame anders platzieren versuchen da eine andere Lösung zu finden und dann wieder vorwärtsgehen allgemein gesprochen das ist der letzte dash auf dieser Folie wir gehen so weit zurück wie es unbedingt sein muss um einen Schritt voran zu kommen um die 6 jetzt auch noch zu viel erfüllen und nicht nur die 5 so das war jetzt ein Beispiel für Fürbeck Jianping Beck Jackie Gutenberg Martin haben wir jetzt hier auf den vorher nicht wenn wir jene von ich werde dies es goutieren wie gebe ich angeblich habe wir gekonnt und wir uns vor allem auf diesen dritten sehr allgemein dash also sehr allgemein anwendbar period Konsistenz Techniken das hängt ganz einfach an und wird beliebig kompliziert aber wir stoppen es rechts der die Betrachtung rechtzeitig bevor es beliebig kompliziert wird können sollen so hier steht das Wetter das tat was er nicht sagen das ist natürlich ein bisschen übertrieben dass hier ein Beispiel zu nennen ist natürlich schon ein Beispiel aber es ist nicht das was man normalerweise unter einem konkreten Beispiel will verstehen Sie haben immer noch eine abstrakte variable aber mit Werten und mit einem bestimmten Bereich und eine abstrakte variabel B mit dem bestimmten Wertebereich ich kann mich erinnern ich habe meinen Vortrag von einem Mathematiker gehört es meine ganze Menge Theorie entwickelt hat und dann gesagt hat so jetzt komme zu einem anschaulichen Beispiel betrachten Sie denn er hoch 7 danke okay also offensichtlich hatte er da einen höherdimensionalen ist der Anschauung im Kopf anschauen die Möglichkeit im Kopf als ich also kein Scherz es war wirklich so und er war ich glaube er zornig als Scherz gemeint so so wir haben dessen einfacher Fall wir haben 2 Variablen mit Wertebereich mit Definitionsbereich ja mit Domänen ich bin mir nicht sicher ob es ob das analoge er zum zum Wertebereich oder analog zum Definitionsbereich zu diesen bei welchen dieser beiden Begriffe der Mathematik das also welche von Domänen da das ist die einzige Bedingung muss kleiner Bier sein und dann sehen wir schauen für ne ganze Menge von war ja von Werten in ganz konkret für die Werte 5 6 und 7 für die annehmen kann gibt es gar keinen Wert im Wertebereich in Domäne von B so dass diese billige Art kleiner B erfüllt ist das heißt wir können die Domäne von von vornerein reduzieren auf 3 und 4 und aus selben Grund in der von B 5 oder 1 reduzieren auf 4 und 5 das sieht jetzt gekünstelt aus dass das natürlich ist es künstlich so gebastelt das das gerade so eine schöne Reduktion gibt aber erinnern Sie sich an an dieses dramatische Beispiel mit der Reduktion von mit der mit den Service Station für die Bahn ja was was steckt eigentlich dahinter das habe ich damals vielleicht nicht so thematisiert wie hätte tun können das will ich jetzt aber noch mal die man Sie sehen was dahinter steckt ist wenn Sie ein Problem eine Instanz gegeben haben aus der Praxis so riesengroß dass sie eine schlägt egal was es ist egal so diese Servicestation Geschichte ist oder irgendwas anderes B oder sonst was dann steckt typischerweise unglaublich viel Redundanz drin da ist unglaublich viel unwichtiges Zeugs dran was das was über sie nur was sie nur noch und unnötig Rechenzeit kostet wenn sie beispielsweise die Optimierungsproblem oder der gleichen Systeme wenn Sie so was typischerweise aus der Praxis kriegen also je nach Anwendungsgebiet dann dann können Sie damit rechnen dass der dieser Matrix viel viel kleiner ist als ist sein die Spalten zwar in vielen Anwendungen ist das so ja das heißt dass ein schönes Beispiel dafür dass sie unendlich viele Daten mit sich rumschleppen die keine Zusatzinformationen gehalten die die nicht weil er die sie letztendlich nicht nicht betrachten müssen Sie müssen es nur rauskriegen sie müssen nur diese Matrix dann kondensieren zu einer Matrix die vollen 1 hat also in sehr machen wie vorher entsprechend geringer Zeilen Spalten Star oder zumindest eines von beiden und genau so müssen Sie das hier sehen ja diese Technik solche Techniken haben vor allem ihren Wert und ihre gewaltige Power dann wenn wir diese typische Situation haben das unendlich viel Datenmüll aber aber nicht so recht also sie kann nicht einfach sagen also diese da diese Spalten der Matrix ist Müll die schmeiß ich raus das zu einfach geht sogar teilweise einfach weil sie teilweisen Anwendung sogar die Situation drin haben dass sie 0 Spalten haben oder so die Gesamtlösung wurde rausschmeißen aber so einfach wird ihm das natürlich meistens nicht gemacht sie müssen sie müssen die irgendwie irgendwie rauskriegen und solche einfachen Techniken ähnlich wie wie die einfachen sehr sehr einfachen durch in der Sonne statt und solch einfachen Teilchen die helfen Ihnen häufig dramatisch das Ganze so reduzieren und da haben sie dann ihren großen wert und weil das so häufig ist haben sie hat einen sehr großen praktischen wird so okay wieder zurück zu den kleinen Details nachdem jetzt wieder eine große Rede gehalten wurde konkurrierten kleine das zurück haben zum Beispiel die Situation dass einem der 4 1 und den wird 4 annimmt ist damit noch nicht ausgeschlossen durch diese Reduktion der beiden Domänen denn die Bedingung auch kleiner B ist natürlich von 4 und 4 a gleich 4 und billig ich auf so aber für jede Bewegung von egal ob sie aber gleich 3 oder wir werden wissen Sie sie finden eine zu es zulässt entsprechen Belegung Balbi die diese bedingt erfüllt das ist natürlich in der Praxis in der in der Realität sie nehmen sich die eine wegen her das ist nur eine von Millionen oder von Tausenden von Bedingung die sie bis sie konzentrieren sich in dem Moment auf diese Bedingungen reduzieren damit die Domäne und den weiter sich wie wir das bei dem Service Station gemacht habe mit der Bahn sie konzentrieren sich auf einem das sie sich meist ein Zug aus und dann geht's weiter sich meist eine Mahnung brausende weiter und so fort so das für dich gern vielleicht nochmal ganz kurz überspringen und später nochmal drauf
gekommen Nord Konsistenz sie essen hochtrabendes Wort für ne Kleinigkeit wenn ich das mal so sagen darf ich hoffe dass ich damit niemand der sich mit dieser Thematik beschäftigt auf die Füße trete wer einfachstes Beispiel ist sie haben der Domäne die Domäne einer Variablen x ist gleich 1 bis irgendein Ende ist egal was auch immer am konkreten wert 1 bis 1000 und sie haben die Bedingung 2 x kleiner gleich 10 so dass ein bisschen komplizierter sein als nur externe gleich 5 aber es ist natürlich Jacke wie Hose das heißt also diese Bedingung ist nur erfüllt und das ist Not consistency werden wenn X aus was ist das dann 1 bis 5 ist an einer werde können Sie vergessen von vorne rein in dort kommt es hinaus consistency bedeutet sie haben eine und deren Bedingungen belegen in der nur eine einzige variabel vorkommt dem sprechen ab consistency bedeutet
2 Variablen jetzt komme ich zurück zu der
fröhlichen übersprungen habe und dass wir dann auch unsere letzte für heute sein wenn Sie für jeden Sieg sie stellen sich einfach mal für jede Variable einen Knoten vor in einem zusätzlichen konzeptionellen des Grafen denn sie sind mehr werde und Kopf haben den wir nicht implementieren und auf dem Kanal goldene laufen lassen so war sie gerne sehr von mir so Nord consistency dessen Bedingungen auf einzelnen Knoten aber Konsistenz sie das Bedingungen auf Paaren von Knoten die sie dann sagen durch bekannte darstellen können ja jede Bedingung die genau 2 variabel enthält sowas wie zum Beispiel wir doch mal so was hier aus dem ganz anderen Kontext wie sehr man sich an diese Gleichung was man im Kontext seit dem diese Gleichung was bitte das die Chrysler schon die die die beschreibt die Menge aller Punkte auf dem Rand eines Kreises im er mit 3 dass er um den Ursprung so und das ist eine binäre will Bedingungen so dass eine konstante er es gegeben und das in 2 Variablen Wärter das würde dann also eine Kante darstellen ist kann man das weiterspinnen ist es bisschen schwieriger zu zeichnen dass Sie diese 3 Knoten in einer Bedingung drin haben ja wir können also die Kreis Gleichung zur Kind Google Gleichung im er auch 3 erweitern um um ein Beispiel dafür zu haben oft Zeichen man das dann so komisch mit solchen komischen weiß nicht wie man diese Gebilde nennen würde also verstehen was ich meine hier gesagt wir sollen so 3 näherungsweise Kreisbögen sein oder was was immer man einnimmt wird mit der Zeichnung schon bisschen schwieriger eine andere Möglichkeit der Visualisierung wäre die auch nicht gerade übersichtlich aber immerhin es ist es ist nun mal Komplex Information die man da darstellen würde haben dass Sie hier die Variablen setzen so und dann und dass sie hier die Bedingungen setzen so und war und dass eine Kante besagt dass diese war ja wenn diese Bedingung vorkommen dass sie war kommen das ist das zum Beispiel eine binäre Variable und das wäre dann eine Ternera variabel mit 3 Variablen drin Erzählungen eine binäre Bedingung eine Eltern ihre Bedingungen und so weiter das ist einfach ein sprachlicher Rahmen der diese Nauth Konsistenz
Sie diese Konsistenz sie Welt dem
gesprochen haben und jede höhere Art von von Bedingungen einfach in einen gemeinsamen zusammen haben hinein passt so dass man also von diesem ganzen verschiedenen Dingen in Uniform Malweise reden kann so damit sind wir für heute am Ende unserer Zeit Ich möchte mich bedanken und wir sehen uns jetzt erst einmal eine ganze Weile nicht mehr ich habe letztens erst zu ist gar nicht klar gemacht dass wir das das DKB 2 in 2013 ja auch vorlesungsfreie ist also wenn ich nicht Student auf hingewiesen hätte dann wäre ich in K 2 am Dienstag und am Mittwoch in meiner ersten Vorlesungen gestolpert und hätte mich da wahrscheinlich gewundert okay
gut in diesem Sinne ich wünsche Ihnen eine schöne Auszeit für diese Zeit ich weiß nicht ob es eine Auszeit vom Studium für sie ist aber sie werden sicherlich ein bisschen wenigstens Auszeit finden wenigstens am 24. ab 18 Uhr und Abend am einunddreißigsten ab 23 Uhr werden Sie sicherlich Auszeit Auszeit ach so ja richtig sie erinnern sich am 21. sollten Sie etwas vorsichtig sein wenn sie auf die Straße treten die Wettervorhersage für den 21. ist schon mal ist schon mal ein schlechtes Omen habe ich jetzt Meteoriten das ist aber keine der Wettervorhersage oder gut also dann wünsche ich Ihnen eine schöne Auszeit oder was auch immer sie nicht in dieser Zeit machen
Loading...
Feedback
hidden