AV-Portal 3.23.3 (4dfb8a34932102951b25870966c61d06d6b97156)

Introduction - Generel Discussion of Algorithmic Problems

Video in TIB AV-Portal: Introduction - Generel Discussion of Algorithmic Problems

Formal Metadata

Title
Introduction - Generel Discussion of Algorithmic Problems
Title of Series
Part Number
1
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...
Sheaf (mathematics) Area Vacuum
Group action Recursive set Real number Direction (geometry) Maxima and minima Lösung <Mathematik> Student's t-test Zielfunktion Focus (optics) Number Length of stay Strategy game Zusammenhang <Mathematik> Natural number Estimation Airfoil Randbedingung <Mathematik> Decision theory Optimization problem Feasibility study Set (mathematics) Enumerated type Zielfunktion Object (grammar) Mathematical optimization
Kante Cue sports Greatest element Bindung <Stochastik> Graph (mathematics) Direction (geometry) Maxima and minima Lösung <Mathematik> Matching (graph theory) Zielfunktion Subset Physical quantity Plane (geometry) Solution set Graph (mathematics) Randbedingung <Mathematik> Maximum (disambiguation) Optimization problem Feasibility study Set (mathematics) Incidence algebra Zielfunktion Function (mathematics) Optimum Mathematical optimization Directed graph
Kante Point (geometry) Boolean algebra Constraint (mathematics) Nummerierung Ende <Graphentheorie> Price index Lösung <Mathematik> Matching (graph theory) Function (mathematics) Infinity Subset Number Mathematics Matrix (mathematics) Plane (geometry) Vector graphics Summation Constraint (mathematics) Slide rule Euclidean vector Element (mathematics) Coordinate system Feasibility study Set (mathematics) Incidence algebra Predicate (grammar) Matrix (mathematics) Element (mathematics) Connected space Subset Volumetric flow rate Index Function (mathematics) Travelling salesman problem Quadratic equation Ecke Set theory Object (grammar) Power set Linie Matrix (mathematics)
Kante Constraint (mathematics) Model theory Maxima and minima Lösung <Mathematik> Subset Sign (mathematics) Mathematics Matrix (mathematics) Plane (geometry) Partition of a set Vertex (graph theory) Summation Constraint (mathematics) Slide rule Euclidean vector Death by burning Moment (mathematics) Set (mathematics) Term (mathematics) Strecke Inversion (music) Travelling salesman problem Quadratic equation Linie Matrix (mathematics)
Kante Computer programming Constraint (mathematics) Model theory Maxima and minima Feasibility study Calculus Lösung <Mathematik> Term (mathematics) Continuous function Existence Approximation Zielfunktion Heuristic Optimum Vertex (graph theory) Normal (geometry) Mathematical optimization Scale (map) Identical particles
Point (geometry) Position Plane (geometry) Physicist Sheaf (mathematics) Universe (mathematics) Theory Complete metric space Set (mathematics) Infinity Quantum computer
Addition Model theory Complete metric space Approximation Equivalence relation Mathematical model Variable (mathematics) Mathematics Per mil Graph (mathematics) Adjacency matrix Vertex (graph theory) Pairwise comparison Elementary arithmetic Multiplication Beat (acoustics) Operations research Observational study Laufzeit Binary file Complete metric space Fraction (mathematics) Number theory Optimum Heuristic Integer Scale (map) Factorization Group representation
Kante Stress (mechanics) Neighbourhood (graph theory) Clique problem State of matter Graph (mathematics) Covering space Lösung <Mathematik> Dreiecksungleichung Variable (mathematics) Mathematics Plane (geometry) Field extension Strategy game Solution set Network topology Vertex (graph theory) Validity (statistics) Arc (geometry) Hamiltonian (quantum mechanics) Polynomial Constraint (mathematics) Decision theory Complementarity Neighbourhood (graph theory) Element (mathematics) Well-formed formula Function (mathematics) Travelling salesman problem Sheaf (mathematics) Theorem Social class Set theory Iteration Integer Mathematical optimization Euklidischer Raum
Point (geometry) Kante Stress (mechanics) Neighbourhood (graph theory) Graph (mathematics) Real number Maxima and minima Lösung <Mathematik> Zielfunktion Function (mathematics) Infinity Approximation Abstrakter Raum Subset Physical quantity Mathematics Plane (geometry) Solution set Iteration Graph (mathematics) Energy level Modulform Spacetime Vertex (graph theory) Length Local ring Arc (geometry) Social class Rule of inference Slide rule Point (geometry) Feasibility study Set (mathematics) Term (mathematics) Existence Solution set Symmetric matrix Function (mathematics) Travelling salesman problem Relation <Mathematik> Optimum Power set Mathematical optimization Euklidischer Raum Combinatorics
Kante Neighbourhood (graph theory) Greatest element Konvexe Funktion Maximum (disambiguation) Konstruktion <Mathematik> Maxima and minima Feasibility study Lösung <Mathematik> Maxima and minima Zielfunktion Set (mathematics) Grand Unified Theory Iteration Travelling salesman problem Relation <Mathematik> Optimum Local ring Arc (geometry) Euklidischer Raum Local ring Chain rule
Neighbourhood (graph theory) Zahl Maxima and minima Feasibility study Lösung <Mathematik> Connected space Force CW-Komplex Solution set Iteration Zusammenhang <Mathematik> Optimum Iteration Social class
Maxima and minima Feasibility study Hill differential equation Term (mathematics) Local ring Smith chart
Fluid Maxima and minima Local ring
so genau sind die Änderungen der immer so sein dass er verlängert werden an der TU Darmstadt gut noch Kontrolle dass es
nicht auf mute gestaltet so ist nicht auf mit geschaltet hatte zwar soll ich hoffe das funktioniert weiterhin alles sieht
so weit gut und mehr so gut
hallo allerseits ich möcht Sie zur zweiten Vorlesung begrüßen ich hatte setzt man gekündigt ich will versuchen das das ganz aufgenommen wird also was auf genau kommt wieder aufgenommen wird ist wenn alles funktioniert hat das Kamerabild und der Bildschirm und mein Ton deshalb wundern Sie sich nicht dass ich mehr Zeit auf war war aber sie war nicht über die Lautsprecher das geht hier in den Empfänger nicht in nicht in dieser Technik und was ich noch brauche ist dann jemanden der mir zeigt wie man aus diesem Fantasie oben Datenformat dann habe ich dieses Video macht aber ich denke das sollte das geringste Problem sein gut wir hatten beim letzten Mal einerseits die wesentlich satorischen Punkte besprochen andererseits aber auch wir sind ja schon bisschen eingestiegen in das Thema gibt es von ihrer Seite aus heute nochmal organisatorische Punkte zu besprechen wir haben sie alle den Forumsbeitrag von mir gelesen wenn ich dann schauen Sie bitte da rein bei Gelegenheit ist nicht eilig aber schon sehr sinnvoll also es gibt ein Forum und wie bei jeder Veranstaltung hier durch die Fachschaft organisiert und da habe ich eigentlich nur reingeschrieben dass sie mit den nicht algorithmischen Anteilen der Programmieraufgabe eigentlich schon beginnen können dass dass es gar keinen Grund gibt der warten bis die Algorithmen da sind so ich mache einen kleinen Sprung ich werde gerade hier am Anfang keine einige kleinere Abschnitte überspringen wenn die Zeit reicht werd' ich wieder zurückkehren dazu später aber die Wahrscheinlichkeit ist nicht groß dass die Zeit reichen wird das sind Abschnitte die 1. nicht so wichtig dafür 2. aber besonders schwierig zu verstehen sind das heißt also ich denke wir sind uns einig dass das keine schlechte Idee ist diese Punkte zu über springen ich will direkt einsteigen jetzt in das Thema allgemein das zum algorithmischen Problemstellungen das hat mir beim letzten Mal noch nicht angesprochen nicht so weit immer noch nicht gekommen nicht mehr gut was haben Sie
für algorithmische Problemstellung Entscheidungsprobleme festzustellen dass im Graben festzustellen ob es eine Lösung gibt oder nicht er ist meistens natürlich nicht so besonders prickelnd zu wissen das ist eine Lösung gibt ja stellen sich eines der Probleme vor die wir beim letzten Mal behandelt haben beispielsweise das Problem hier für für eine Universität ein Stundenplan für alle soll Belegung zu erstellen wenn der Algorithmus in sagt ja Rohrer es gibt eine Lösung schön aber sie möchten sie natürlich gern in der Hand haben zuweilen reicht ein Entscheidungsproblem zuweilen reicht Ja oder Nein zu wissen zum Beispiel eben bei Entscheidungsfragen ja soll ich soll ich die und die Finanz- Investition tätigen ja oder nein da reicht das natürlich ein nicht mehr als Entscheidung er kann man auch nicht erwarten Konstruktionsproblem ist das typische er das auch das diebische was sie in der GD 2 meistens kennen gelernt haben den sie an einsortiert Problem dabei die Aufgabe eine sortierter Reihenfolge der Eingabe Sequences zu konstruieren oder denken Sie an wenn Sie das innige die 2 dringen Mertsching also das was sie kennen Suchfunktion in einer Datei worden einer Datei zu finden aber die ist die Aufgabe alle vorkommen der dieses Suchwortes in der Datei zu konstruieren eine Liste aller Positionen wo dieses Suchwort in der Datei vorkommen zu konstruieren und so weiter wieder W nicht weniger wichtig ist seltener richtig essen Aufzählung Problem nämlich alle Lösungen zu einer Problemstellung zu geben und das ist meistens reicht das einer wenn man eine Lösung hat da wo man nicht alle zu haben da ist aber durchaus in manchen Kontexten sehr sinnvoll zum Beispiel denken Sie an an Ziele Probleme wer mit mehreren Ziel Kriterien denken Sie beispielsweise aus unserer Praxis unserer Arbeitsgruppe Fahrplanauskunft bei der Deutschen Bahn da haben Sie 3 Ziele Kriterien die Fahrzeit also wie schnell sie von von A nach B kommen der Fahrpreis natürlich und die Bequemlichkeit ausgedrückt Anzahl und Verweildauer bei den umstiegen vielleicht der Bequemlichkeit die voll besetzte Regionalbahn ist nicht so bequem wie der dünn besetzte ICE oder so etwas der mindestens 3 Kriterien haben Sie und natürlich weiß der Fahrkartenautomat nicht was was der Kunde für ein ziel Profil hat ob wie wichtig ihm Fahrzeug wie wichtig ihm Fahrpreis und wie wichtig ihnen die Bequemlichkeit ist ja da gibt es so sie können sich so verschieden Countrywide vorstellen der Geschäftsmann die Geschäftsfrau da ist Zeit Geld also vor allem wichtig möglichst schnell der arme Student die arme Studenten das Geld alles als an was nicht so wichtig okay Zeit ist auch wichtig auf Studien haben heutzutage keine Zeit mehr im zu meiner Zeit oder die alte Dame mit den 2 schweren Koffer für die natürlich Bequemlichkeit das Wichtigste ist möglichst wenig Umstieg er und den Umstieg getan möglichst irgendwie bequem ja dementsprechend Krieg der Fahrkartenautomat nicht eine Lösung sondern eine ganze Innovationen von vorn jeweils nach verschiedenen Profilen halbwegs optimalen Lösungen das hat also Innovations- Probleme mehr als eine Lösung sie es durch aus hin und wieder eine eine sinnvolle Zielsetzung ist es aber wenn man nicht weiß was dann der Endkunde wirklich wäre wenn man so dass man Ihnen Alternativen Optionen anbieten aus und das womit wie wir uns hier vor allem beschäftigen werden sind optimal Währungsprobleme so heißt auch die Lehrveranstaltung ja wir haben nicht nur einfach eine eine Probe in die einen wir wohl nicht einfach nur eine Lösung finden eine zulässige Lösung gibt sondern wir wollen eine Lösung finden die nach irgendeinem Kriterien optimal ist denken Sie an das Bein an das Navi beispielsweise typischerweise ist dass die Zeit fast optimiert wird sie wollen einen Weg von A nach B finden im Straßenverkehr der die Zeit optimierte minimale Zeit nach den nach den geschätzten Zeiten für die einzelnen Streckenabschnitte die Navi gespeichert sind drin also da extra Vista da extra Problem beispielsweise wäre ein Optimierungsproblem so hier noch einmal wie ich eben auch gesagt hatte Entscheidungsprobleme sind manchmal wichtig Aufstellungsprobleme manchmal möchte man mehr als eine Lösung haben aber meistens wir eine Lösung haben oder eine optimale oder wenig oft genug davon reden wir hier in diesem Semester oft genug wird man nicht die optimale Lösung gaben im Gegensatz beispielsweise zum kürzesten Weg wo sie in fast linear Zeit mittags das Algorithmus ein optimale Lösung bekommen wir reden über Probleme wo sie nicht immer die optimale Lösung in endlich in vernünftiger Zeit bekommen können oder es nicht erwarten können dass sie die bekommen da also wenn wir von Optimierungsproblem reden meinen wir unter Umständen reicht uns auch eine halbwegs optimale Lösung ein Grund warum er alle Entscheidungsprobleme nicht so wichtig sind ist dass sie typischerweise ja tatsächlich auch eine Lösung die für ein Jahr in wenn Sie das das Beispiel von eben hatten und soll ich die und die Finanzanlage solch Akt in Aktien investieren oder nicht dann wird der Algorithmus ich formuliere es mal um festzustellen ob es sinnvoll ist in Aktien zu investieren oder nicht wird er versuchen eine Aktion Strategie zu entwickeln und zu entscheiden eine möglichst gute Aktienstrategie sogar um zu entscheiden ob sich das lohnt oder nicht und denke dann keiner der alte doch noch weiter tun und diese Aktion Strategien auch sagen dieser Zusammenhang hier ist trivial aber manchmal durchaus von Bedeutung Konstruktionsproblem dass Sie irgendeine Lösung haben wollen können Sie natürlich immer trivialer als Optimierungsproblem Ansehen in den sie jede Einzellösungen denselben Kriterien sollten im Ziel eben Objekte ab mit der ich beim letzten Mal schon ziel der Ziele Funktionswert Zielsetzung und dann ist es ein Optimierungsproblem wo halt alle Lösungen gleichen optimalen wert haben das ist deshalb unter Umständen sinnvoll weil sie können sich nur die Jungs Algorithmus vernehmen und die dann auf Konstruktionsproblem an werden wenn sie schon schönen alten Algorithmus haben Unterschiede implementiert ist schön Jude ist und sie wollen gar nicht jetzt ob die mehr sondern sie wollen irgendeine Lösung herausbekommen na ja dann dann stecken Sie Ihre Problemstellung da trotzdem rein und geben jeder einzelne möglichen Lösung denn sie Funktionswert 1 so wir betrachten also Optimierungsprobleme so heißt auch der scheinen und das ist auch der Grund warum die Führung der Veranstaltung so heißt es ist nicht Algorithmen Algol allgemein sondern und nicht Probleme allgemein sondern Optimierungsalgorithmen Optimierungsprobleme weil sich alles darauf reduziert
ist so wir müssen uns sprachliche Wissen verständigen werden immer wieder nach demselben Schema über Probleme reden erst einmal ist entscheidend wichtig dann kämpfe ich in jenem Sommersemester bei den Studierenden algorithmischen Modellierung die genau zu unterscheiden zwischen was ist das Problem und was ist die Lösung das würde mit begegnet mir auch immer wieder auch wenn ich mit Leuten aus der Wirtschaft oder Industrie zusammenarbeite dass man wenn man versucht das Problem zu beschreiben schon in Gedanken irgendeine algorithmische Vorgehensweise hat und sich von von dieser Vorgehensweise die man über Mittag Auffahrt schon beeinflussen lässt wie man das Problem beschreibt das ist natürlich problematisch weil man damit praktisch befreiend ist schon wenn man wenn man über die Essen über die Problemstellung spricht sich sich praktisch selber bei den also welche Möglichkeiten einschränkt so und was woraus besteht ein Optimierungsproblem aus der Menge der zulässigen Eingaben denken Sie an das Problem hier eine Universität die die Hörsäle der Veranstaltung in der Seele und und den Zeit Slots zu parken dann ist jeder zulässige Input eben gegeben durch eine Menge von Hörsäle mit ihren Ausstattungsmerkmalen 2 Sitze vielleicht noch technische Ausstattung dann ist natürlich gegeben die Menge der Lehrveranstaltungen mit den Anforderung des Dozenten jeweils was die technische Ausstattung ist und mit der Schätzung wie viele Sitzplätze gebraucht werden und natürlich die Zeit Slots an der TU-Darmstadt der besonders interessant gestaltet sind die sind ist das wären die zulässigen in Porz jeder jeder in wie jeder der sich jedes dritte aus 3 Mengen soll in Hörsälen solchen Lehrveranstaltungen und solchen Zeit Satz wäre ein zulässiger in vielleicht eigentlich ist es noch ein bisschen komplizierter man müsste noch ein bisschen mehr in als in Butter zu leben müsste zum Beispiel Informationen dazu nehmen dass die dass die Hörsäle Verzicht verteilen auf 2 2 Zweig der Campus für einmal statt einmalig diese und dass man nicht in in 5 Minuten vom einen zum anderen kommt so dass es da wieder Einschränkung gibt und so weiter so der fiese Beaud trotz Krise bitte sollte noch dazusagen allgemein wie Sibylle heißt im Englischen wirklich durchführbar hat sich da etabliert im Bereich Algorithmik das als zulässig zu übersetzen die zuletzt in Inputs also das was der Algorithmus verarbeiten solle was womit alles fertig werden soll die zulässige Output das was Algorithmus liefern soll was essen wir immer wieder bei diesem Universitäts- Planungsproblemen was wäre ein zulässiger Output für einen gegebenen Input also vielleicht noch ein Wort dazu wenigstens ist eine das Halle hat verschiedene Bedeutung im Englischen heißt unter anderem auch das selbe wie Input im Bereich Algorithmik manchmal werden auch im deutschen dann von Instanz was wir einen zulässige Outputs das hat also Sieger Output wäre für jeden einzelnen der falsche oder genauso Finanzen Termin einer Lehrveranstaltung die 1 beispielsweise hat 2 Termine wieder einen Termin eine Zuweisung welche Raum welcher Zeit laut welche wöchentliche Zeit dort das muss das ganze fiese bitte dass das ganze durchführbar zulässig ist muss es die entsprechenden Rahmenbedingungen einhalten es muss natürlich einhalten dass keine 2 Lehrveranstaltung am selben zwar zum selben Zeit im selben Haushalt eingeplant sind selbstverständlich ist muss einplanen dass die Dozenten und auch die Studierenden wäre natürlich schön wenn es die wenn das so wäre wenn das eingeplant wäre das die Chance haben von einem soll zum anderen zu kommen ohne in eine Vorlesung frühzeitig raus zu gehen oder anderen zu spät zu kommen und so weiter Objekte ist das ist da auch in diesem Beispiel durch aus einer Frage was wäre die Zielsetzung das diskutieren wenn algorithmischen Modellierung durch ummodellieren das dann auch der Zielsetzung könnte beispielsweise sein Dozenten können angeben welche Termine passen Ihnen gut welche Teile Termine es okay welche Termine passen nicht so gut und welche Termine gehen gar nicht und nach diesen Presse diese Präferenzen summiert über alle Professoren über alle Dozenten hinweg zu optimieren das könnte ein Optimierungs- Ziel sein was man hier betrachtet das muss der Kunde und der Saft des aufwendiger miteinander aushandeln anderes Optimierungs- vielleicht über Studenten freundlicher könnte beispielsweise sein da und nach Möglichkeit der Stundenplan jedes Studierenden aber so geparkt ist dass auch die Leute die aus dem Odenwald oder außen aus dem Westerwohld oder so kommen und möglichst nicht jeden Tag einreisen wollen das auf die Rücksicht genommen wird und oder ähnliche Sachen also Sie sehen die Zielsetzung das es gerade wenn man mit mehr zu um wenn man wirklich über konkrete Problemstellung aus Industrie aus der Wirtschaft aus der Verwaltung redet es meistens nicht so problematisch zu spezifizieren was die Randbedingungen die unbedingt und einst Umständen einzuhalten sind aber es ist häufig durchaus eine Sache der Diskussion zu spezifizieren was eigentlich die Zielsetzung ist die man optimieren möchte so jetzt ein bisschen vom Maler aber wie viel eigentlich nur müssen wir dem malerischen Mutationen für das was wir eben auf der letzten Folie gesagt haben wir uns kalligrafisches I für alle potenziellen in die Menge aller potentiellen in werden von einer mathematischen Menge hier für jedes für jeden Input haben wir eine Menge von unzulässigen Lösung natürlich hat der eine Input an zulässige Lösungen als der andere Input und für diese und auf dieser Menge für eine gegen Instanz für indigene Input aber das hat es die Zielfunktion indiziert mit dem Import haben wir eine Funktion die die Menge der zulässigen Lösung abbildet in die reellen Zahlen die meisten sicherlich in nicht negativen realen Zahlen vielleicht sogar in die natürlichen Zahlen aber auf jeden Fall immer in die reellen Zahlen und wir haben Richtung immer wir wir wollen minimieren oder wie wollen maximieren entweder wollen wir Profite maximieren oder wir wollen Kosten minimieren das ist immer das oder oder müsse nicht Kosten im Sinne von Euro sein können auch unbequem in seine kalten sein die wir minimieren wollen und so weiter so was ist die
Aufgabe was die algorithmische Aufgabe das ist die Aufgabe die einen Algorithmus gestellt wird ein Algorithmus ist dieses Optimierungsproblem dass ich jetzt hier ganze generisch abstrakt spezifiziert habe wenn es da vielleicht diese Aufgabe löst diese Tas- zunächst einmal zu bestimmen ob der Lösungsraum nicht leer ist werden sie wieder das Beispiel mit der Vorlesungs Belegung kann es kann sein dass der Randbedingungen das dafür sorgen das es keine Lösung gibt ja das und das der Lösungsraum F von die und die leere Menge ist das muss man natürlich vorher abklären und wenn es keine leere Menge ist wenn es also zulässige Lösungen gibt dann wollen wir nicht und eine zulässige Lösung daraus konstruieren sondern wir wollen eine konstruieren die diese Zielfunktion je nachdem wie die Richtung ist entweder Minimieren oder Maximieren das heißt also wir wollen ein X finden so dass der Zielfunktion wird von X das Minimum ist Bindung über alle möglichen Ziele Funktionswerte der Lösungsmenge oder das Maximum genommen über alle möglichen Ziele Funktionswerte ich ich schreibe das so abstrakt närrisch weil das habe ich dann müssen wir auch schon angekündigt das ist die Ebene war die wir sinnvollerweise einnehmen werden um auch über solche genetischen Algorithmen zu sprechen über Algorithmen die im nicht für eine spezifische Problemstellung konstruiert sind die für Tier Problem sondern für eine ganze Bandbreite von Optimierungsproblemen da muss man natürlich eine gewisse abstrakte Ebene einnehmen aber sehr verständlich denn die immer wieder auch auf die Ebene konkrete Beispiele zurück um zu sehen was das jetzt umgesetzt im konkreten bedeutet so fern war schon mal damit an Mirtschink haben Sie es mit mal gesehen da oder was immer verschiedene Sachen in denke er Algorithmik versteht man darunter folgen sicher dass die Kamera das Bild gut sieht sie haben einen ungerichteten Grafen irgendwie sowas vielleicht ein bisschen größer denn mal ich mal jetzt zusammenhängt der muss aber nicht zusammenhängend sein so und Sie wollen jetzt eine gewisse haben farbige Kreiden des was Sie suchen ist eine Kaltenegger Menke eine Kantenlänge die dir Eigenschaft hat das keine 2 kannten sich an einem gemeinsamen entknoten berühren wenn ich die Kanten zum Beispiel in die kann man einnehme darf ich die 4 nicht mehr nehmen sondern ich kann zum Beispiel die hier noch leben jetzt kann man sich schauen welche ich noch nehmen kann ich kann zum Beispiel die hier nehmen die und ich kann jetzt mindestens noch die hier leben und ich glaube jetzt kann ich keine mehr hinzunehmen ohne ohne diese Eigenschaft zu verletzen 4 könnten habe ich jetzt so spontan einfach gefunden die die Eigenschaft haben dass sie dass sie sich gegenseitig nicht einen gemeinsamen Knoten berühren in den entknoten das ganze er wird die Relevanz des Ganzen wird vielleicht sichtlicher ich zum Spezialfall übergehe zu debattierten Grafen dass sämtliche könnten dass die Knoten Menge aus 2 Teilen besteht ich links und rechts einordnen kann und die Kanten mehr und alle kannten gehen zwischen den Knoten hin und her die rings um die rechts sind so wie ich das hier gezeichnet habe so vielleicht ein bisschen dicker und jetzt wollen sie eine maximale Zuordnung von links und rechts möglichst viel zuordnen ich nehme mal den hier her ohne die beiden zu dann kann ich dir zu ordnen dann kann ich dir zuordnen kann und dann kann ich noch zum Beispiel die hier zuordnen ja hier ist offensichtlich dass es mit Schink maximal ist ja wohl alle auf der rechten Seite sind gematcht besser geht es ja gar nicht hier weiß ich nicht genau ob das wirklich maximales ausführlich die maximale Anzahl von könnten ist ich bin ja einfach mal irgendwie so spontane von oben nach unten und hinten rum Rechtsflanke durchgegangen und wer weiß ob nicht ob das die richtige Strategie Haubitzen Optimum zu finden vielleicht gibt es ja auch mit dem mit 5 Karten kann sein habe ich mir keine Gedanken dazu gemacht das ist ein Mädchen das heißt der Import ist ein und gerichteter Graph so bezeichnen wir immer Grafen das haben Sie sicherlich schon wirklich 2 oder so gesehen bestehend aus einer großen Menge VOV wie wir Text ist einer der beiden Worte die typischerweise für Knoten Grafen anwenden werden es andere wurde Snaut Knoten und Etsch kann der sowas ist das ein Import also das ist vor allem das Sie wenn sehen dass eine rechts natürlich auch so spezieller Fall eines Input was ist ein Input 1 zulässige Output eine Teilmenge der Kanten Menge ebenso wie sie gemalt habe so dass keine 2 Kanten darin eine einen Inzidenzen Knoten gemeinsam haben sich nicht an einem gemeinsamen Knoten berühren und die Zielsetzung ist die Kardinalität der ausgewählten keine Menge zu maximieren ob mir das längst gelungen ist wie gesagt weiß ich nicht spielt es auch keine Rolle wir werden in Kürze sehen wie wir beispielsweise hier bei Mirtschink zu einem optimalen Ergebnis kommen können sogar in sehr effizienter Zeit so war also das nochmal so formuliert wie das auf der Folie zu haben die Instanzen des Imports das aus der kalligrafischen Menge I sind die ungerichteten Grafen die Lösungsmenge zu einem gegebenen Input G ist die Menge aller Mädchens in diesen Grafen ja also das ist eine natürlich nur eine zulässige Lösung sie können sich leicht auch der zweite der dritte 4. zulässige Lösung dazu was können die leere Menge übrigens ist auch nach Definition der zulässige Lösung wenn auch nicht gerade eine eine mit besonders hoher Kardinalität und die Zielfunktion sagt einfach aus wie viel wie bekannte Mädchen drin sind das normale ist das müssen
wir auch noch mal kurz hier anhand dieses Beispiels erläutern wir darauf immer wieder auch zurück kehren werden und weil es auch wenn sie mal später etwas weiter mit dem Thematik zu tun haben werden für den das auch wieder begegnen wie Spitze mit zählt man typischerweise unzulässige Lösung meine spezifiziert sie kann dabei Mertsching hier unten gucken man spezifiziert sehe durch einer Grundmenge nämlich was ist die Grundmenge hier die Menge aller möglichen Teilmengen der Kantenlänge das ist die Grundmenge und durch Nebenbedingungen sagen wir welche Elemente dieser Grundmenge tatsächlich mit sind welche wir als zulässige Lösung akzeptieren das ist die Grundmenge der Power stellt also die Potenzmenge sie Mathematik die Potenzmenge das ist die Menge einer Teilmenge einer Menge in diesem Fall die Menge aller Teilmengen der Kantenlänge das ist die Grundmenge und die Nebenbedingungen Zeit ganz schön ins den den Bedingungen sind da das eine Teilmenge M nur dann ein Mädchen ist werden für alle Elemente aus diesem Mädchen gerne sehen hier Sie haben eine kannte die V 1 und V 2 verbindet und eine Kante W 1 mit viel 2 verwendet sie nehmen sich 2 Kanten der aus dem Mertsching egal welche und sie fordern die nehmen Bedingung ist dass diese Knoten alle unterschiedlich sind was das das kann dass keiner ein Knoten der einen der Kante entlud noch der einen kannte ist das steht hier mit diesen 4 und gleich als Bedingungen alles noch mal genau auf formuliert ein Import der Schädigungen Output ist gegeben durch Grundmenge und durch Nebenbedingungen die sagen welche Elemente dieser Grundmenge sind tatsächlich zulässige Lösungen der noch mal ganz kurz das haben wir gemacht wir haben ein Prädikat eingeführt dass hier Sinn dieser muss als ein Prädikat eine Botschaft Funktionen die sagt er auf der Grundmenge gesagt welches Element der Grundmenge tatsächlich eine zulässige Lösung ist und welches keine zulässige Lösung ist
gut wir können das Mädchen Problem auch noch mal vom Maler spezifizieren nämlich dass wir sagen und dann machen auch Schluss damit keine Sorge nämlich dass wir sagen werden die wir reden gar nicht von Element von Mengen von Elementen des ist für das für die Behandlungen im Computer und praktisch von solchen erfahren von Mengen zu sprechen von solchen anschaulichen Gebilden wohl bei wem kommt wieder immerhin sind letztendlich zahlen wir müssen also alles was wir um Computer lösen wollen in Zahlen ausdrücken und was wir hier machen ist dass wir nicht von Mädchen zu reden sondern wir reden von 0 1 Vektoren auf der Kantenlänge die besagt X für eine Kante also Sie können sich die Kantenlänge Menge indiziert vorstellen kann eines könnte 2 kannte 3 dann haben Sie oder meinetwegen auch könnte 0 kann 1 kann 2 dann haben Sie hier also bei X von E 1 einen ganzzahligen Index wie ganz normal wie ganz normal aber er ist und die Semantik ist diese kannte gleich ein das X auf einer Kante ist gleich 1 genau dann wenn diese Karte Mertsching ist gesucht ist also ein X gesucht ist nicht nur eine Menge sollen gesucht ist ein Vektor x 1 0 1 Viktor dessen Komponenten indiziert sind mit den Karten durch irgendeine Indizierung der Karten durch und eine Nummerierung der kannten unternehmen bedingt dass sich jetzt schön elegant ausdrücken nämlich da die alle kannten die zu einem gegebenen Knoten ich betrachte hier der so Sommer alle kann geklingelt wurden in Sittensen kennen Sie diese Art und Weise mit zum Zeichen umzugehen meistens haben sie hier in der Mathematik man so gesehen sowas wie I gleich 1 bis n das soll den vertraut sein das kann man natürlich auch so schreiben man kann sich überlegen dass hier über die Elemente einer Menge summiert ist und das könnte man wenn man unbedingt will auch so schreiben dass man die Menge da in der schreibt und dieser zweite Formulierung die erst mal bisschen komisch und unnötig kompliziert aussieht die lässt sich verallgemeinern zu einer Summe von irgendeinem x irgendeine Art muss keiner zahlen sollen aus irgend einer Menge muss keine Menge von Zahlen seien schon gar nicht Intervall 1 bis n das ist insoweit so weit hoffentlich vertraut oder wenn ich es Ihnen ab jetzt vertraut so wie summieren also über alle Knoten auf aber alle Kanten auf die Inzidenz wird zudem Knoten voraus die den V als benoten waren dazu 7 Ticks auf wir werden uns die Semantik ist das da dieser wird eines ist wenn wenn wenn diese Kante zu Mertsching gehört und die Forderung dass dieser Knoten nur eine möglich nun zu einer einzigen maximal einer Mertsching kannte gehören darf übersetzt sich jetzt schön einfach in die Linie Bedingung das diese Summe der einzelnen die steht kleine gleich 1 ist sprich maximal 1 diese X wird es 1 1 1 bis 0 sein so und jetzt haben wir es aber so weit okay es sieht wieder kompliziert aus keine Sorge also Wesen das vom den weg sie haben sich das TSP noch mal zur Veränderung wie das Ganze sie haben in der anschaulichen Form Punkte in der Ebene oder im Raum oder auf irgendeine Oberfläche und Sie wollen eine möglichst kurzen Strecken zukäme durch diese Punkte legen so dass jeder Punkt genau einmal berührt ist denn das ist jetzt mal durchdiskutiert dass das konkrete Anwendungen in der Fertigungstechnik an allen Ecken und Enden hat stellen sich vor dem Roboter der Schweiß period auf Mackerras sowie abfährt und der Schweißarbeiten zu tun der muss der Film soll natürlich möglichst schnell seinen Weg machen damit der Durchsatz der ganzen Fertigungsstraße nicht vielleicht vermindert wird dadurch dass dieser Roboter so lange braucht so aber wir haben auch gesagt das ist nur die anschauliche Variante ganz allgemein wenn wir jetzt von der Ebene oder von der Karosserie die abstrahieren und den allgemeinsten Fall die Essenz rausholen dann reden wir nicht mehr von Punkten in der Ebene oder sonst irgendwo werden von irgendwelchen Objekten die nicht näher benannt sind die einfach nur gegeben sind als Indiz ist 1 bis 1 aber keine Sorge denn so vor dem egal was es ist ob das Punkte in der Ebene sind oder wer weiß was und was wir wirklich als Input haben dann ist keine im auch keine Punkte mit ihren euklidischen Koordinaten der Ebene mehr sondern alles was wir dann abstrakt haben sind die Distanzen von jedem Punkt zu jedem Punkt die Distanz wie lange es dauert oder wie viel wie lang der Weg ist um von dem ein Punkt zum nächsten zu kommen das ist das in dessen was notwendig ist um das TSB zu zu lösen so was ist jetzt der Output der Autor des wieder eine quadratische Matrix also den Tod ist eine quadratische Matrix man Objekte so typisch zu verbinden der der Input ist eine Garage Distanz Matrix der Output ist alle worauf ich 0 1 Matrix mit der Semantik ja 1 1 gesetzt einem Eintrag I J wenn der Weg von Ina nach er Teil dieser Rundtour ist oder anders formuliert wenn zyklisch J unmittelbar auf wie folgt dann können wir die Zielsetzung schon mal sehr einen sofort und einfach schreiben nämlich das hier das sind die Distanzen das sind die das in die Einträge die sagen welche welche unmittelbaren Verbindung von welchen egal welchen J tz jeweils tatsächlich noch unter drin sind und mir dass hier mit dieser Doppel Summe über alle über alle Felder über alle Einträge dem er der beiden Matrizen auf war steht hier wenn Sie sich an einen Sommer und mir rechts ansehen wenn sich eine also man rechts ansehen dann ist der entweder neue wenn das x 0 ist oder er wenn das X 1 ist hatte hatte also so man denn wird die Ort das heißt die Summe summiert alle des Iraks auf für die XJ 1 ist nach unserer Semantik zumindest also alle des als auf alle Distanzen für die Wege die in die tatsächlichen darunter drin sind und genau das ist es was wir wollen jetzt damit haben wir schon
mal die Zielsetzung formuliert wir sind immer noch nicht dabei also wir
bekommen heute zu den Algorithmen keine Sorge wir machen wir machen noch ein bisschen vor ja der Trockenübungen mit algorithmischen Problemstellungen die in den Bedingungen die Grundmenge ist die Menge aller 0 1 Vektoren wächst die Nebenbedingungen die jetzt sagen unter welchen Umständen ein solche 0 1 1 0 1 Matrix um genau zu sein eine und oder welche Umstände eine solche 0 1 Matrix tatsächlich eine zulässige Lösung sind das in den man mit denen die sagen dieses X ist tatsächlich eine Rundtour davon an 1 mit dem Gesicht nicht K 1 Punkt kein Objekt folgt auf sich selbst also die X auf der die Übernahme müssen alle 0 sein 2. neben Bedingung für jedes für Sie diese Schreibweise mit dem Vorzeichen sind darauf vertraut Ostern Mathematik nämlich an gut 2. Bedingung ist was macht so einen Strecken Zug aus eingeschlossen Strecken Zug es geht wir denken uns denn natürlich orientiert ist vollkommen egal in welcher Orientierung wie hier in der Ebene im Allgemeinen ist es nicht egal denn wir wir haben es ja so weit abstrahiert dass die Einrichtung und die Einrichtung nicht unbedingt gleich lang sein müssen was auch realistisches denken Sie Sie müssen nicht im realen Straßenverkehr durch zum Beispiel Sie am 2 Punkte in Darmstadt Sie wissen es gibt ne Menge Einbahnstraßen dann startet die des tanzt vom sagen mal zum Beispiel vom also Sie wissen auch dass diese ganze Umkehrung des die Unterführung und so weiter ja die die die Distanzen der Einrichtung wo sich unter Führung geben müssen von beispielsweise Rheinstraße zum Karolinenplatz und umgekehrt vom Karolinenplatz zur Rheinstraße sind unterschiedlich in dem ein vermisst unter Führung nehmender vollkommen sie direkt durch ich hoffe ich habe es mich jetzt nicht geortet als der Geographie in Darmstadt unkundiger aber so habe ich das irgendwie in Änderung von meinem Autofahrten in Darmstadt so also die Arretierung des allgemeinen wichtig so das hilft uns aber auch diese Orientierung wenig zu sagen es geht genau eine kann daraus und genau eine Kante rein das ist essenziell für einen solchen geschlossen Strecken Zug können wir wieder gut formulieren einen mit denen ist für jeden Knoten ist die rauhe Anzahl der ausgehenden Kanten gleich 1 das heißt die Summe der Echse der rausgehen kann es gleich 1 eben ein wer das 1 sind 0 und das kann ich einfach wieder durch auf summieren hier darstellen genau dasselbe für die ausgehenden Kanten so das sind den Nebenbedingungen oder wir haben es gesagt keine Knoten folgt auf sich selbst und wenn ein Knoten gibt es genau eine reingeht und genau einer rausgehen ist damit die Menge der zulässigen Lösungen wie ich sie ihnen hier dargestellt aber beschrieben ok das die Bedingungen sie bauen die belegen dass sie am Anfang rauskomme aber wir müssen doch am einfach rauskommen weil ja auch der in an fahren wenn wir zum Beispiel Anfang ist auch beim Anfang geht eine kann Wein also das es ist noch nicht das Problem aber das ein Problem so die Damen und Herren zum Hörer der Aufnahme können sicher zum Kaffee holen gehen ich bereue ja genau das könnte zum Beispiel sowas entstehen wenn ich das mal versuche das Beispiel möglichst nachzuempfinden so das das schließlich ihren das hier in Basel wurde ein Schluss gibt und hier wie Sie das auch so dass es so aussieht das ist sogar sehr wahrscheinlich dass das eine optimale Lösung ist das optimale Lösung nach dem gehen Dinge wie wir sie jetzt formuliert haben so aussieht wie rechts und nicht so aussieht wie links aber Sie haben wollen ist das was links steht nicht das was rechts ist also brauchen wir noch weitere Nebenbedingungen ich habe zwar gesagt es es meist recht einfach denn nehmen mit dem zu formulieren die Funktion aber es ist auch nicht allzu schwer da noch irgendwas zu vergessen das ist eine Möglichkeit diesen mit denen zu formulieren ich will es Ihnen kurz an der Tafel skizzieren was diesen mit den besagt wenn Sie so eine Zerlegung haben in 2 so Zyklen dann können Sie zum Beispiel Linie durchziehen das Geld dass diese Intuition ist natürlich nur für diesen Fall in der Ebene geeignet aber das lässt sich nur das was ich Ihnen hier intuitiv sage lässt sich natürlich auch genauso gut abstrakt Übertragung auf den allgemeinen Fall sie haben hier die Menge S Teilmenge von Knoten und ihren es quer viel es hat 4 Knoten ist wer hat auch Knoten so und die Bedingungen die dort haben ist für jede Zerlegung der Knoten in 2 nicht leere Teilmengen S und das Klehr muss mindestens eine Kante gehen von erst nach es quer das sagen diese Bewegungen hier die auf Messen mich so brutal aus so war steht hier für jede Teilmenge die nicht die ganze Menge ist hier sehen Sie ganz klein 1 durchgestrichen beim kleiner gleich also echt kleinere Teile Teilmenge von 1 bis n es soll aber auch nicht wer sein das heißt eine echte Zerlegung in 2 nicht leere Teilmengen für jede solche Zerlegungen soll gelten es gibt mindestens eine Kante größer gleich 1 die Summe der könnten wert das größer gleich 1 gibt mindest eine kannte J so dass die liegt und JENS klären die also von einem Knoten I in einen in einzelnen schönen Vereinen nur den es zu einem Knoten nach es quer geht und wenn Sie das noch zur sich einfügen wenn sie das nochmal Moment überlegen werden Sie mir sicherlich zustimmen dass damit das Problem vollständig beschrieben ist sie damit tatsächlich spezifiziert haben die Menge aller zulässigen Lösung sind genau das was wir haben wollen dieser Rundtour ich wieder nicht weiter eingehen das ist natürlich noch gut gruselig was hier steht nicht nur weil zu komisch aus so rosig aussieht sondern des Freundes der nicht weil sie ein exponentieller Anzahl von Bedingungen haben ja exponentiell Sie wissen was das heißt 2 hoch 10 ist schon 1022 1. Million 32. Milliarde und so weiter ist als und stellen Sie haben frei ich bin mir nicht sicher bin wenn sie wenn sie was machen sie mit diese beiden Teile nach die wenn wir denn nur so was machen das wiederum widerspricht dann den man mir Dingen die auf der letzten Folie hatten das genau eine kann rein genau meine kann daraus geht ja aber es widerspricht diesem mit keine kürzer seiner dass keine zulässige Lösung sie meinen wir das akzeptieren soll ach so ja also vor also Folgendes ist vielleicht vielleicht interessanter Punkt ich glaube ich war ich glaube ich habe ein Gefühl dafür worauf Sie hinaus wollen denken wir im Straßenverkehr ja da haben Sie vielleicht den Hauptbahnhof nicht Verbrennungen schließt Beispiel den Karolinenplatz als einen der Punkte den sie Anfang wollen aber natürlich kommen sie laufend aber trotzdem am Karolinenplatz vorbei ja sie haben ihre unter eine Strecke von Licht Wiese zum Hauptbahnhof und kommen da vermutlich am Karolinenplatz wobei sie eine Strecke drin von Heiligen nach Eberstadt und kommt vermutlich am Karolinenplatz vorbei einer der wahrscheinlich nicht aber Sie verstehen was ich meine ja natürlich kommt man physisch dann an diesem Punkt vorbei aber was man machen würde ist dass man dann beispielsweise man hat indes das Matrix eine eine eine eine Distanz von was nicht als Beispiel von Licht Wiesel nach Hauptbahnhof da man Distanz wird dem wir vorher ab berechnend abgelegt haben und dass wir physischen Karolinenplatz noch mal vorbeikommen spielt dann gar keine Rolle mehr kann natürlich im Einzelfall
er tatsächlich zu einer Verbesserung führen wenn wir so sein Information noch drin haben dass es mir physisch dabei vorbeikommen dass wir das Apcoa Karolinenplatz rausschmeissen können falls so eine Verbindung drin ist dann wäre das nur Variationen des das Handlungsreisenden Problems die Algorithmen die wir betrachten haben Vorteile dass sie eben nicht nur auf eine Problemstellung spezifizierten so aus auch mit Variationen klar kommen er werde nun eine Variation des Problems wo man sich noch mal genau überlegen müsste für die spezielle Situation wo wir sind was genau ist diese Variationen ja ich hat es angedeutet wenn ich Sie richtig verstanden habe sie war ja zu diesem Koffer haben die wenn Karolinenplatz ein Punkt ist den man anläuft und sie haben und und und an der Verbindung geht über den Karolinenplatz dann sollte zum Teil des zum Input dazu gehören zu der kannte nicht nur die Information wie weit lang ist die Kante sondern auch die Information dass Sie am Karolinenplatz vorbei geht so und so ist glaube ich das glaube ich dass die Variation die sehen im Hinterkopf hatten was ist die SP angeht ich habe mich mal länger mit jemand anderes darüber unterhalten der der intensiver dran arbeiten wir waren uns beide einig wären schon unglaublich viele TSB bis irgendwann das sehen Wirtschaft gesehen aber noch nie so reinrassig wie man es hier natürlich aufbereitet darstellt es sind immer irgendwelche kleinen Verkomplizierungen dabei so dass die Problemstellungen bisschen anders aussieht als in der Vorlesung irgendwelche Zusatzbedingungen oder Zusatzinformationen aber genau
das habe mache die Kinosaal Vorlesung um Algorithmen kennen zu lernen die mit solchen klein waren und geht denn wenn Sie zum Beispiel so Teams Problem anschauen sowie 7 kleinere da Variation daraus machen dass sie zum Beispiel sagen es soll zwar möglichst weit sortiert werden aber zum Beispiel die beiden dürfen auch wenn sie so sind dürfen sie trotzdem nicht so rum Sasonow müssen so um gleich oder so etwas wenn Sie mit einer Variation einführen haben sie sofort verloren sie können keine Sortieralgorithmus mehr darauf anpassen auf solche Variationen also ich finde es jedenfalls nicht wie man das machen sollte was wird oder so auch sehr schwierig werden so noch im per kleine Sommer dieses ich denke wir sollen es langsam mal zu den Algorithmen übergehen also ich wäre wäre ein paar denn er überschwänglich werde aber natürlich auch in der angeben welche vorhin nicht übersprungen habe damit sie das bei der Vorbereitung auf die Prüfung natürlich genau wissen das ist jetzt wichtig ist comma langsam zu den Algorithmen wenn man ein Algorithmus exakt der Konstruktions- Version für Zulässigkeit Versionen wenn es beweisbar das entscheiden period es beweist nur wenn er grünes beweisbar eine zulässige Lösung findet vorausgesetzt es gibt eine sonst davon natürlich sagen es gibt keine Lösung und den Optimierungs- Versionen weder beweisbar eine optimale Lösung findet approximativ heißt das ist jetzt nicht genau spezifiziert was das heißt der Algorithmus findet beweisbar eine Lösung die vielleicht nicht ganz zulässig ist aber nicht weit weg davon ist das ist oft sind vorbei Problemstellungen bei dem man keine Hoffnung haben kann dass man sie hundertprozentig durch Algorithmus lösen kann aber 99 Prozent ich kann man sie durch ein Rhythmus lösen so dass man hinterher noch an den kann durch scharfes Sehen gucken hier und da ein bisschen verschieben ein Beispiel dafür ist der zum Algorithmus beispielsweise wurde sie melden sich an sie geben Prioritäten die 3 Termine für Kleingruppen Übungen sind möchte ich gerne haben die 3 gehen gar nicht und wenn wenn wenn abgeschlossenes wenn jeder Teilnehmer seine seine Angaben gemacht hat dann Versuch der Zuteilung des Algorithmus übrigens ist das genauso mitschwingt Algorithmus also muss für das mit den Problemen was sich in vorigen eingangs erwähnt hatte versucht dann eine Lösung zu finden unsere Erfahrung ist er schafft es nicht hundertprozentig erschoss auch nicht 99 Prozentig aber schafften sie so 90 Prozent Licht und der Mensch können der gehen und kann die restlichen 10 Prozent die der Algorithmus nicht geschafft hat kann er die dann noch im geplanten und Herr Fricke ist also durchaus sinnvolle auch da wo man keine Hoffnung haben kann dass auf ein Algorithmus der die Problemstellung hundertprozentig löst also nichts für Sie Lösung findet dann eine Lösung wenigstens so finden die nah an der Zulässigkeit ist denn ich war ja wohl nicht mehr viel zu tun ist um die Lösung zulässig zu machen Optimierung heißt wir möchten eine Lösung haben wird ist eine zulässige Lösung die Beweise die vielleicht nicht optimal ist aber beweisbar nicht zu weit weg ist von Optimalität und was wir damit es approximativ also nicht heuristisch fordern wir es gibt eine vernünftiges mathematische Maßstab der und sagt das wie weit wie weit die ist die Lösung die es brechen hat weg ist von von der optimale Lösung beispielsweise 10 Prozent schlechter als die optimale Lösung oder 5 Prozent schlechter als die optimale Lösung und es ist beweisbar dass er tatsächlich so gut mathematisch beweisbar dass er tatsächlich so gut ist wo nix beweisbar ist diese Algorithmen heißen heuristisch und das sind das ist die Mehrzahl der über die wir hier betrachten werden weil es halt mit Problemen Problemstellung zu tun habe mit 1 bis Problemstellungen bei dem man nicht mehr viel beweisen kann oder bis es hat kein Mensch die Beweise gefunden deshalb steht auch hier nur der gewusst versucht Erkennens wird versucht eine zulässige oder einen halbwegs zulässige Lösung zu finden aber keine Garantie und der Optimierung er versucht eine optimale oder allerdings dieser Gemeinde Lösungen zu finden aber das hat trotzdem keine Garantie so dieses
Kapitel wenn wir ganz kurz streifen mit den Dingen die halbwegs unterhaltsam sind und die mathematische sagen wenn wieder ausblenden wenn ich Zeit bleibt werden wir darauf zurückkommen aber nicht unbedingt
haben können Sie ein bisschen genauer nachlesen in diesem Buch das wenn sie auch eine Bibliothek bei uns da finden Sie auch die Kartons drehen Sie sehen ja an einigen Stellen ist das noch genug Platz ist da waren Kartons vorher drehen
die Fohlen unterstellt waren zu einer Zeit als man also aber kleine Informatikdozenten noch nicht so richtig das Bewusstsein hatte Ende Bezug auf Urheberrechte im Internet also schon ne Weile her inzwischen hat man dieses Bewusstsein und in der Vorbereitung dieses Semesters habe ich ist eine der wesentlichen Sachen ich einen Foley gemacht habe war erst einmal die Folie diese Kartons rauszuschmeißen ja damit ich sie damit ich die die Aufzeichnungen hier und die Folien problemlos ins Internet gehen kann und nicht in Lumpen Intranet hineinhängen aus was was zwar auch nicht korrekt ist nach meinem Verständnis nach meinem Rechtsverständnis aber immerhin wird man da mit großer Wahrscheinlichkeit nicht erwischt aber was ist Intranet denkt so weit ich weiß also mystisch wird schon schwierig sei mit Google finden die Rechtsabteilungen der Firmen das dann nicht so sie sind also der Chief Algorithmen Designer ihrer Kompanie der ihr mich ja comma soll Ihres Unternehmens und sie soll jetzt ein Problem lösen das sehr wichtig ist und sie arbeiten und arbeiten und arbeiten und arbeiten was gerungen ändern sich also einige Editionen Plinius Algorithmen gelernt haben und stellen fest wie es geht nicht Sie finden nichts es geht nicht wenn sie nicht fest sondern sie stellen fest ich krieg's nicht hin so was natürlich nicht wollen ist dass sie jetzt ihren Boss beichten müssen ich kann beim besten Willen keine effizienten Algorithmus finden ich vermute ich bin einfach zu dem dazu das wollen sie nicht so wenn sie das tun dass er dann wird ihr Boss vermutlich wenig Verständnis dafür haben also vielleicht nur etwas zum Wort Boss es geht doch das Wort Chef und das Wort schief im im Englischen also das was was wir normalerweise Chef ansehen es im Englischen eigentlich Bars Chef ist meistens weiß das jemand der Küchenchef genau und also der Ort Koch und schief ist eigentlich Häuptling kann tragen häufig auch auf Polizeichef also Polizei Klink und manchmal auch dann eben auf so ein bisschen salopp auf andere Position des Chief Algorithmen Designer also Sie wollen Sie denn nicht zu Ihrem Chief oder Chats und sie ihn zu ihrem Boss und sie wollen natürlich nicht dass der Boss sie umgehen feuert sondern sie wollen sollen sagen hier ich kann keinen effizienten Algorithmus finden weil es gibt einen solchen Algorithmus nicht das ist das was sie wollen zu sagen dass eine Opas die Aufgabe die die mir gestellt das ist eine unmögliche Aufgabe wobei das natürlich auch noch können sich vorstellen nicht allzu leicht ist ja das eine Problemstellung Infekte bitte nicht unbedingt machbar ist ich will hier nicht in diese Theorie der NP-Vollständigkeit einen steigen hier es gibt eine solche es gibt Techniken mit denen man das beweisen kann und wie schon beim letzten Mal gesagt hatte für die allergrößte Mehrzahl der Problemstellung ist es tatsächlich so dass diese Problemstellung endlich wer ist ich will nochmal wiederholen was das konkret bedeutet in der Praxis ist ich will jetzt nicht aber wir sagen wie das definierte so weit also was konkret bedeutete Praxis bedeutet nehmen TSB als Beispiel ja dass es endlich mehr oder dieses Zuordnungsprobleme die Universität das auch endlich wenden sich die SPD mehr für die für jeden Algorithmus denn sie für das TSB basteln egal wie der aussieht egal wie wie ja der Gebasteltes für jeden denkbaren Machbaren Algorithmus wenn er uns den in C C plus plus klar aber es Müller oder auch ein Quantencomputer so das Thema gibt er implementieren können wird es möglich sein eine Eingabe vielleicht von der Größe von 50 Punkten zu finden 5 Punkte der Ebene muss gleich abstrakt sein 50 Punkte der Ebene und ihr Algorithmus rechnet sich darauf tot braucht länger als dieses Universum in Zeit geben wird wenn die Physiker mit die Einschätzung Recht haben wesentlich länger als brauche mehr Universum es gibt nicht die eine Menge von 50 Knoten sodass alle also Gesichter Tod Rede werden sondern für den Algorithmus gibt es jeweils eine spezifische Menge von Fernsichten wurden die zu finden ist nicht ganz einfach Baumann nicht finden man hat bewiesen dass so Problemen Beschwerde sind damit weiß man dass das so der Fall ist da also das ist ein
gepflegtes Understatement kennt er wieder listet man eh Importen kann keinen bis hofft Kurt so also viel zu wissen dass das Problem hat es schwer ist in dieser in dieser Bedeutung das ist natürlich schön drastisch von den Chancen ausgedrückt er lässt sie aufhören damit ihren Kopf gegen die Wand zu knallen und stattdessen etwas besseres zu tun nämlich das was wir eben gesehen haben heuristisch oder approximativ vorzugehen wenn sie Glück haben wenn sie oder gut oder für tüchtig sind tüchtig sind und das Glück des Tüchtigen dabei haben so vielleicht formuliert dann finden sie einer brauche aktive Lösung das heißt sie können zwar nicht Optimalität garantieren aber sie können garantieren dass sie nach einem vernünftigen Maßstab nicht weit weg von Optimalität sind wenn sie nicht so Glück oder nicht oder nicht so tüchtig sind dann ist alles was übrig bleibt etwas Mystisches und was nicht schlecht ist ich will das Ruf kein Fall Schlechtriemen Gegenteil will mehr über Heuristiken vor allem die sind in der Praxis verdammt gut wenn sie gut gemacht sind ja also da kann man es gibt oft Situationen in den kann man alles durch Algorithmen finden wo über irgendwelche Indizien sagen kann da ja im Normalfall finden die sogar die optimale Lösung das sieht ganz danach aus dass die Lösung die wir hier dann haben durch diese Ristic tatsächlich optimal sind oder vielleicht ein paar Promille weg von Optimalität so es gibt weitere Möglichkeiten für ein Algorithmus der exponentiellen Aufwand hat natürlich können Sie auch dass die SP mindestens mit Faktor werden auf denn sie mich alle Möglichkeiten ausprobieren sehr nur hatte viele Permutationen nur in Anführungszeichen die Fakultät wächst dramatisch aber das eine Exponential Zeit Algorithmus in der Hoffnung dass die Instanzen dieser eingeben das dem USGS exponentiell ist aber in den Inputs die sie tatsächlich hier betrachten vielleicht nicht exponentiell ist das ist die Hoffnung hier ja bei heuristischen Algorithmen haben wir die Hoffnung dass die Lösung gut ist aber wir haben die Laufzeiten der Kontrolle hier haben wir die Garantie dass das am Ende des Algorithmus bei der Terminierung die Lösung optimal oder approximativ ist aber wenn die Laufzeit nicht unter Kontrolle sondern hoffen dass die Laufzeit bei den Instanzen die der freien Wildbahn wirklich vorkommen gut ist auch das ist eine Hoffnung die sehr oft sehr gut erfüllt ist andere Möglichkeit ist die durch aus oft ist wer das ist dass wir versuchen eine andere Abstraktion zu finden das dass man nur deshalb zu einer MP Koch vollständigen Problemstellung gekommen es war man vielleicht ein paar Dinge paar Indizien die in den Daten stecken ignoriert hat und wenn man die herausarbeitet zum anderen Aufzug zum kommt kommt man plötzlich zu einer andern Problemstellung die nicht mehr beschwert ist da ist zu diesem letzten Punkt möchte ich Sie auf die einer Vorlesung algorithmische Modellierungen Sommersemester Verfalls da werden wir genau solche Dinge betrachten so und jetzt Schluss mit
NP-Vollständigkeit jetzt überspringen wir das alles hier sie sehen Mathematik
Mathematik Mathematik Sie haben wahrscheinlich keine große Lust ich habe wahrscheinlich auch keine große
Lust also kommen wir jetzt
endlich zu den Algorithmen war er lang genug so wie viel Zeit haben wir heute aber nicht mehr so viel Zeit nach halbe Stunde noch ungefähr und ich muss auf Google aufpassen dass ich immer relativ zügig Schluss mache der weil solange das Einparken noch so lange Zeit bei mir dauert so lange ich das noch nicht ausreichen geübt habe das aber und paar so in Nachbarschaft basierter ansetzt da gehen um einen Schritt
voran zu einer 1. Intuition wir sind wieder beim TSB das ist das worum es in diesem Kapitel als Grundlage gilt zunächst einmal vielleicht die Frage an Sie schauen sich das oder 3 Bilder H können Sie auf Anhieb etwas darüber sagen ob das mehr ob ab dass eine optimale Lösung ist oder nicht wenn wir für die Kantenlängen euklidische die übliche normale länge in der Ebene annehmen bitte das nicht optimal genau die 2 quer Wege sind länger das können uns vielleicht da drauf ist Kranefeld vielleicht einem Beispiel kurz anschauen sie haben hier 2 Querwege die sich kreuzen und wenn sie die beispielsweise so miteinander verbinden warum ist das Kürzel mal wir beides in einem Bild ich glaube ich muss mir ich glaube ich sollte doch versuchen noch mal zu wünschen dass viel zu unübersichtlich klar mehr also ich würde mich freuen wenn die Fachschaft eine Initiative starten würde die alle einen Ewigkeit Beschluss das ist niemals so habe die TU Darmstadt bestätigt H für seinen Hörsinn abgeschafft werden vielleicht sogar die Hörsäle die keine Tafeln haben des Audimax wieder welche bekommen die und die die Tafeln haben vielleicht auch mal den wieder bequemere Tafeln haben wo man nicht laufen wischen muss so was ist die Situation hier wir die mal notieren das ist die das Bild sieht sieht so aus mit den 2 kannten nur die mal wirklichen ein Bild rein tun um die miteinander zu vergleichen dann stellen Sie fest das ist länger an dass es länger die dass es länger dass es länger die ist Kammerdiener unterteilen in D 1 und D 2 und die in C 1 und C 2 und der ganze Dreiecksungleichung anwenden ist kleiner gleich B 1 plus C 2 die ist kleiner gleich B 2 plus C 1 und wenn Sie beides zusammen nehmen dann kriegen Sie raus aber Plus des ist auf jeden Fall kleiner gleich der plus C unten und wenn wir nicht in einer Art und Weise haben sondern den typischen Fall wie hier dann haben sie sogar echt kleiner also kann es nicht dass das obere Bild die Rundtour kann nicht optimal sein so das Weizenmehl Nebenbedingungen worum es geht sind Operation wie dieser wir laufen auf der Lösungsmenge herum wir stellen uns vor die Lösungsmenge ist ein Graus mit Verbindungen dazwischen zwischen wiesen immer auf einen Knoten auf einer Lösung und wir gehen zu einer benachbarten Lösung deshalb heißen die sehen Sie hier noch mal oben in der Überschrift Nachbarschafts basierte ansetzte mehr das ist der abstrakte blickt der konkrete Blick bei diesem Beispiel ist wir suchen uns 2 Kanten mehr zum Beispiel die beiden noch 2 beliebige andere könnten sein können in direkt und fügen 2 neue kannten so ein dass ich wieder eine Rundtour ergibt wobei da noch eine Reparatur notwendig ist sie sehen dass hier wenn ich diese 2 Kanten Löcher wie ich das gemacht habe und dann die 2 kann entsprechend einfüge dann stimmt 1. einmal je nachdem wo mich die Einfüh- bestimmt erst mal um was mit und hier da kann nicht ich muss einen der beiden offengebliebene Strecken Züge umdrehen ich habe hier den rechten umgedreht damit das Ganze wieder zu einer Rundtour und ja das ist die Operation die man von einer Tour zur nächsten kommt ja wir haben sie in jeden Zeitung ist der ihn immer von Schleifen hier im programmiertechnischen Sinne wir haben eine Schleife wo in jeder Iteration wo wir zwischen 2 Iterationen immer eine zulässige Rundtour haben und in die Redaktion er wie dieser Rundtour schmeißen kann aus dem zu anerkannten rein und haben dann nach dieser Iteration wieder eine neue und war und hoffen dass wir auf die Art und Weise wie Staaten irgendwie vielleicht sogar minder zufällige Rundtour oder mit einer Rundtour die uns so nach einfachen Kriterien besonders gut ausschaut Staaten zu einer und hoffen dass wir so Schritt für Schritt zu einer das und und kommen darum geht es hier um das das ist ein Thema das sich sehr stark nutzbringend variieren lässt nämlich nicht einfach gucken wenn ich die 2 kann aus und entsprechend anerkannten reintue bringt das bessere Lösungen es sondern sondern zu zum Beispiel auch variieren dahin gehend dass man nicht in so einem lokalen Loch gefallen befanden bleibt wenn es keine Möglichkeit gibt durch einen so einen solchen Austausch Schritt zur besseren Lösung zu kommen das man vielleicht erlaubt doch einen verschlechternde ausschritt aus deutscher zu machen in der Hoffnung dass man dann wieder zu verbessernden kommen die besser sind als das wo wir gestartet sind oder auch wie wir dann später das in der Evolution Strategien genetischer Algorithmen für werden mehrere zulässiger Lösungen im Wettstreit gegeneinander antreten lassen wer die jeder von den verändert sich auf diese Art und Weise so ein bisschen das Prinzip von Mutation und Selektion aus der Biologie das der Revolution Strategien und die die so aussehen als ob sie das zu guten Lösungen führen werden die Leben oder duplizieren sich sogar und die anderen die so aussehen als ob sie in als ob sie ihren Sackgassen reingehen die streichen wir aus unserem Pool von zulässig ist und das ist so ungefähr das große Bild von diesem Kapitel so dann gehen wir wieder
zurück jetzt haben mehr eine gewisse Vorstellung davon worum es
geht abstrakt gesprochen wir reden viel von Nachbarschaftsbeziehungen ja wir sind in diesem Beispiel die wir vielleicht noch mal ganz kurz
darin diese sagen diese beiden Touren diese beide und tun das oberste und das und das Übel sind miteinander benachbart durch diese Operation ich dieser Gruppe Operation die wir uns als definierende Operation vorgenommen haben kommen wir von der eine Lösung zu andern und übrigens auch wieder zurück das symmetrische Nachbarschaft mehr derselben Art von Operation komme von danach dann wieder zurück so habe stark so
der Betrachtung sieht also eine Instanz ein Input A 1 Menge von Punkten in der Ebene beim TSB eine lief gegebene und wieder diese Notation hatten wir heute eingeführt er von I für die Instanz I ist er von E die Menge der zulässigen Lösungen Beispiel TSB die Menge der Rundtouren der echten Rundtouren ohne sub Zyklen und wir haben die Zielfunktion dass es beim TSB eben die Länge der Strecken Zugs und was wir für jeden einzeln wieder 1 eine zulässige Lösung definieren das sind die die wir mit so einer Operation erreichen die die das ist die Nachbarschaft sind des DLR man sind die zulässigen Lösungen die wir auf ihre Weise erreichen das heißt viel was wir uns abstrakt vorstellen ist jeder zulässige Lösung besteht denn wirklich die Menge der zulässigen Lösungen als Punkte in einem abstrakten Raum vor und dann ist es auch vollkommen egal ob wir vom TSB Rede von irgend einer Problemstellung das ist das der Grund dafür warum das Opfer ist immer der Grund warum man abstrahiert damit man verschiedene konkrete Dinge unter einen Hut bringen kann auf gleiche Art und Weise sehen und bannen kann und diese beiden und wollen von dem Bild sind so rum und so und mit einer Karte verbunden was gesagt ich komme mit dieser algorithmischen Vorschrift 2 kann rausnehmen anno 2 könnten rein nehmen von dem einen zum anderen mehr diese Abstraktionen macht auch vielleicht noch mal klar dass wir nicht unbedingt nur von einer Möglichkeit drehen wie man von einer Lösung sondern kommen kann es gibt auch es gibt auch bei bei derselben Problemstellung wie beim der SPD kann natürlich sehr viele Möglichkeiten wie wir von ab wie wir das definieren können man konstruiert eine neue Lösung aus einer gegebenen Lösung ja es gibt beispielsweise überhaupt keinen Grund sich auf 2 Karten zu beschränken wenn nur und so so so mit 3 Sie können das auch den Übergang von einer Tour zu einer hoffentlich bessere und Tour mit über 3 oder mehr Karten definieren über 3 kannten sie nehmen die 3 heraus dann bleiben diese 3 Teilabschnitte übrig und das muss ich gucken aber dass sich die so miteinander verbindet dass ich keine so Zyklen geben so eine könnte beispielsweise dann so eine Kante und so eine Kante und Sie müssen dann diese diese nur angedeuteten Teil Touren natürlich dann sprechen wo wenn ich es umdrehen das ist natürlich genauso möglich ja der ihn von einem abstrakten Schema ein dessen Basis wie die Algorithmen definieren die denn konkret zum Beispiel dieses oder oder dass man 2 kann ist das ist absolut konform dann zu dem was sie auch in der Übungsaufgaben machen sollen mit den Möglichkeiten ihre Programmiersprache die sie gewählt haben ja aber wenn vermutlich die meisten von ihnen werden vielleicht manche Zebus bloß oder oder ich weiß nicht was Jahr mit den Apps Aktionsmöglichkeiten Impro viele Möglichkeiten genau das nachzubilden dass die Algorithmen genau auf dieser Ebene sind und dann kann man sowohl die Problemstellung diese behandeln als auch die konkrete Definition dieser Nachbarschaft wie ein Fremdwort wir so sowjetische Supreme praktisch als konkrete Klassen abgeleitet von Interface ist reinstecken dass die Zielsetzung der praktischen Aufgabe so was es jetzt also eine Nachbarschaft jeder zulässigen Lösung wird eine gewisse Teilmenge der zu dessen Lösungen er zugeordnet ich weiß nicht ob Ihnen diese Darstellungsweise vertraut ist also wenn sie das ist eine Menge ist ihnen vertraut dass man 2 Lorenz schreibt das ist die Potenzmenge der mir von allen also die Menge also Teilmengen von einem und jetzt vielleicht nicht weiter zu vertiefen um eine so schreibt die Mathematiker können das genau sagen ach misst sich der Mathematiker ja gut das definiert einen Grafen ja die Knoten sind die Lösungen und die Karten sind genau diese diese Beziehungen von einer Lösung kann ich zu einer Mission algorithmischen Vorschrift kommen das heißt ich habe mir gerichtete kannte hier kann es durchaus mal sein sie kann ja durchaus einen unendlich großen Lösungsraum haben wir eine Problemstellung was wäre jetzt ein gutes Beispiel für ein unendlich großen Lösungsraum Thespis natürlich kein gutes Beispiel dafür ein Beispiel für für einen Problemstellungen unendlich großen Lösungsraum für die mir sein gut dass sich jeder wieder Problemstellung die bei den zulässigen lösen weil er die Intervall oder eine Menge von reellen Zahlen sind er ist natürlich automatisch der Fall gut mit wäre es auch kein passendes Beispiel ein und wie wir gesprochen haben symmetrisch oft genug ist die so ist algorithmische Vorschrift wenn man die zweimal anwende comma wieder zum Ausgangs- so Ausgangs Lösung dann ist die symmetrisch so jetzt haben wir genug hoffentlich langsam mit Formen und hantiert was wir brauchen und mit damit umzugehen ist etwas was wir beim letzten Mal schon schön intuitiv dargestellt haben da muss man eigentlich noch ein bisschen man nicht wir hatten letztes Mal so ein Bild gezeichnet die von einer Funktion die Frage von einer Funktionen von 1 die zum Beispiel so aus auslegt so sowas hatten wir letzte Mal das hier ist ein lokales und zugleich globales Optimum das das ist nur ein lokales Optimum ich denke es ist klar was gemeint ist der Mathematik haben sie mit optimal schon zu tun gehabt der Punkt hier der tatsächlich die Funktion global minimiert und lokale heißt eben nur in einer Umgebung ist es das Beste in einer kleinen beschränken Umgebung ist das die beste Lösung das ist entscheidend wichtig für diese Nachbarschaft basierten Ansätze denn wenn sie das machen was man erst einmal intuitiv machen würde was würde man das würde man machen in der zum Beispiel hier die SPD
man würde sich mit mit irgend einer mit und einer Lösung anfangen die man sich irgendwie konstruiert hat primitiv oder intelligent konstruiert hat und dann würde man gucken gibt es Möglichkeiten gibt es 2 Kanten die wenn ich die wegnehme und die Tour sowie der wieder zusammenfügen so dass sich insgesamt da besser Tour ergibt wenn ja mache ich das stellen habe ich das so Tour dann nicht weiter die von dieser neuen Tour aus Google wieder gibt es irgendwelche 2 kannten mich hier raus nehmen und dafür das ebenso umstürzte gibt es da wieder was Beßres wenn ja mache ich das wieder und irgendwann wird die Antwort na endlich vielen Schritten würde unweigerlich die Antwort nein sein es gibt keine 2 Kanten mehr von der jetzigen Tour dich in dieser langen Abfolge von um Konstruktionen wo ich hingekommen bin die immer in jeder und Konstruktion der Verbesserung der Zielfunktion gegeben haben wenn ich jetzt angekommen denn irgendwann kommt der Punkt wo es keine Möglichkeit der Verbesserung mehr gibt was kann sei keine mehr geben kann jetzt ist die Frage bin ich hier wo ich hin will oder bin ich hier wo ich eigentlich nicht in will wenn ich tatsächlich im globalen Optimum in der bestmöglichen Lösung gelandet oder dumm gelaufen bin ich nur an einer Lösung gelandet die im Lokal in dieser Nachbarschaft der unmittelbaren Umgebung nicht das ist mehr hat wo ich eben durch wegnehmen 2 Kanten und Umstöpseln wie auf dieser Folie ist das comma aber vielleicht gibt es dort immer bessere Lösungen mehr offensichtlich hängt es davon ab wo ich Stade den wenn ich hier gestartet werden und Schritt für Schritt nicht verbessere dann nicht da wo ich hin will welche gestartet werden und die Schritt für Schritt verbessere allein nicht da wo ich nicht hin wollte und das kann beliebig schlecht sein die Tour die rauskommt kann beliebig rechts ab deshalb ist es wichtig
hier sich über globales ein lokales Optimum damit auseinanderzusetzen was global das Minimum oder Maximum wenn immer noch Minimum das ist eine zulässige Lösung so dass der Ziele Funktionswert minimales ist über Global minimal ist also wieder Ziele Funktionswert jeder eine unzulässige Lösung ist größer gleich den Siedlungs- und wir diese eine Lösung ein lokales Minimum wiederum ist eine zulässige Lösung so dass der Zielfunktion Swertz optimal minimal ist in der Nachbarschaft es gibt von diesem können period aus in diesen Grafen bei dem ich Wochen haben es in der Nachbarschaft Grafen gibt es keinen benachbarten Knoten den ich mit einer Kante erreichen kann mit einer solch einer wünschen Summation erreichen kann der noch ob optimal ist der der besser ist schon Übung so die schönsten Bilder sind natürlich die wo es um diese Unterscheidung keine Sorgen machen müssen und damit wenn man so ein bisschen befassen mit dem schönsten aller Fälle das dann nennt man diese Nachbarschaft exakt wenn jedes lokale Minimum auch ein globales Minimum ist das heißt wenn das Bild nicht so aussieht sondern wir hatten es beim letzten Mal konvexe Funktionen wenn das Bild beispielsweise so aussieht wenn es keine lokalen neben minimal gibt dann können wir starten wo wir wollen wir kommen immer so da wie immer in einem lokalen Minimum ankommen kommt automatisch und global mit dem ja im globalen immer an ich habe das jetzt hier Minimum genannt alles natürlich für Maximus alles das so der erste Algorithmus und dann auch noch so einfach viel zu einfach wird komplizierter so kann das was ich eben mündlich skizziert habe wir stellen fest TSB beispielsweise wir beginnen in der Initialisierung mit irgend einer Arbeit war die mit der beliebigen zulässigen Lösung solange wie ja in der aktuellen Lösung für die aktuelle Lösung 1. einen Nachbarn es finden also den damit in der Nachbarschaft Grafen mit einer Kette kannte erreichen kann der hänge ich besseren sie Funktionswert hat dann nehmen wir so eine Lösung und das wird unser neues Sterne und mit diesen neuen Herstellern gehen wir wieder in diese wahrscheinlich in bitte ja ja natürlich ja sie müssen sagen wir so ja ja genau sie haben schon einen wesentlichen Punkt angesprochen die Definition der Markt Nachbarschaft ist oft genug heikel wie oft genug nicht ganz trivial wenn Sie die Nachbarschaft so groß wählen den kostet jeder einzelne Schritt unheimlich viel Zeit wenn Sie Nachbarschaft so klein wählen kann es sein dass sie viel zu früh irgendwo stecken bleiben sie müssen auch gucken dass sie tatsächlich innerhalb dieses Nachbarschaft Grafen von jeder Lösung zu jeder anderen Lösung kommen könnten betrachten Sie zum Beispiel folgendes betrachten Sie folgende Problemstellung war sie haben Besitzer dann noch okay sie haben eine Menge von irgendwelchen Stücken das Stück 1 bis Stück ändern ja mit länger aber ist oder Gewicht A 1 und Gewicht aber ein und die wollen Sie halbe-halbe aufteilen das ist der Input Output Aufteilung in 2 Mengen ja denken Sie Sie wollen wir wollen es falsch denken Sie an eine Scheidung und die sind Kosten Werte oder oder der einzelnen Güter und sie wollen halbe-halbe die Güter die sie habe nach den Kosten aufteilen ist es ist ein blödes Beispiel aber mir fällt auch kein besseres Beispiel für diese vereinfachte Version einer allgemein Problemstellung ein siehe möglich ist mehr an halbe-halbe zu kommen so jetzt gehen wir auf diese Art und Weise vor Sie haben eine Aufteilung hier zum Beispiel für 3. hier haben sie 3 oder 4 3 drin und sie definiert als Nachbarschaft Austausch das sehe dass Sie hier ein X oder ein Y haben und diese Aufteilung geht in eine neue Aufteilung über in dem sie das X und das y miteinander
einsetzen das soll y sein so so ja so kann die Nachbarschaft definieren schön einfach alle algorithmisch handhabbar was ist zu dieser Nachbarschaft Definition zu sagen genau der Nachbarschaft Graf um uns wieder im Garten der will würden sagen der Nachbarschaft Kraft ist hochgradig unzusammenhängend zerfällt in einzelne Zusammenhangs Komponenten das heißt Sie können sie keine mit einem weg von solchen Schritten hier niemals zu einer Lösung kommen und die Aufteilung nicht 5 zu 3 ist in gemessen an Anzahl von Städten aber wir wissen Sie dass das die guten Lösung wirklich die Aufteilung zu 3 Jahren vielleicht ist 4 zu 4 die richtige Aufteilung oder für für die die die die gleichen sich beide auf den 4 zu 4 die besten Lösungen oder sogar beinah Aufteilung 1 zu wir insgesamt 1 zu 7 wenn ein Stück besonders schwer ist ja und im beantwortet das bis ihre Frage es ist nicht meine nicht der Mann hat das Problem in gewisser Weise gebe ich Ihnen Recht verlagert aber verlagert in eine Problemstellung diese Nachbarschaft zu finden die man viel besser Intellektuellen im Griff hat als jetzt zu versuchen irgendwie von der grünen Wiese aus ein Algorithmus für so ein komplexes Pop-Art komplexe Problemstellung sich selber auszudenken eine nach Herrschaftsbeziehungen muss nicht zwangsläufig sehr mit dem scheint die Welt C betrachtet haben sind es aber ist nicht zwangsläufig der Fall wobei mir jetzt ganz spontan kein sinnvolles Beispiele für nichtsemitischen Nachbarschaft einfällt also unzählige Beispiele fallen mir natürlich sofort ein aber damit die belästigen Ja ok ja genau wenn sie diese okay vielleicht ist das nur sinnvolles Beispiel es ist auch ein Ort von von der von der Größe und Zahl zu kleineren Zahl gehen also mittels zu verschieben das ist dann keine symmetrischen Nachbarschaft mehr bei der rückwärts nicht verschieben durften mehr gut also dass ist der Algorithmus nur sehr einfache Schleife auf diesem abstrakten Niveau und auf diesem abstrakten Niveau möchte ich gerne denn die Implementation bei Ihnen sehen alles was konkret ist wichtig ausgelagert sehen in Klassen die dort drinnen definierte Interface das implementieren beziehungsweise wenn sie nicht auf oder wählen dann das entsprechende analoge in ihrer Programmiersprache wenn sie eine Programmiersprache haben in ins Auge gefasst haben die so was nicht ist wirklich vernünftig erlaubt sollten Sie noch mal drüber nach den und das jährliche Programmiersprache dann für diese Veranstaltung ist so ja für alle für alle Algorithmen für alle Algorithmen und möchte ich die Implementation auf diesem Abstraktionsniveau sehen ich möchte in dem eigentlichen algerischen Code kein Hinweis darauf sehen ob dies gerade das TSP oder eine einer Problemstellung gelöst wird kein Hinweis darauf mit welcher Nachbarschaftsbeziehungen dass wir das jetzt gemacht wird das soll alles ausgelagert werden wenn man dann mal weg nur geplatzt ist dann ist glaube ich ganz einfach das meine Erfahrung als es noch die Forscher noch Einführung in FOC war und das in der Veranstaltung war mit vielleicht die Aufgabe zu lösen so Kommentare nur dazu müssen sich beeilen nur wie das ist die letzte Folie bitte nochmal ganz kurz Konzentration noch eine Minute wenn man exakte Nachbarschaft haben wo jede Sokal Optimum global das Optimum ist dann kriecht dieses einfache Schema natürlich schon die optimale Lösung denn sie terminiert erst dann das ist die aber bedingt hier die A-Probe dem ist ist gleichbedeutend damit das wir mit der Lösung die wir jetzt setzt konstruiert haben eine ein lokales Optimum haben und wenn die Nachbarschaft exakt ist ist das nach Definition automatisch ein globales Optimum so wenn die Lösungsmenge endlich ist dann wird der Algorithmus nach einer endlichen Anzahl von Iterationen terminieren warum weil er sicher von Schritt zu Schritt verbessert das heißt er kommt nie zweimal dieselbe Lösung er kommt in jeder Iteration an eine immer neue Lösung gebe sei nicht gesehen hat und das man endlich viele Lösungen im endlich großen Lösungsraum geht heißt es nach endlich vielen Schritten ist Schicht ist vielleicht doch so Finito ist das richtige Wort dann danke ich Ihnen und wenn Sie Fragen haben zur Vorlesung oder zu und zu praktischen Aufgabe oder zu Organisationen stellen Sie die gerne im Forum ich werden jetzt wieder angewöhnen regelmäßig Forum zu lesen ich hoffe ich werde dann noch immer vom Forum per Email wie bisher auch benachrichtigt wenn was neues da ist beziehungsweise gerne auch auf anderen Kanälen entweder nach der Veranstaltung hier oder eben per Email oder sonst wie gut und dann bis nächste Woche als Trick ab
Loading...
Feedback
hidden