Introduction - Generel Discussion of Algorithmic Problems
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Serientitel | ||
| Teil | 1 | |
| Anzahl der Teile | 12 | |
| Autor | ||
| Lizenz | CC-Namensnennung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben. | |
| Identifikatoren | 10.5446/21461 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
|
12
00:00
FlächeninhaltGarbentheorieVakuumComputeranimation
02:45
Globale OptimierungEntscheidungstheorieAbzählenFokalpunktFeasibility-StudieLösung <Mathematik>Zusammenhang <Mathematik>MengeOptimierungsproblemProfil <Strömung>VerweildauerGruppenoperationt-TestObjekt <Kategorie>SchätzungStrategisches SpielEntscheidungsproblem
12:25
Feasibility-StudieZielfunktionLokales MinimumGlobale OptimierungMatchingGraphFunktion <Mathematik>MultigraphBillard <Mathematik>t-TestZahlenbereichObjekt <Kategorie>EbeneMengeRichtungZielfunktionKanteMinimumMaximumOptimierungsproblemLösungsraumRandbedingung <Mathematik>Bindung <Stochastik>Reelle ZahlLösung <Mathematik>Natürliche ZahlMatchingBerührung <Mathematik>KnotenmengeKantenmengeMatching-ProblemMathematisches Zeichen
22:06
MatchingGraphFunktion <Mathematik>Feasibility-StudieMultigraphZielfunktionMengenlehreBoolesche AlgebraNebenbedingungPrädikat <Logik>TeilmengeIndexberechnungElement <Gruppentheorie>UnendlichkeitQuadratische GleichungMatrizenrechnungRechenschieberTravelling-salesman-ProblemTeilmengeSummeMengeInzidenzalgebraKanteMathematikNebenbedingungLösungsraumZahlenbereichLösung <Mathematik>VektorrechnungZielfunktionEbeneElement <Mathematik>LinieFunktion <Mathematik>Physikalische GrößeEnde <Graphentheorie>OptimumEckeGerichteter GraphIndexEinfach zusammenhängender RaumVektorPotenzmengeNummerierungPolygonzugUngerichteter GraphKnotenmengeMatchingKantenmengeSummierbarkeitZahlAusdruck <Logik>Matching-ProblemComputeranimation
31:46
Travelling-salesman-ProblemNebenbedingungMatrizenrechnungQuadratische GleichungRechenschieberLokales MinimumModelltheorieTermKnotenmengeMatrizenringPunktNebenbedingungEbeneZerlegung <Mathematik>VektorrechnungLösung <Mathematik>TeilmengeMengeKoordinatenObjekt <Kategorie>MathematikVorzeichen <Mathematik>LinieKanteDurchflussUmkehrung <Mathematik>SummeMatrix <Mathematik>PolygonzugKnotenmengeRichtungQuadratSummandDiagonale <Geometrie>Computeranimation
41:27
NebenbedingungModelltheorieTermKnotenmengeFeasibility-StudieNichtunterscheidbarkeitNormalvektorStetige FunktionZielfunktionKalkülExistenzsatzLokales MinimumHeuristikGlobale OptimierungApproximationSummeKanteZerlegung <Mathematik>OptimierungStreckeMatrizenringMaßstabTeilmengeVerbrennungMengeOptimumMomentenproblemLösung <Mathematik>NebenbedingungComputeranimation
51:07
GarbentheorieVollständigkeitUnendlichkeitPhysikalische TheorieSchwebungApproximationBruchrechnungBeobachtungsstudieMultigraphKnotenmengeGanze ZahlÄquivalenzklasseAdjazenzmatrixGruppendarstellungBinärdatenPunktrechnungModelltheorieVariableOperations ResearchAdditionMultiplikationPaarvergleichZahlentheorieEntscheidungstheorieValiditätPolynomKlasse <Mathematik>Hamilton-OperatorGraphElement <Gruppentheorie>Funktion <Mathematik>Ausdruck <Logik>TheoremMengenlehreClique <Graphentheorie>Überlagerung <Mathematik>KomplementaritätGlobale OptimierungTopologieEuklidischer RaumErweiterungPhysikerGrundraumFaktorisierungPositionMathematikMaßstabMathematische ModellierungOptimumVollständigkeitMengeLaufzeitHeuristikEbenePunktPromilleQuantencomputerSchätzung
01:00:29
Nachbarschaft <Mathematik>GarbentheorieKreisbogenTravelling-salesman-ProblemEuklidischer RaumRechenschieberRelation <Mathematik>GraphLösungsraumMinkowski-MetrikTermGlobale OptimierungKombinatorikExistenzsatzApproximationLokales MinimumFeasibility-StudieIterationMultigraphUnendlichkeitSymmetrische MatrixPunktKnotenmengeFunktion <Mathematik>SchlussregelIterationStrategisches SpielZugbeanspruchungLösung <Mathematik>AggregatzustandNebenbedingungNachbarschaft <Mathematik>DreiecksungleichungLösungsraumKanteEbeneGraphLängeEvolutionsstrategiePolygonzugGruppoidComputeranimationFlussdiagramm
01:07:54
Feasibility-StudiePunktNachbarschaft <Mathematik>Globale OptimierungFunktion <Mathematik>SchlussregelKreisbogenEuklidischer RaumTravelling-salesman-ProblemLokales MinimumIterationGraphMultigraphUnendlichkeitSymmetrische MatrixKnotenmengeRelation <Mathematik>StellenringEbeneKanteLösung <Mathematik>MengePunktMathematikPolygonzugLängeKlasse <Mathematik>Physikalische GrößeLösungsraumÜbergangTeilmengePotenzmengeAbstrakter RaumReelle ZahlZugbeanspruchungModulformZielfunktionComputeranimationFlussdiagramm
01:16:21
KreisbogenTravelling-salesman-ProblemEuklidischer RaumNachbarschaft <Mathematik>Relation <Mathematik>StellenringLokales MinimumFeasibility-StudieIterationLokales MinimumMinimumKettenregelKanteZielfunktionFunktion <Mathematik>OptimumLösung <Mathematik>Konvexe FunktionStellenringMaximumKonstruktion <Mathematik>MathematikMenge
01:24:05
Lokales MinimumFeasibility-StudieNachbarschaft <Mathematik>IterationGroße VereinheitlichungMengeEinfach zusammenhängender RaumOptimumZusammenhang <Mathematik>Klasse <Mathematik>IterationZahlKraftLösungsraumCW-KomplexLösung <Mathematik>LängeStellenringAnalogieschluss
01:31:49
Lokales MinimumNachbarschaft <Mathematik>Smith-DiagrammFeasibility-StudieHill-DifferentialgleichungTermStellenringComputeranimation
01:33:02
Lokales MinimumFluidStellenringComputeranimation
Transkript: Deutsch(automatisch erzeugt)
00:01
präsentiert von Open Learnware, die Plattform für Lernmaterialien an der TU Darmstadt. Gut, nochmal Kontrolle, dass das nicht auf Mute geschaltet. So, ist nicht auf Mute geschaltet.
00:20
Halt, jetzt war es zu... Ich hoffe, das funktioniert weiterhin. Alles sieht soweit gut aus. So, gut, hallo allerseits. Ich möchte Sie zur zweiten Vorlesung begrüßen.
00:43
Ich hatte ja letztes Mal angekündigt, ich werde versuchen, dass das Ganze aufgenommen wird. Also, was konkret aufgenommen wird, ist, wenn alles funktioniert hat, das Kamerabild und der Bildschirm und mein Ton. Deshalb wundern Sie sich nicht, dass ich Netz hat, aber Sie hören nichts über die Lautsprecher.
01:01
Das geht hier in den Empfänger, nicht in die Saaltechnik. Und was ich noch brauche, ist dann jemanden, der mir zeigt, wie man aus diesem Quantasia-Roh-Datenformat dann ein richtiges Video macht. Aber ich denke, das sollte das geringste Problem sein. Gut, wir hatten beim letzten Mal einerseits die wesentlichen organisatorischen Punkte besprochen,
01:24
andererseits aber auch sind wir schon ein bisschen eingestiegen in das Thema. Gibt es von Ihrer Seite aus heute nochmal organisatorische Punkte zu besprechen? Haben Sie alle den Forumsbeitrag von mir gelesen? Wenn nicht, dann schauen Sie bitte da rein bei Gelegenheit.
01:41
Ist nicht eilig, aber schon sehr sinnvoll. Also es gibt ein Forum, 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 ja eigentlich schon beginnen können, dass es gar keinen Grund gibt, da zu warten, bis die Algorithmen da sind.
02:02
So, ich mache einen kleinen Sprung. Ich werde gerade hier am Anfang einige kleinere Abschnitte überspringen. Wenn die Zeit reicht, werde ich wieder zurückkehren dazu später, aber die Wahrscheinlichkeit ist nicht groß, dass die Zeit reichen wird. Das sind Abschnitte, die erstens nicht so wichtig, dafür zweitens aber besonders schwierig zu verstehen sind.
02:26
Das heißt also, ich denke, wir sind uns einig, dass das keine schlechte Idee ist, diese Punkte zu überspringen. Ich will direkt einsteigen jetzt in das Thema Allgemeines zu algorithmischen Problemstellungen. Das hatten wir beim letzten Mal noch nicht angesprochen, nicht?
02:40
Soweit sind wir noch nicht gekommen. Nicht? Nee. Gut. Was haben wir für algorithmische Problemstellungen? Entscheidungsprobleme, Decision Problem, festzustellen, ob es eine Lösung gibt oder nicht ist meistens natürlich nicht so besonders prickelnd zu wissen, dass es eine Lösung gibt.
03:04
Ja, stellen Sie sich eines der Probleme vor, die wir beim letzten Mal behandelt haben, beispielsweise das Problem hier für eine Universität einen Stundenplan für alle Hörsaalbelegungen zu erstellen, wenn der Algorithmus Ihnen sagt, ja, hurra, es gibt eine Lösung. Schön, aber die möchten Sie natürlich gerne in der Hand haben.
03:22
Zuweilen reicht ein Entscheidungsproblem, zuweilen reicht es Ja oder Nein zu wissen, zum Beispiel eben bei Entscheidungsfragen. Ja, soll ich soll ich die und die Finanzinvestition tätigen? Ja oder Nein, da reicht natürlich ein mehr als eine Entscheidung.
03:41
Kann man auch nicht erwarten. Konstruktionsproblem ist das typische. Ja, das ist auch das typische, was Sie in der GDI 2 meistens kennengelernt haben. Denken Sie an das Sortierproblem. Da war die Aufgabe, eine sortierte Reihenfolge der Eingabesequenz zu konstruieren. Oder denken Sie an, wenn Sie das in der GDI 2 hatten, String Matching, also
04:05
das, was Sie kennen, Suchfunktion in einer Datei, ein Wort in einer Datei zu finden. Da war es die Aufgabe, alle Vorkommen. Dieses Suchwort ist in der Datei zu konstruieren. Eine Liste aller Positionen, wo dieses Suchwort in der Datei vorkommt, zu konstruieren und so weiter.
04:26
Wieder weniger wichtig, seltener wichtig ist ein Aufzählungsproblem, nämlich alle Lösungen zu einer Problemstellung zu geben. Und das ist meistens reicht es eigentlich, wenn man eine Lösung hat. Da braucht man nicht alle zu haben.
04:42
Ist aber durchaus in manchen Kontexten sehr sinnvoll. Zum Beispiel denken Sie an Zielprobleme mit mehreren Zielkriterien. Denken Sie beispielsweise aus unserer Praxis, unserer Arbeitsgruppe Fahrplanauskunft bei der Deutschen Bahn.
05:00
Da haben Sie drei Zielkriterien. Die Fahrzeit, also wie schnell Sie von A nach B kommen, der Fahrpreis natürlich und die Bequemlichkeit. Ausgedrückt Anzahl und Verweildauer bei den Umstiegen, vielleicht noch Bequemlichkeit. Die voll besetzte Regionalbahn ist nicht so bequem wie der dünn besetzte ECE oder so etwas.
05:23
Na ja, mindestens drei Kriterien haben Sie. Und natürlich weiß der Fahrkartenautomat nicht, was der Kunde für ein Zielprofil hat. Wie wichtig ihm Fahrzeit, wie wichtig ihm Fahrpreis und wie wichtig ihm die Bequemlichkeit ist.
05:41
Sie können sich so verschiedene Kundenprofile vorstellen. Der Geschäftsmann, die Geschäftsfrau, da ist Zeit Geld, also vor allem wichtig möglichst schnell. Der arme Student, die arme Studentin, da ist Geld alles. Alles andere ist nicht so wichtig. Okay, Zeit ist auch wichtig. Auch Studierende haben heutzutage keine Zeit mehr im Gegensatz zu meiner Zeit.
06:00
Oder die alte Dame mit den zwei schweren Koffer, für die natürlich Bequemlichkeit das wichtigste ist. Möglichst wenig Umstiege und wenn Umstiege dann möglichst irgendwie bequem. Ja, dementsprechend liefert ihn der Fahrkartenautomat nicht eine Lösung, sondern eine ganze Enormation von jeweils nach verschiedenen Profilen halbwegs optimalen Lösungen.
06:21
Deshalb, also Enormationsprobleme mehr als eine Lösung sind durchaus hin und wieder eine sinnvolle Zielsetzung. Insbesondere wenn man nicht weiß, was dann der Endkunde wirklich will, sodass man ihm alternativen Optionen anbieten muss. Und das, worum wir uns hier vor allem beschäftigen werden, sind Optimierungsprobleme.
06:41
So heißt ja auch die Lehrveranstaltung. Ja, wir haben nicht nur einfach eine, wir wollen nicht einfach nur eine Lösung finden, eine zulässige Lösung, sondern wir wollen eine Lösung finden, die nach irgendeinem Kriterium optimal ist. Denken Sie an das Navi beispielsweise.
07:01
Typischerweise ist das die Zeit, was da optimiert wird. Sie wollen einen Weg von A nach B finden im Straßenverkehr, der die Zeit optimiert. Der minimale Zeit nach den nach den geschätzten Zeiten für die einzelnen Streckenabschnitte, die im Navi gespeichert sind drin ist. Also Dijkstra, das Dijkstra Problem beispielsweise wäre ein Optimierungsproblem.
07:25
So, hier nochmal, wie ich eben noch gesagt hatte, Entscheidungsprobleme sind manchmal wichtig. Aufzählungsprobleme, manchmal möchte man mehr als eine Lösung haben, aber meistens will man eine Lösung haben oder eine optimale oder wenigstens.
07:40
Oft genug davon reden wir hier in diesem Semester, oft genug wird man nicht die optimale Lösung haben. Im Gegensatz beispielsweise zum kürzesten Weg, wo Sie in fast Linearzeit mit Dijkstra's Algorithmus eine optimale Lösung bekommen. Wir reden hier über Probleme, wo Sie nicht immer die optimale Lösung in vernünftiger Zeit bekommen können oder es nicht erwarten können, dass Sie die bekommen.
08:07
Also, während wir von Optimierungsproblemen reden, dann meinen wir unter Umständen reicht uns auch eine halbwegs optimale Lösung. Ein Grund, warum Entscheidungsprobleme nicht so wichtig sind, ist, dass sie typischerweise ja tatsächlich auch eine Lösung liefern.
08:26
Ja, wenn Sie das Beispiel von eben hatten, soll ich die und die Finanzanlage, soll ich in Aktien investieren oder nicht? Dann wird der Algorithmus, ich fabuliere jetzt mal, um festzustellen, ob es sinnvoll ist,
08:43
in Aktien zu investieren oder nicht, wird er versuchen, eine Aktienstrategie zu entwickeln und zu entscheiden, eine möglichst gute Aktienstrategie sogar, um zu entscheiden, ob sich das lohnt oder nicht. Und dann kann er den einen Schritt noch weiter tun und diese Aktienstrategie Ihnen auch sagen.
09:01
Dieser Zusammenhang hier ist trivial, aber manchmal durchaus von Bedeutung. Konstruktionsprobleme, dass Sie irgendeine Lösung haben wollen, können Sie natürlich immer trivial als ein Optimierungsproblem ansehen, indem Sie jede einzelne Lösung denselben Kriteriumswert, denselben Zielwert geben. Objective hatten wir, glaube ich, beim letzten Mal schon Zielwert, Zielfunktionswert, Zielsetzung und
09:26
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 ein Optimierungsalgorithmus hernehmen und den dann auf ein Konstruktionsproblem anwenden.
09:40
Wenn Sie schon einen schönen Algorithmus haben und der schön implementiert ist, vielleicht schön getunt ist und Sie wollen gar nicht jetzt optimieren, sondern Sie wollen irgendeine Lösung herausbekommen, naja, dann dann stecken Sie Ihre Problemstellung da trotzdem rein und geben jeder einzelnen möglichen Lösung den Zielfunktionswert eins.
10:03
So, wir betrachten also Optimierungsprobleme. So heißt auch die Lehrveranstaltung, das ist auch der Grund, warum die Lehrveranstaltung so heißt. Es sind nicht Algorithmen allgemein, sondern und nicht Probleme allgemein, sondern Optimierungsalgorithmen und Optimierungsprobleme, weil sich alles darauf reduzieren lässt.
10:21
So wir müssen uns sprachlich hier ein bisschen verständigen. Wir werden immer wieder nach dem selben Schema über Probleme reden. Erst einmal ist entscheidend wichtig. Daran kämpfe ich in jedem Sommersemester bei den Studierenden algorithmischen Modellierung. Genau zu unterscheiden zwischen was ist das Problem und was ist die Lösung.
10:45
Das begegnet mir auch immer wieder, auch wenn ich mit Leuten aus der Wirtschaft oder Industrie zusammen arbeite, dass man, wenn man versucht, das Problem zu beschreiben, schon in Gedanken irgendeine algorithmische Vorgehensweise hat und sich von dieser Vorgehensweise, die man irgendwo im Hinterkopf hat, schon beeinflussen lässt, wie man das Problem beschreibt.
11:07
Das ist natürlich problematisch, weil man damit praktisch geframt ist, schon wenn man, wenn man über die Problemstellung spricht, sich praktisch schon selber bei den algorithmischen Möglichkeiten einschränkt.
11:23
So was, woraus besteht ein Optimierungsproblem aus der Menge der zulässigen Eingaben? Denken Sie an das Problem hier an der Universität, die die Lehrveranstaltung in Hörsäle und in Zeitslots zu packen, dann ist jeder zulässige Input eben gegeben
11:43
durch eine Menge von Hörsälen mit ihren Ausstattungsmerkmalen, Anzahl Sitze, vielleicht noch technische Ausstattung. Dann ist natürlich gegeben die Menge der Lehrveranstaltungen mit den Anforderungen des Dozenten jeweils, was die technische Ausstattung ist und mit der Schätzung, wie viele Sitzplätze gebraucht werden
12:01
und natürlich die Zeitslots, die ja an der TU Darmstadt, der besonders interessant gestaltet sind. Die sind, das wären die zulässigen Inputs, jeder, jeder, jedes Trippel aus drei Mengen solchen Hörsälen, solchen Lehrveranstaltungen und solchen Zeitslots wäre ein zulässiger Input.
12:25
Vielleicht, eigentlich ist es noch ein bisschen komplizierter, man müsste noch ein bisschen mehr als Input dazu nehmen, man müsste zum Beispiel Informationen dazu nehmen, dass die Hörsäle sich verteilen auf zwei Campus, einmal Innenstadt, einmal Lichtwiese und
12:42
dass man nicht in fünf Minuten vom einen zum anderen kommt, sodass es da wieder Einschränkungen gibt und so weiter. So der Feasible Outputs, feasible sollte ich noch dazu sagen, allgemein feasible heißt im englischen wörtlich durchführbar, hat sich etabliert im Bereich Algorithmik, das als zulässig zu übersetzen.
13:05
Die zulässigen Inputs, also das, was der Algorithmus verarbeiten soll, womit alles fertig werden soll, die zulässigen Outputs, das, was der Algorithmus liefern soll. Was ist ein, bleiben wir wieder bei diesem Universitätsplanungsproblem, was wäre ein zulässiger Output
13:22
für einen gegebenen Input, achso vielleicht noch ein Wort dazu, Instance ist, das hat verschiedene Bedeutungen im Englischen, heißt unter anderem auch dasselbe wie Input im Bereich Algorithmik. Manchmal redet man auch im Deutschen dann von Instance.
13:43
Was wäre ein zulässiger Output? Das zulässige Output wäre für jeden einzelne Lehrveranstaltung oder genau gesagt für jeden einzelnen Termin einer Lehrveranstaltung, GDI 1 beispielsweise hat zwei Termine, für jeden einzelnen Termin eine Zuweisung, welcher Raum, welcher Zeit-Slot, welcher wöchentlicher Zeit-Slot, das muss, das ganze feasible, dass das ganze
14:04
durchführbar zulässig ist, muss es die entsprechenden Rahmenbedingungen einhalten, es muss natürlich einhalten, dass keine zwei Lehrveranstaltungen zum selben Zeit im selben Hörsaal eingeplant sind, selbstverständlich, es muss einplanen, dass die Dozenten und auch die Studierenden,
14:22
wäre natürlich schön, wenn das so wäre, wenn das eingeplant wäre, dass die eine Chance haben, von einem Hörsaal zum anderen zu kommen, ohne in der einen Vorlesung frühzeitig rauszugehen oder anderen zu spät zu kommen und so weiter. Objective, das ist da in diesem Beispiel durchaus eine Frage, was wäre die Zielsetzung, das diskutieren wir in
14:46
der algorithmischen Modellierung durch und modellieren das dann auch, Zielsetzung könnte beispielsweise sein, Dozenten können angeben, welche Termine passen ihnen gut, welche Termine ist okay, welche Termine passen ihnen nicht so gut und welche Termine gehen gar nicht.
15:04
Und nach diesen, diese Präferenzen summiert über alle Professoren, über alle Dozenten hinweg zu optimieren, das könnte ein Optimierungsziel sein, was man hier betrachtet, das muss der Kunde und der Softwareentwickler miteinander aushandeln.
15:21
Anderes Optimierungsziel, vielleicht etwas studentenfreundlicher, könnte beispielsweise sein, dass nach Möglichkeit der Stundenplan, jedes Studierenden so gepackt ist, dass auch die Leute, die aus dem Odenwald oder aus dem Westerwald oder so kommen und möglichst nicht jeden Tag anreisen wollen, dass auf die Rücksicht genommen wird oder ähnliche Sachen.
15:44
Also Sie sehen die Zielsetzung, wenn man wirklich über konkrete Problemstellungen aus der Industrie, aus der Wirtschaft, aus der Verwaltung redet, ist es meistens nicht so problematisch zu spezifizieren, was sind die Randbedingungen, die unbedingt unter allen Umständen einzuhalten sind,
16:03
aber es ist häufig durchaus eine Sache der Diskussion zu spezifizieren, was eigentlich die Zielsetzung ist, die man optimieren möchte. So, jetzt wird es ein bisschen formaler, aber wir führen eigentlich nur ein bisschen mathematische Notation ein für das, was
16:22
wir eben auf der letzten Folie gesagt haben, wir haben so ein kaligraphisches I für alle potenziellen Inputs, die Menge aller potenziellen Inputs, wir reden von einer mathematischen Menge hier, für jeden Input haben wir eine Menge von zulässigen Lösungen. Natürlich hat der eine Input andere zulässige Lösungen als der andere Input und auf dieser Menge für eine
16:49
gegebene Instanz, für einen gegebenen Input, deshalb ist die Zielfunktion indiziert mit dem Input, haben wir eine Funktion, die die Menge der zulässigen Lösungen abbildet in die reellen Zahlen, meistens sicherlich in die nicht negativen reellen Zahlen.
17:09
Vielleicht sogar in die natürlichen Zahlen, aber auf jeden Fall immer in die reellen Zahlen. Und wir haben eine Richtung, entweder wir wollen minimieren oder wir wollen maximieren, entweder wollen wir Profite maximieren oder wir wollen Kosten minimieren, das ist immer dasselbe
17:22
oder müssen nicht Kosten im Sinne von Euro sein, können auch unbequemlichen Seiten sein, die wir minimieren wollen und so weiter. So, was ist die Aufgabe? Was ist die algorithmische Aufgabe? Das ist die Aufgabe, die an den Algorithmus gestellt wird. Ein Algorithmus löst dieses Optimierungsproblem, das ich jetzt hier ganz generisch abstrakt spezifiziert habe.
17:47
Wenn es das Leist, diese Aufgabe löst, diese Task, zunächst einmal zu bestimmen, ob der Lösungsraum nicht leer ist. Denken Sie wieder an das Beispiel mit der Vorlesungsbelegung. Es kann sein, dass die Randbedingungen dafür sorgen, dass es keine Lösung gibt, dass der Lösungsraum F von I und die leere Menge ist.
18:13
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 irgendeine zulässige Lösung daraus konstruieren, sondern wir wollen eine konstruieren,
18:26
die diese Zielfunktion, je nachdem, wie die Richtung ist, entweder minimieren oder maximieren. Das heißt also, wir wollen ein X finden, sodass der Zielfunktionswert von X das Minimum ist, genommen über alle möglichen Zielfunktionswerte in der Lösungsmenge oder das Maximum, genommen über alle möglichen Zielfunktionswerte.
18:49
Ich beschreibe das so abstrakt, generisch, weil, das hatte ich beim letzten Mal ja auch schon angekündigt, das ist die Ebene, die wir sinnvollerweise einnehmen werden, um auch über solche generischen Algorithmen zu sprechen,
19:02
über Algorithmen, die eben nicht für eine spezifische Problemstellung konstruiert sind, wie für Sortierproblemen, sondern für eine ganze Bandbreite von Optimierungsproblemen. Da muss man natürlich eine gewisse abstrakte Ebene einnehmen, aber selbstverständlich gehen wir immer wieder auch auf die Ebene konkreter Beispiele zurück, um zu sehen, was das jetzt umgesetzt im Konkreten bedeutet.
19:25
So, fangen wir schon mal damit an. Matching. Haben Sie das Matching-Problem mal gesehen? Darunter verstehen wir auch verschiedene Sachen. In der Algorithmik versteht man darunter folgendes, ich hoffe, dass die Kamera das Bild gut sieht. Sie haben einen
19:43
ungerichteten Grafen, irgendwie sowas, vielleicht ein bisschen größer, den male ich mal jetzt zusammenhängt, der muss aber nicht zusammenhängt sein.
20:01
So. Und Sie wollen jetzt eine gewissen, haben wir farbige Kreide? Nee. Was Sie suchen, ist eine Kantenmenge. Eine Kantenmenge, die die Eigenschaft hat, dass keine zwei Kanten sich an einem gemeinsamen Endknoten berühren.
20:24
Wenn ich die Kanten zum Beispiel in die Kantenmenge hineinehme, darf ich die vier nicht mehr nehmen, sondern ich kann zum Beispiel die hier noch nehmen. Jetzt muss ich schauen, welche ich noch nehmen kann. Ich kann zum Beispiel die hier nehmen und ich kann
20:41
jetzt mindestens noch die hier nehmen und ich glaube, jetzt kann ich keine mehr hinzunehmen, ohne diese Eigenschaft zu verletzen. Die vier Kanten habe ich jetzt so spontan ad hoc gefunden, die die Eigenschaft haben, dass sie sich gegenseitig nicht in einem gemeinsamen Endknoten berühren.
21:07
Das Ganze, die Relevanz des Ganzen wird vielleicht ersichtlicher, wenn ich zu einem Spezialfall übergehe, zu Bipartitengrafen, dass sämtliche Kanten, dass die Knotenmenge aus zwei Teilen besteht, die ich links und rechts anordnen kann und die Kantenmenge und
21:27
alle Kanten gehen zwischen den Knoten hin und her, die links und 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.
21:47
Ich nehme mal den hier her, ordne die beiden zu, dann kann ich die hier zuordnen, dann kann ich die hier zuordnen und dann kann ich noch zum Beispiel die hier zuordnen.
22:02
Hier ist offensichtlich, dass das Matching maximal ist, weil alle auf der rechten Seite sind gematcht, besser geht es ja gar nicht. Hier weiß ich nicht genau, ob das wirklich maximal ist, ob das wirklich die maximale Anzahl von Kanten ist. Ich bin ja einfach mal irgendwie so spontan von oben nach unten und hinten rum rechts
22:22
lang durchgegangen und wer weiß, ob das die richtige Strategie war, ob jetzt ein Optimum zu finden. Vielleicht gibt es ja auch ein Matching mit fünf Kanten, kann sein, habe ich mir jetzt keine Gedanken dazu gemacht. Das ist ein Matching, das heißt der Input ist ein ungerichteter Graph, so bezeichnen wir ja immer
22:42
Graphen, das haben Sie sicherlich schon in der GDI 2 oder anderswo gesehen, bestehend aus einer Knotenmenge. V, V wie Vertex ist einer der beiden Worte, die typischerweise für Knoten im Graphen verwendet werden, das andere Wort ist Node, Knoten. Und E Edge Kante, so was ist, das ist ein Input, also vor allem
23:03
das was Sie links sehen, das ist rechts natürlich auch ein spezieller Fall eines Inputs. Was ist zu einem gegebenen Input ein zulässiger Output, eine Teilmenge der Kantenmenge, ebenso wie ich sie dick gemalt habe, sodass keine zwei Kanten darin einen incidenten Knoten gemeinsam haben,
23:24
sich nicht an einem gemeinsamen Endknoten berühren und die Zielsetzung ist die Kardinalität der ausgewählten Kantenmenge zu maximieren. Ob mir das links gelungen ist, wie gesagt, weiß ich nicht, spielt jetzt auch keine Rolle. Wir werden in Kürze sehen, wie wir beispielsweise hier bei Matching zu einem optimalen Ergebnis kommen können, sogar in sehr effizienter Zeit.
23:48
So, also das nochmal so formuliert, wie wir es auf der Folie hatten. Die Instanzen, die Inputs aus der kalligraphischen Menge I sind die ungerichteten Graphen.
24:02
Die Lösungsmenge zu einem gegebenen Input G ist die Menge aller Matchings in diesem Graphen. Ja, also das hier ist eine, natürlich nur eine zulässige Lösung. Sie können sich leicht auch eine zweite, eine dritte, eine vierte zulässige Lösung dazu basteln.
24:22
Die leere Menge übrigens ist auch nach Definition eine zulässige Lösung, wenn auch nicht gerade eine mit besonders hoher Kardinalität. Und die Zielfunktion sagt einfach aus, wie viele Kanten im Matching drin sind.
24:42
Das normal ist es, das müssen wir auch nochmal kurz hier anhand dieses Beispiels erläutern, weil wir darauf immer wieder auch zurückkehren werden. Und weil es auch, wenn Sie mal später etwas weiter mit dem Thematik zu tun haben werden, wird Ihnen das auch wieder begegnen.
25:01
Wie spezifiziert man typischerweise eine zulässige Lösung? Man spezifiziert sie, können wir beim Matching hier unten gucken, man spezifiziert sie durch eine Grundmenge. Nämlich, was ist die Grundmenge hier?
25:21
Die Menge aller möglichen Teilmengen der Kantenmenge. Das ist die Grundmenge und durch Nebenbedingungen sagen wir, welche Elemente dieser Grundmenge tatsächlich Matching sind, welche wir als zulässige Lösung akzeptieren. Was ist die Grundmenge? The power set, also die Potenzmenge, Sie kennen aus der Mathematik die Potenzmenge.
25:43
Das ist die Menge einer Teilmenge, in diesem Fall die Menge aller Teilmengen der Kantenmenge. Das ist die Grundmenge und die Nebenbedingungen, die Nebenbedingungen sind, dass eine Teilmenge M nur dann ein Matching ist,
26:04
wenn für alle Elemente aus diesem Matching, Sie sehen hier, Sie haben eine Kante, die V1 mit V2 verbindet und eine Kante W1 mit W2 verbindet. Sie nehmen sich zwei Kanten her aus dem Matching, egal welche, und Sie fordern, die Nebenbedingung ist, dass diese Knoten alle unterschiedlich sind.
26:28
Dass keiner Endknoten der eine der Kante, Endknoten auch der anderen Kante ist, das steht hier mit diesen vier Ungleichheitsbedingungen. Alles nochmal genauer aufformuliert, ein Input, Entschuldigung ein Output, ist gegeben durch eine Grundmenge und durch Nebenbedingungen,
26:49
die sagen, welche Elemente dieser Grundmenge sind tatsächlich zulässige Lösungen. Nochmal ganz kurz, was haben wir hier gemacht? Wir haben ein Prädikat eingeführt, das hier ist ja nichts anderes als ein Prädikat,
27:02
das hier ist eine Bullshit-Funktion, die sagt auf der Grundmenge, die sagt, 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 Matching-Problem auch noch mal formaler spezifizieren, nämlich,
27:28
dass wir sagen, und dann machen wir auch Schluss damit, keine Sorge, nämlich, dass wir sagen, wir reden gar nicht von Element, von Mengen und von Elementen, das ist für die Behandlung im Computer unpraktisch, von solchen, von Mengen zu sprechen, von solchen anschaulichen Gebilden.
27:50
Worüber wir im Computer immer reden, sind letztendlich Zahlen, wir müssen also alles, was wir auf dem Computer lösen wollen, in Zahlen ausdrücken. Und was wir hier machen, ist, dass wir nicht von Matchings reden, sondern
28:03
wir reden von 01-Vektoren auf der Kantenmenge, die besagt, X für eine Kante, also Sie können sich die Kantenmenge indiziert vorstellen, Kante 1, Kante 2, Kante 3, dann haben Sie, oder meinetwegen auch Kante 0, Kante 1, Kante 2, dann haben Sie hier also bei X von E einen ganzzahligen Index, wie ganz normal,
28:27
wie ganz normal bei Arrays, und die Semantik ist, diese Kante, das X auf einer Kante ist gleich 1, genau dann, wenn diese Kante Matching ist, gesucht ist also ein X, gesucht ist nicht mehr eine Menge, sondern gesucht
28:43
ist ein Vektor X, ein 01-Vektor, dessen Komponenten indiziert sind mit den Kanten, durch irgendeine Indizierung der Kanten, durch irgendeine Nummerierung der Kanten, und die Nebenbedingungen lässt sich jetzt schön elegant ausdrücken,
29:00
nämlich, die alle Kanten, die zu einem gegebenen Knoten, ich betrachte hier in der SOSOMA alle Kanten, die zu einem gegebenen Knoten indiziert sind, kennen Sie diese Art und Weise mit Summenzeichen umzugehen? Meistens haben Sie ja in der Mathematik Summen so gesehen, so was wie I gleich 1 bis N,
29:32
das sollte Ihnen vertraut sein. Das kann man natürlich auch so schreiben, man kann sich überlegen, dass hier über die Elemente einer Menge summiert ist,
29:41
und das könnte man, wenn man unbedingt will, auch so schreiben, dass man die Menge dahinter schreibt, und diese zweite Formulierung, die erst mal ein bisschen komisch und unnötig kompliziert aussieht, die lässt sich verallgemeinern zu einer Summe von irgendeinem X, irgendeiner Art
30:02
muss keine Zahl sein, aus irgendeiner Menge muss keine Menge von Zahlen sein, schon gar nicht in der Wahl 1 bis N. Das ist Ihnen hoffentlich so weit vertraut, oder wenn nicht, ist es Ihnen ab jetzt vertraut. So, wir summieren also über alle Kanten auf, die Inzident zu dem Knoten V ist, die den V als N-Knoten haben, das nehmen wir die X auf,
30:25
wir erinnern uns, die Semantik ist, dass dieser Wert 1 ist, wenn diese Kante zum Matching gehört, und die Forderung, dass dieser Knoten nur zu einer einzigen, maximal einer Matching Kante gehören darf, übersetzt sich jetzt schön einfach in die lineare Bedingung, dass diese Summe der 1, die hier rechts steht, kleine gleich 1 ist,
30:51
sprich, maximal einer dieser X-Werte ist 1, alle anderen müssen 0 sein. So, jetzt haben wir es aber so weit. Ok, es sieht wieder kompliziert aus, keine Sorge,
31:03
also wir sind jetzt vom Matching weg. Sie haben dann sich an das TSP, nochmal zur Erinnerung, wie das Ganze aussieht. Sie haben in der anschaulichen Form Punkte in der Ebene oder im
31:23
Raum oder auf irgendeiner Oberfläche, und Sie wollen einen möglichst kurzen Streckenzug durch diese Punkte legen, sodass jeder Punkt genau einmal berührt ist. Wir haben das jetzt mal durchdiskutiert, dass das konkrete Anwendungen in der Fertigungstechnik an allen Ecken und Enden
31:42
hat. Stellen Sie sich vor, ein Roboter, der Schweißpunkt auf einer Karosserie abfährt, um da Schweißarbeiten zu tun, der 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.
32:06
So, aber wir haben auch gesagt, das ist nur die anschauliche Variante. Ganz allgemein, wenn wir jetzt von der Ebene oder von der Karosserie abstrahieren und den allgemeinsten Fall die Essenz rausholen, dann reden wir nicht mehr von Punkten in der Ebene oder sonst irgendwo,
32:27
wir reden von irgendwelchen Objekten, die nicht mehr benannt sind, die einfach nur gegeben sind als Indizes 1 bis N. Objekt 1 bis Objekt N. Es ist uns vollkommen egal, was das ist, ob das Punkte in der Ebene sind oder Gott weiß was.
32:44
Und was wir wirklich als Input haben dann, ist eben auch keine Punkte mit ihren euklidischen Koordinaten in 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
33:01
oder wie lang der Weg ist, um von dem einen Punkt zum nächsten zu kommen. Das ist das in Essenz, was notwendig ist, um das TSP zu lösen. So, was ist jetzt der Output? Der Output ist wieder eine quadratische Matrix.
33:24
Also der Input ist eine quadratische Matrix. Wir haben N Objekte, so zyklisch zu verbinden. Der Input ist eine quadratische Distanz Matrix. Der Output ist eine quadratische 0, 1 Matrix mit der Semantik. Wir haben eine 1 gesetzt, einem Eintrag i, j, wenn der Weg von i nach j Teil dieser Rundtour ist.
33:46
Oder anders formuliert, wenn zyklisch j unmittelbar auf i folgt. Dann können wir die Zielsetzung schon mal sofort und einfach hinschreiben. Nämlich das hier. Das sind die Distanzen.
34:03
Das sind die Einträge, die sagen, welche unmittelbaren Verbindungen von welchen i nach welchen j jeweils tatsächlich in der Rundtour drin sind. Und wir summieren das hier mit dieser Doppelsumme über alle Felder, über alle Einträge der beiden Matrizen auf.
34:21
Was steht hier? Wenn Sie sich einen einzelnen Summanden hier rechts ansehen, wenn Sie sich einen einzelnen Summanden rechts ansehen, dann ist der entweder 0, wenn das x0 ist. Oder wenn das x1 ist, hat der einzelne Summand den Wert dij. Das heißt, die Summe summiert alle dij auf, für die xj1 ist.
34:47
Nach unserer Semantik summiert es also alle dij auf alle Distanzen für die Wege, die tatsächlich in der Rundtour drin sind.
35:00
Und genau das ist es, was wir wollen. Jetzt, damit haben wir schon mal die Zielsetzung formuliert. Wir sind immer noch nicht dabei, wir kommen heute zu den Algorithmen, keine Sorge. Wir machen noch ein bisschen vorher Trockenübungen mit algorithmischen Problemstellungen.
35:27
Die Nebenbedingungen, die Grundmenge ist die Menge aller 01 Vektoren x. Die Nebenbedingungen, die jetzt sagen, unter welchen Umständen eine solche 01 Matrix um genau zu sein,
35:43
tatsächlich eine zulässige Lösung sind, das sind die Nebenbedingungen, die sagen, dieses x ist tatsächlich eine Rundtour. Dann fangen wir mal an. Eine Nebenbedingung ist sicherlich, kein Objekt folgt auf sich selbst. Also die x auf der Diagonale müssen alle 0 sein.
36:03
Zweite Nebenbedingung für jedes i, diese Schreibweise mit dem Vorortzeichen ist Ihnen doch auch vertraut aus der Mathematik nehme ich an. Zweite Bedingung ist, was macht so einen geschlossenen Streckenzug aus? Es geht, wir denken uns den natürlich orientiert.
36:22
Ist vollkommen egal in welcher Orientierung, hier in der Ebene. Im Allgemeinen ist es nicht egal, denn wir haben das ja so weit abstrahiert, dass die eine Richtung und die andere nicht unbedingt gleich lang sein müssen. Was auch realistisch ist, denken Sie, Sie müssen durch den realen Straßenverkehr durch.
36:42
Zum Beispiel, Sie haben zwei Punkte in Darmstadt. Sie wissen, es gibt eine Menge Einbahnstraßen in Darmstadt. Die Distanz, sagen wir mal zum Beispiel, Sie wissen auch diese ganzen Umgehungen, die Unterführung und so weiter. Die Distanz in der Einrichtung, wo Sie die Unterführung nehmen müssen,
37:03
von beispielsweise Rheinstraße zum Carolinenplatz und umgekehrt vom Carolinenplatz zu Rheinstraße, sind unterschiedlich. In einem einen Fall müssen Sie Unterführung nehmen, in einem anderen Fall kommen Sie direkt durch. Ich hoffe, ich habe mich jetzt nicht geoutet, als der Geografie in Darmstadt unkundiger.
37:20
Aber so habe ich das irgendwie in Erinnerung von meinen wenigen Autofahrten hier in Darmstadt. Also die Orientierung ist allgemein wichtig. So, das hilft uns aber auch, diese Orientierung, nämlich zu sagen, es geht genau eine Kante raus und genau eine Kante rein. Das ist essentiell für einen solchen geschlossenen Streckenzug. Das können wir wieder gut formulieren.
37:41
Eine Nebenbedingung ist, für jeden Knoten ist die Anzahl der rausgehenden Kanten gleich 1. Das heißt, die Summe der Xe der rausgehenden Kanten ist gleich 1. Eben ein Wert ist 1, alle anderen sind 0. Und das kann ich einfach wieder durch aufsummieren hier. Genau dasselbe für die rausgehenden Kanten.
38:06
Das sind die Nebenbedingungen. Oder? Wir haben jetzt gesagt, kein Knoten folgt auf sich selbst und für jeden einzelnen Knoten gibt es genau eine reingehende und genau eine rausgehende.
38:21
Ist damit die Menge der zulässigen Lösungen, wie ich sie Ihnen hier dargestellt habe, beschrieben? Okay, Sie brauchen die Bedingungen, dass wir wieder am Anfang rauskommen. Aber wir müssen doch am Anfang rauskommen, weil ja auch der Anfang, wenn hier zum Beispiel der Anfang ist,
38:41
auch beim Anfang geht ja eine Kante rein. Also das ist noch nicht das Problem, aber das ist ein Problem. So, die Damen und Herren Zuhörer der Aufnahme können sich jetzt einen Kaffee holen gehen,
39:01
aber sich bereilen. Genau, es könnte zum Beispiel so etwas entstehen, um das Beispiel möglichst nachzuempfinden. So, dass es hier im wahrsten Wort einen Kurzschluss gibt
39:26
und hier, wie sieht das aus? So, dass es so aussieht. Ist sogar sehr wahrscheinlich, dass das eine optimale Lösung ist. Nach den Nebenbedingungen, wie wir sie jetzt formuliert haben, so aussieht wie rechts und nicht so aussieht wie links.
39:43
Aber was wir haben wollen ist das, was links steht und nicht das, was rechts ist. Also brauchen wir noch weitere Nebenbedingungen. Ich hatte zwar gesagt, es ist meist recht einfach, die Nebenbedingungen zu formulieren im Verhältnis zu Z-Funktionen, aber es ist auch nicht allzu schwer, da noch irgendwas zu vergessen.
40:02
Das ist eine Möglichkeit, diese Nebenbedingungen zu formulieren. Ich will es Ihnen kurz an der Tafel skizzieren, was diese Nebenbedingungen besagt. Wenn Sie so eine Zerlegung haben in zwei Subzyklen, dann können Sie zum Beispiel eine Linie durchziehen.
40:24
Diese Intuition ist natürlich nur für diesen Fall in der Ebene geeignet, aber das, was ich Ihnen hier intuitiv sage, lässt sich natürlich auch genauso gut abstrakt übertragen auf den allgemeinen Fall. Sie haben hier die Menge S, Teilmenge von Knoten, und hier haben Sie S quer.
40:45
S hat vier Knoten, S quer hat auch vier Knoten. So, und die Bedingungen, die dort sagen, ist, für jede Zerlegung der Knotenmenge in zwei nicht leere Teilmenge S und S quer, muss mindestens eine Kante gehen von S nach S quer.
41:05
Das sagen diese Bedingungen hier, die auf den ersten Blick so brutal aussehen. So, was steht hier? Für jede Teilmenge S, die nicht die ganze Menge ist, hier sehen Sie ganz klein ein Durchgestrichen beim kleiner Gleich,
41:20
also echt kleinere Teilmenge von 1 bis N. S soll aber auch nicht leer sein, das heißt eine echte Zerlegung in zwei nicht leere Teilmengen. Für jede solche Zerlegung soll gelten, es gibt mindestens eine Kante größer gleich 1, die Summe der Kantenwerte ist größer gleich 1, es gibt mindestens eine Kante ij,
41:43
sodass i in S liegt und j in S quer, die also von einem Knoten in S zu einem Knoten nach S quer geht. Und wenn Sie das noch zusätzlich einfügen, wenn Sie sich das noch mal im Moment überlegen,
42:01
werden Sie mir sicherlich zustimmen, dass damit das Problem vollständig beschrieben ist. Dass Sie damit tatsächlich spezifiziert haben, die Menge aller zulässigen Lösungen sind genau das, was wir haben wollen, diese Rundtouren. Ich will da nicht weiter reingehen, das ist natürlich noch gruselig, was hier steht, nicht nur, weil es so komisch aussieht, so gruselig aussieht, sondern es ist vor allem deshalb gruselig, weil Sie hier eine exponentielle Anzahl von Nebenbedingungen haben.
42:26
Ja, exponentiell, Sie wissen, was das heißt. 2 hoch 10 ist schon 1000, 2 hoch 20 ist eine Million, 2 hoch 30 ist eine Milliarde und so weiter ist äußert unschön. Sie haben noch eine Frage.
42:47
Ich bin mir nicht sicher, wenn Sie was machen. Sie haben jetzt diese beiden Teile, diese Subzyklen. Wenn Sie jetzt einfach so was machen. Das wiederum widerspricht dann den Nebenbedingungen, die wir auf der letzten Folie hatten,
43:05
dass genau eine Kante rein und genau eine Kante rausgeht. Ja, aber es widerspricht diesen Nebenbedingungen. Es kann kürzer sein, aber es ist keine zulässige Lösung.
43:22
Sie meinen, ob man das akzeptieren soll. Ach so, ja, also Folgendes ist vielleicht ein interessanter Punkt. Ich glaube, ich habe ein Gefühl dafür, worauf Sie hinaus wollen.
43:41
Denken wir an Straßenverkehr. Da haben Sie vielleicht den Hauptbahnhof, nicht Hauptbahnhof ist ein schlechtes Beispiel, den Karolinplatz als einen der Punkte, den Sie anfahren wollen. Aber natürlich kommen Sie trotzdem am Karolinplatz vorbei. Ja, Sie haben in Ihrer Rundtour eine Strecke von Lichtwiese zum Hauptbahnhof
44:01
und kommen da vermutlich am Karolinplatz vorbei. Sie haben eine Strecke von Erheiligen nach Eberstadt und kommen vermutlich am Karolinplatz vorbei. Nein, da wahrscheinlich nicht, aber Sie verstehen, was ich meine. Ja, natürlich kommt man physisch dann an diesem Punkt vorbei.
44:20
Aber was man machen würde, ist, dass man dann, beispielsweise man hat in der Distanzmatrix eine Distanz von, was hatten wir jetzt als Beispiel, von Lichtwiese nach Hauptbahnhof. Da haben wir einen Distanzwert, den wir vorher berechnet und abgelegt haben. Und dass wir physisch am Karolinplatz nochmal vorbeikommen,
44:45
spielt dann gar keine Rolle mehr. Kann natürlich im Einzelfall tatsächlich zu einer Verbesserung führen, wenn wir sozusagen die Information noch drin haben,
45:01
dass wir physisch dabei vorbeikommen, dass wir deshalb Karolinplatz rausschmeißen können, falls so eine Verbindung drin ist. Dann wäre das eine Variation des handlungsreisenden Problems. Die Algorithmen, die wir betrachten, haben den schönen Vorteil, dass sie eben nicht nur auf eine Problemstellung spezifiziert sind, sondern auch mit Variationen klarkommen.
45:21
Ja, wir hätten dann eine Variation des Problems, wo man sich nochmal genau überlegen müsste, für die speziellen Situationen, wo wir sind. Was genau ist diese Variation? Ja, ich hatte es angedeutet, wenn ich sie richtig verstanden habe, ist die Variation, die Sie im Kopf haben, die, wenn Karolinplatz ein Punkt ist, den man anläuft,
45:44
und andere Verbindungen gehen über den Karolinplatz, dann sollte zum Teil zum Input dazugehören, zu der Kante nicht nur die Information, wie lang ist die Kante, sondern auch die Information, dass sie am Karolinplatz vorbeigeht. Das ist, glaube ich, die Variation, die Sie im Hinterkopf hatten.
46:03
Was das TSP angeht, ich habe mich mal länger mit jemandem anders darüber unterhalten, der intensiver dran arbeitet, wir waren uns beide einig, wir haben schon unglaublich viele TSPs in der Industrie und Wirtschaft gesehen, aber noch nie so reinrassig, wie man es hier natürlich aufbereitet darstellt. Es sind immer irgendwelche kleinen Verkomplizierungen dabei,
46:22
sodass die Problemstellung ein bisschen anders aussieht als in der Vorlesung. Es gibt auch irgendwelche Zusatzbedingungen oder Zusatzinformationen. Aber genau deshalb machen wir die Optimierungsalgorithmen-Vorlesung, um Algorithmen kennenzulernen, die mit solchen kleinen Varianten umgehen. Denn wenn Sie zum Beispiel Sortierungsprobleme anschauen, so wie Sie eine kleine Variation daraus machen,
46:44
dass Sie zum Beispiel sagen, es soll zwar möglichst weit sortiert werden, aber zum Beispiel die beiden dürfen, auch wenn sie so rum sind, dürfen sie trotzdem nicht so rum sein, sondern müssen so rum bleiben oder so etwas, wenn Sie so eine kleine Variation einführen, haben Sie sofort verloren. Sie können keinen Sortieralgorithmus mehr darauf anpassen, auf solche Variationen.
47:05
Also ich wüsste jetzt jedenfalls nicht, wie man das machen sollte. Oder es würde auch sehr schwierig werden. So, noch ein paar kleine, soll man diese? Nee, ich denke wir sollen jetzt langsam mal zu den Algorithmen übergehen.
47:22
Also ich werde ein paar Dinge hier überspringen. Ich werde aber natürlich auch hinterher angeben, welche vorhin ich übersprungen habe, damit Sie das bei der Vorbereitung auf die Prüfung natürlich auch genau wissen. Das ist jetzt wichtig. Jetzt kommen wir langsam zu den Algorithmen.
47:40
Wir nennen einen Algorithmus exakt in der Konstruktionsversion, Zulässigkeitsversion, wenn es beweisbar, das ist der entscheidende Punkt, wenn der Algorithmus beweisbar eine zulässige Lösung findet, vorausgesetzt, es gibt eine. Sonst darf man natürlich sagen, es gibt keine Lösung. Eine Konstruktionsversion, wenn er beweisbar eine optimale Lösung findet.
48:03
Approximativ heißt, dass es jetzt nicht genauer 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 sinnvoll bei Problemstellungen, bei denen man keine Hoffnung haben kann,
48:21
dass man sie hundertprozentig durch den Algorithmus lösen kann, aber 99 prozentig kann man sie durch den Algorithmus lösen, sodass man hinterher noch rangehen kann, durch scharfes Hingucken, hier und da ein bisschen verschieben. Ein Beispiel dafür ist der Zuteilungsalgorithmus, beispielsweise in Moodle. Sie melden sich an, sie geben Prioritäten. Die drei Termine für Kleingruppenübungen sind, möchte ich gerne haben.
48:45
Die drei gehen gar nicht. Und wenn abgeschlossen ist, wenn jeder Teilnehmer seine Angaben gemacht hat, dann versucht der Zuteilungsalgorithmus, übrigens ist das genauso ein Matching-Algorithmus, Algorithmus für das Matching-Problem, was ich vorhin eingangs erwähnt hatte,
49:03
versucht dann eine Lösung zu finden. Unsere Erfahrung ist, er schafft das nicht hundertprozentig, er schafft es auch nicht nur 99 prozentig, aber er schafft es irgendwie so 90 prozentig. Und der Mensch kann hinterhergehen und kann die restlichen 10% die der Algorithmus nicht geschafft hat, kann er die dann noch irgendwie per Hand hin und her frickeln.
49:21
Ja, ist also durchaus sinnvoll, auch da, wo man keine Hoffnung haben kann, dass auf einen Algorithmus, der die Problemstellung hundertprozentig löst, also eine zulässige Lösung findet, dann eine Lösung wenigstens zu finden, die nah an der Zulässigkeit ist, die nicht mehr viel zu tun ist,
49:40
um die Lösung zulässig zu machen. Optimierung heißt, wir möchten eine Lösung haben, möglichst eine zulässige Lösung. Die Beweisung, die vielleicht nicht optimal ist, aber beweisbar, nicht zu weit weg ist von Optimalität. Und damit es approximativ heißt und nicht heuristisch, fordern wir,
50:01
es gibt ein vernünftiges mathematisches Maßstab, der uns sagt, wie weit die Lösung, die der Algorithmus berechnet hat, weg ist von der Optimallösung, beispielsweise 10% schlechter als die Optimallösung
50:21
oder 5% schlechter als die Optimallösung. Und es ist beweisbar, dass er tatsächlich so gut, mathematisch beweisbar, dass er tatsächlich so gut ist. Wo nichts beweisbar ist, diese Algorithmen heißen heuristisch und das ist die Mehrzahl der Algorithmen, die wir hier betrachten werden, weil wir es halt mit Problemstellungen zu tun haben, mit algorithmischen Problemstellungen,
50:42
bei denen man nicht mehr viel beweisen kann oder bis jetzt hat kein Mensch die Beweise gefunden. Deshalb steht auch hier nur, der Algorithmus versucht, attempts at, versucht, eine zulässige oder halbwegs zulässige Lösung zu finden, aber keine Garantie. Und bei Optimierung, er versucht, eine optimale oder halbwegs optimale Lösung zu finden,
51:05
aber deshalb trotzdem keine Garantie. So, dieses Kapitel werden wir nur ganz kurz streifen mit den Dingen, die halbwegs unterhaltsam sind und die mathematischen Sachen werden wir hier ausblenden. Wenn Zeit bleibt, werden wir darauf zurückkommen, aber nicht unbedingt.
51:26
Können Sie ein bisschen genauer nachlesen in diesem Buch, das finden Sie auch in der Bibliothek bei uns. Da finden Sie auch die Cartoons drin. Sie sehen hier an einigen Stellen, dass das noch genug Platz ist, da waren Cartoons vorher drin. Die Folien sind erstellt worden zu einer Zeit, als man als so armer kleiner Informatikdozent
51:44
noch nicht so richtig das Bewusstsein hatte in Bezug auf Urheberrechte im Internet. Also schon eine Weile her. Inzwischen hat man dieses Bewusstsein und in der Vorbereitung dieses Semesters habe ich,
52:03
erst einmal diese Cartoons rauszuschmeißen, damit ich die Aufzeichnungen hier und die Folien problemlos ins Internet hängen kann und nicht in irgendein Intranet hineinhängen muss. Was zwar auch nicht korrekt ist nach meinem Rechtsverständnis, aber immerhin wird man da
52:25
mit großer Wahrscheinlichkeit nicht erwischt, wenn man es ins Intranet hängt, soweit ich weiß. Also wird schon schwierig sein. Mit Google finden die Rechtsabteilungen der Firmen das dann nicht. So, Sie sind also der Chief Algorithm Designer Ihres Unternehmens.
52:45
Und Sie sollen jetzt ein Problem lösen, das sehr wichtig ist. Sie arbeiten und arbeiten und arbeiten und arbeiten, basteln rum, erinnern sich an alles, was Sie in der GD2 und den Amplimierungsalgorithmen gelernt haben und stellen fest, es geht nicht, Sie finden nichts. Also es geht nicht, stellen Sie nicht fest,
53:02
sondern Sie stellen fest, ich kriege es nicht hin. So, was Sie natürlich nicht wollen, ist, dass Sie jetzt Ihrem Boss beichten müssen. Ich kann beim besten Willen keinen effizienten Algorithmus finden. Ich vermute, ich bin einfach zu dämlich dazu. Das wollen Sie nicht. So, wenn Sie das tun, dann wird Ihr Boss vermutlich wenig Verständnis dafür haben.
53:25
Also vielleicht nur etwas zum Wort Boss. Es gibt auch das Wort Chef und das Wort Chief im Englischen. Also das, was wir normalerweise als Chef ansehen, ist im Englischen eigentlich Boss.
53:41
Chef ist meistens der Küchenchef, also der Hauptkoch. Und Chief ist eigentlich Häuptling. Häuptling übertragen häufig auch auf Polizeichef, also Polizeihäuptling. Und manchmal auch dann eben auf, so ein bisschen salopp auf andere Positionen,
54:02
wie hier Chief Algorithm Designer. Also Sie wollen, Sie gehen nicht zu Ihrem Chief oder Chef, sondern Sie gehen zu Ihrem Boss. Und Sie wollen natürlich nicht, dass der Boss Sie umgehend feuert, sondern Sie sollen sagen, hier, ich kann keinen effizienten Algorithmus finden,
54:23
weil es gibt einen solchen Algorithmus nicht. Das ist das, was Sie wollen. Zu sagen, das ist eine Boss, die Aufgabe, die du mir gestellt hast, ist eine unmögliche Aufgabe. Wobei, das natürlich auch noch, können Sie sich vorstellen, nicht allzu leicht ist.
54:43
Dass eine Problemstellung intractable nicht unbedingt machbar ist. Ich will hier nicht in diese Theorie der NP-Vollständigkeit einsteigen hier. Es gibt eine solche, es gibt Techniken, mit denen man das beweisen kann. Und wie ich schon beim letzten Mal gesagt hatte, für die allergrößte Mehrzahl der Problemstellungen
55:04
ist es tatsächlich so, dass diese Problemstellung NP-schwer ist. Ich will nochmal wiederholen, was das konkret bedeutet. NP in der Praxis, ich will jetzt nicht sagen, wie das definiert ist und so weiter, sondern was konkret bedeutet für die Praxis bedeutet, nehmen Sie das TSP als Beispiel her, das ist NP-schwer, oder dieses Zuordnungsproblem, hier Universitäten ist auch NP-schwer,
55:24
nehmen Sie das TSP her. Für jeden Algorithmus, den Sie für das TSP basteln, egal wie der aussieht, egal wie genial der gebastelt ist, für jeden denkbaren, machbaren Algorithmus, für jeden Algorithmus, den Sie in C, C++, Java, Assembler,
55:44
oder auch auf dem Condom Computer System ergibt, implementieren können, wird es möglich sein, eine Eingabe vielleicht von der Größe von 50 Punkten zu finden, schon Punkte in der Ebene, muss gar nicht abstrakt sein, 50 Punkte in der Ebene, und Ihr Algorithmus rechnet sich darauf tot,
56:05
braucht länger als dieses Universum eben Zeit geben wird, wenn die Physiker mit ihren Schätzungen recht haben, wesentlich länger, es braucht mehrere Universen. Es gibt nicht die eine Menge von 50 Knoten,
56:22
sodass alle Algorithmen sich da totrennen, sondern für jeden Algorithmus gibt es jeweils eine spezifische Menge von 50 Knoten, die zu finden ist nicht ganz einfach, brauchen wir auch nicht finden, man hat bewiesen, dass das Problem NP-schwer ist und damit weiß man, dass das so der Fall ist.
56:40
Also das hier ist ein gepflegtes Understatement. Can't evidence that many important problems can't be solved quickly. So, also zu wissen, dass das Problem hart ist, schwer ist in dieser Bedeutung,
57:01
das ist natürlich schön drastisch von Garen Johnson ausgedrückt, 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.
57:20
Wenn sie Glück haben, wenn sie oder gut oder tüchtig sind, tüchtig sind und das Glück des Tüchtigen dabei haben, so vielleicht formuliert, dann finden sie eine approximative 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.
57:40
Wenn sie nicht so glücklich oder nicht so tüchtig sind, dann ist alles, was übrig bleibt, etwas heuristisches. Was nicht schlecht ist, ich will das auf keinen Fall schlecht reden, im Gegenteil, wir reden ja hier über Heuristiken vor allem, die sind in der Praxis verdammt gut, wenn sie gut gemacht sind.
58:01
Es gibt oft Situationen, in denen kann man heuristische Algorithmen finden, wo man über irgendwelche Indizien sagen kann, naja, im Normalfall finden die sogar die optimale Lösung. Das sieht ganz danach aus, dass die Lösungen, die wir hier in der Hand haben, durch diese Heuristik tatsächlich optimal sind, oder vielleicht ein paar Promille weg sind von Optimalität.
58:23
So, es gibt weitere Möglichkeiten, ein Algorithmus, der exponentiellen Aufwand hat, natürlich können Sie auch das TSP mindestens mit faktorellem Aufwand lösen, indem Sie nämlich alle Möglichkeiten ausprobieren.
58:41
Sie haben nur faktorell viele Permutationen, die Fakultät wächst dramatisch, aber ein Exponentialzeit-Algorithmus in der Hoffnung, dass die Instanzen diese reingeben, dass der im Worst Case exponentiell ist,
59:03
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 Laufzeit unter Kontrolle. Hier haben wir die Garantie,
59:21
dass am Ende des Algorithmus bei der Terminierung die Lösung optimal oder approximativ ist, aber wir haben die Laufzeit nicht unter Kontrolle, sondern hoffen, dass die Laufzeit bei den Instanzen, die in der freien Wildbahn wirklich vorkommen, gut ist. Auch das ist eine Hoffnung, die oft sehr gut erfüllt ist. Eine andere Möglichkeit, die durchaus oft wert ist,
59:42
ist, dass wir versuchen, eine andere Abstraktion zu finden, dass man nur deshalb zu einer mp-vollständigen Problemstellung gekommen ist, weil man vielleicht ein paar Dinge, ein paar Indizien, die in den Daten stecken, ignoriert hat, und wenn man die herausarbeitet und zu einer anderen Abstraktion kommt, kommt man pleite hin.
01:00:00
sich zu einer anderen Problemstellung, die nicht mehr NP schwer ist. Zu diesem letzten Punkt möchte ich Sie auf die Vorlesung Algorithmische Modellierung im Sommersemester verweisen. Da werden wir genau solche Dinge betrachten. So, jetzt Schluss mit NP-Vollständigkeit. Jetzt überspringen wir das alles hier.
01:00:21
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 ja auch lang genug. So, wie viel Zeit haben wir heute? Haben wir nicht mehr so viel Zeit? Eine halbe Stunde noch ungefähr. Und ich muss aufpassen, dass ich immer relativ zügig Schluss mache,
01:00:45
weil solange das Einpacken noch so lange Zeit bei mir dauert, solange ich das noch nicht ausreichend oft geübt habe, das Abbauen und Einpacken. So, nachbarschaftsbasierter Ansatz. Da gehen wir mal einen Schritt voran. Zu einer ersten Intuition. Wir sind wieder beim TSP.
01:01:04
Das ist das, worum es in diesem Kapitel als Grundlage geht. Zunächst einmal vielleicht die Frage an Sie. Schauen Sie sich das obere der drei Bilder an. Können Sie auf Anhieb etwas darüber sagen, ob das eine optimale Lösung ist oder nicht,
01:01:20
wenn wir für die Kantenlängen euklidische, die üblichen normale Länge in der Ebene annehmen? Bitte? Ist nicht optimal. Genau, die zwei Querwege sind länger. Das können wir uns vielleicht an einem Beispiel kurz anschauen.
01:01:44
Sie haben hier zwei Querwege, die sich kreuzen. Und wenn Sie die beispielsweise so miteinander verbinden. Warum ist das kürzer?
01:02:00
Malen wir beides in ein Bild rein. Ich glaube ich muss, ich glaube ich sollte doch versuchen nochmal zu wischen. Das wird zu unübersichtlich.
01:02:21
Also, ich würde mich freuen, wenn die Fachschaft eine Initiative starten würde. Einen Ewigkeitsbeschluss, dass niemals, solange die TU Darmstadt besteht, die Tafeln an den Hörsälen abgeschafft werden. Und vielleicht sogar die Hörsäle, die keine Tafeln mehr haben,
01:02:42
wenn wir das Audimax wieder welche bekommen. Und die, die Tafeln haben, vielleicht auch mal dann wieder bequemere Tafeln haben, wo man nicht laufen wischen muss. So, was ist die Situation hier?
01:03:02
Wenn wir die mal notieren. Das Bild sieht so aus, mit den zwei Kanten. Wenn wir die beiden mal wirklich in ein Bild reintun, um die miteinander zu vergleichen.
01:03:21
Dann stellen Sie fest, das ist Länge A, das ist Länge B, das ist Länge C, das ist Länge D. Jetzt können wir die noch unterteilen in B1 und B2 und die in C1 und C2. Und dann können Sie Dreiecksungleichung anwenden. A ist kleiner gleich B1 plus C2.
01:03:46
D ist kleiner gleich B2 plus C1. Und wenn Sie beides zusammennehmen, dann kriegen Sie raus, A plus D ist auf jeden Fall kleiner gleich B plus C.
01:04:05
Und wenn wir nicht den entarteten Fall haben, sondern den typischen Fall wie hier, dann haben Sie sogar einen echt kleiner. Also kann es nicht, das obere Bild, die Rundtour kann nicht optimal sein. So, das war jetzt nur eine Nebenbedingung. Worum es geht, sind Operationen wie diese.
01:04:23
Wir laufen auf der Lösungsmenge herum. Wir stellen uns vor, die Lösungsmenge ist ein Graph mit Verbindungen dazwischen. Wir sind immer auf einem Knoten, auf einer Lösung.
01:04:40
Und wir gehen zu einer benachbarten Lösung. Deshalb heißen die, sehen Sie hier nochmal oben in der Überschrift, nachbarschaftsbasierte Ansätze. Das ist der abstrakte Blick. Der konkrete Blick bei diesem Beispiel ist, wir suchen uns zwei Kanten her, zum Beispiel die beiden, hätten auch zwei beliebige andere Kanten sein können,
01:05:02
nehmen die weg und fügen zwei neue Kanten so ein, dass sich wieder eine Rundtour ergibt, wobei dann noch eine Reparatur notwendig ist. Sie sehen das hier, wenn ich diese zwei Kanten lösche, wie ich das gemacht habe, und dann die zwei Kanten entsprechend einfüge, dann stimmt erst einmal, je nachdem,
01:05:26
ich muss einen der beiden offengebliebenen Streckenzüge umdrehen, ich habe hier den rechten umgedreht, damit das Ganze wieder zu einer Rundtour wird. Das ist die Operation, wie man von einer Tour zur nächsten kommt. Wir haben in jedem Zeitpunkt, wir reden immer von Schleifen hier, im programmiertechnischen Sinne.
01:05:46
Wir haben eine Schleife, wo in jeder Iteration, wo wir zwischen zwei Iterationen immer eine zulässige Rundtour haben und in jeder Iteration ändern wir diese Rundtour, schmeißen zwei Kanten raus, tun zwei andere Kanten rein
01:06:01
und haben dann nach dieser Iteration wieder eine neue Rundtour. Und hoffen, dass wir auf die Art und Weise, wir starten irgendwie, vielleicht sogar mit einer zufälligen Rundtour oder mit einer Rundtour, die uns so nach einfachen Kriterien besonders gut ausschaut, starten mit so einer und hoffen, dass wir so Schritt für Schritt zu einer besseren Rundtour kommen.
01:06:23
Darum geht es hier und das ist ein Thema, das sich sehr stark nutzbringend variieren lässt. Nämlich nicht nur einfach gucken, wenn ich die zwei Kanten rausnehme und entsprechend zwei andere Kanten reintue, bringt das bessere Lösungen, sondern zum Beispiel auch variieren dahingehend,
01:06:45
dass man nicht in so einem lokalen Loch gefangen bleibt, wenn es keine Möglichkeit gibt, durch einen solchen Austauschschritt zu einer besseren Lösung zu kommen, dass man vielleicht erlaubt doch einen verschlechternden Austauschschritt zu machen,
01:07:01
in der Hoffnung, dass man dann wieder zu Verbesserungen kommt, die besser sind als das, wo wir gestartet sind. Oder auch wir werden dann später, das sind dann Evolutionsstrategien, genetische Algorithmen, wir werden mehrere zulässige Lösungen im Wettstreit gegeneinander antreten lassen. Jede von denen verändert sich auf diese Art und Weise so ein bisschen,
01:07:23
das Prinzip von Mutation und Selektion aus der Biologie, deshalb Evolutionsstrategien. Und die, die so aussehen, als ob sie zu guten Lösungen führen werden, die überleben oder duplizieren sie sogar. Und die anderen, die so aussehen, als ob sie eher in Sackgassen reingehen,
01:07:42
die streichen wir aus unserem Pool von zulässigen Lösungen. Das ist so ungefähr das große Bild von diesem Kapitel. So, dann gehen wir wieder zurück. Jetzt haben wir eine gewisse Vorstellung davon, worum es geht. Abstrakt gesprochen reden wir von Nachbarschaftsbeziehungen.
01:08:04
Ja, in diesem Beispiel, gehen wir vielleicht nochmal ganz kurz dahin, wir sagen, diese beiden Touren, diese beiden Rundtouren, das oberste und das unterste Bild, sind miteinander benachbart. Durch diese Operation, durch diese algorithmische Operation, die wir uns als definierende Operation vorgenommen haben,
01:08:22
kommen wir von der Einlösung zu anderen und übrigens auch wieder zurück. Das ist eine symmetrische Nachbarschaft. Mit derselben Art von Operation kommen wir von da nach da wieder zurück. So, wir betrachten uns jetzt also eine Instanz, eine Input, eine Menge von Punkten in der Ebene beim TSP, eine Gegebene.
01:08:49
Und wieder, diese Notation hatten wir heute eingeführt, f von i für die Instanz i, ist f von i die Menge der zulässigen Lösungen. Im Beispiel TSP die Menge der Rundtouren, der echten Rundtouren ohne Subzyklen.
01:09:03
Und wir haben die Zielfunktion, das ist beim TSP eben die Länge des Streckenzugs. Und was wir für jede einzelne zulässige Lösung definieren, sind die, die wir mit so einer Operation erreichen.
01:09:21
Das ist die Nachbarschaft, sind die Zulässigen Lösungen, die wir auf die Art und Weise erreichen. Das heißt, was wir uns abstrakt vorstellen, ist, jeder zulässige Lösung, wir stellen
01:09:56
uns wirklich die Menge der zulässigen Lösungen als Punkte in einem abstrakten Raum vor.
01:10:03
Und dann ist es auch vollkommen egal, ob wir vom TSP reden oder von irgendeiner anderen Problemstellung. Das ist der Grund dafür, warum wir so abstrahieren. Das ist immer der Grund, warum man abstrahiert. Damit man verschiedene, konkrete Dinge unter einen Hut bringen kann, auf gleiche Art und Weise sehen und behandeln kann. Und diese beiden Rundtouren von dem Bild sind Sorum und Sorum mit einer Kante verbunden, was besagt, ich
01:10:32
komme mit dieser algorithmischen Vorschrift zwei Kanten rausnehmen, andere zwei Kanten rein, nehmen von dem einen zum anderen.
01:10:43
Diese Abstraktion macht auch vielleicht nochmal klar, dass wir ja nicht unbedingt nur von einer Möglichkeit reden, wie man von einer Lösung zu anderen kommen kann. Es gibt auch bei ein und derselben Problemstellung wie beim TSP natürlich sehr viele Möglichkeiten, wie wir das definieren können.
01:11:05
Man konstruiert eine neue Lösung aus einer gegebenen Lösung. Es gibt beispielsweise überhaupt keinen Grund, sich auf zwei Kanten zu beschränken. Wenn Sie eine Rundtour haben, so mit drei, Sie können das auch den Übergang
01:11:27
von einer Tour zu einer hoffentlich besseren Tour mit über drei oder mehr Kanten definieren. Sie nehmen die drei raus, dann bleiben diese drei Teilabschnitte übrig und jetzt
01:11:44
muss ich gucken, dass ich die so miteinander verbinde, dass sich keine Subzyklen ergeben. So eine Kante beispielsweise, dann so eine Kante und so eine Kante. Und Sie müssen dann diese nur angedeuteten Teiltouren natürlich dann entsprechen, wo es notwendig ist umdrehen.
01:12:10
Das ist natürlich genauso möglich. Wir reden von einem abstrakten Schema, auf dessen Basis wir die Algorithmen definieren,
01:12:21
die dann konkret zum Beispiel dieses oder das mit den zwei Kanten ist. Das ist absolut konform dann zu dem, was Sie auch in der Übungsaufgabe machen sollen, mit den Möglichkeiten Ihrer Programmiersprache, die Sie gewählt haben. Java werden vermutlich die meisten von Ihnen wählen, vielleicht manche C++ oder ich weiß nicht was.
01:12:43
Ja, mit den Abstraktionsmöglichkeiten, mit den Polymorphie-Möglichkeiten genau das nachzubilden, dass die Algorithmen genau auf dieser Ebene sind. Und dann kann man sowohl die Problemstellung, die Sie behandeln, als auch die konkrete Definition dieser Nachbarschaft wie in ein Framework, wie in eine Softwaretechnische Framework praktisch als konkrete Klassen abgeleitet von Interfaces reinstecken.
01:13:07
Das ist die Zielsetzung der praktischen Aufgabe. So, was ist jetzt also eine Nachbarschaft? Jeder zulässigen Lösung wird eine gewisse Teilmenge der zulässigen Lösung zugeordnet.
01:13:26
Ich weiß nicht, ob Ihnen diese Darstellungsweise vertraut ist. Also wenn Sie M ist eine Menge, ist Ihnen dann vertraut, dass man zwei hoch M schreibt?
01:13:45
Das ist die Potenzmenge von M, also die Menge, also Teilmenge von M. Brauchen wir jetzt vielleicht nicht weiter zu vertiefen, warum man das so schreibt.
01:14:03
Die Mathematiker können Ihnen das genauer sagen. Ach Mist, ich bin ja Mathematiker. Gut, das definiert einen Graphen. Die Knoten sind die Lösungen und die Kanten sind genau diese Beziehungen.
01:14:23
Von einer Lösung kann ich zu einer mit so einer algorithmischen Vorschrift kommen. Das heißt, ich habe eine gerichtete Kante. Hier kann es durchaus mal sein, Sie können ja durchaus einen unendlich großen Lösungsraum haben für eine Problemstellung.
01:14:40
Was wäre jetzt ein gutes Beispiel für einen unendlich großen Lösungsraum? TSP ist natürlich kein gutes Beispiel dafür. Ein Beispiel für eine Problemstellung mit einem unendlich großen Lösungsraum. Fällt Ihnen was ein?
01:15:09
Gut, also jede Problemstellung, die bei den zulässigen Lösungen ein Intervall oder eine Menge von reellen Zahlen sind, ist es natürlich automatisch der Fall.
01:15:20
Gut, mir fällt jetzt auch kein passendes Beispiel ein. Und wie wir gesprochen haben, symmetrisch oft genug ist die algorithmische Vorschrift. Wenn man die zweimal anwende, kommt man wieder zur Ausgangslösung. Dann ist die symmetrisch. So, jetzt haben wir genug, hoffentlich langsam, mit Formeln rumhantiert.
01:15:43
Was wir brauchen, um damit umzugehen, ist etwas, was wir beim letzten Mal schon schön intuitiv dargestellt haben. Wie spät haben wir es denn eigentlich? Na ja, noch ein bisschen.
01:16:02
Nämlich, wir hatten letztes Mal so ein Bild gezeichnet von einer Funktion, von einer Funktion von R nach R, die zum Beispiel so aussieht.
01:16:36
So, sowas hatten wir letztes Mal. Das hier ist ein lokales und zugleich globales Optimum.
01:16:58
Das ist nur ein lokales Optimum.
01:17:05
Ich denke, es ist klar, was gemeint ist, in der Mathematik haben Sie mit Optima schon zu tun gehabt. Der Punkt hier, der tatsächlich die Funktion global minimiert und lokal heißt eben nur, in einer Umgebung ist das das Beste.
01:17:25
In einer kleinen beschränkten Umgebung ist das die beste Lösung. Das ist entscheidend wichtig für diese nachbarschaftsbasierten Ansätze. Denn wenn Sie das machen, was man erst einmal intuitiv machen würde, was würde man machen?
01:17:41
Zum Beispiel hier, TSB. Man würde sich mit irgendeiner 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 zwei Kanten, die, wenn ich
01:18:06
die wegnehme und die Tour so wieder zusammenfüge, sodass sich insgesamt eine bessere Tour ergibt. Wenn ja, mache ich das. Schön, habe ich eine bessere Tour. Dann gehe ich weiter, gehe von dieser neuen Tour aus, gucke wieder.
01:18:21
Gibt es irgendwelche zwei Kanten, wenn ich die rausnehme und dafür das eben so umstöpsele, gibt es da wieder was besseres. Wenn ja, mache ich das wieder. Und irgendwann wird die Antwort, nach endlich vielen Schritten, wird unweigerlich die Antwort nein sein. Es gibt keine zwei Kanten mehr von der jetzigen Tour, die ich in dieser langen Abfolge
01:18:41
von Umkonstruktionen, wo ich hingekommen bin, die immer in jeder Umkonstruktion eine Verbesserung der Zielfunktion gegeben haben. Wenn ich jetzt angekommen bin, irgendwann kommt der Punkt, wo es keine Möglichkeit der Verbesserung mehr gibt, wo es keine zwei Kanten mehr geben kann. Jetzt ist die Frage, bin ich hier, wo ich hin will oder bin ich hier, wo ich eigentlich nicht hin will?
01:19:11
Bin ich tatsächlich im globalen Optimum in der bestmöglichen Lösung gelandet oder dumm gelaufen bin ich nur
01:19:21
an einer Lösung gelandet, die eben lokal in dieser Nachbarschaft, in der unmittelbaren Umgebung nichts besseres mehr hat, wo ich eben durch wegnehmen zwei Kanten und umstöpseln, wie auf dieser Folie, zunächst besseren komme, aber vielleicht gibt es trotzdem noch bessere Lösungen. Offensichtlich hängt es davon ab, wo ich gestartet bin.
01:19:42
Wenn ich hier gestartet bin und Schritt für Schritt mich verbessere, dann lande ich da, wo ich hin will. Wenn ich hier gestartet bin und mich Schritt für Schritt verbessere, dann lande ich da, wo ich nicht hin wollte. Und das kann beliebig schlecht sein. Die Tour, die rauskommt, kann beliebig schlecht sein.
01:20:03
Deshalb ist es wichtig hier, sich über globales und lokales Optimum damit auseinanderzusetzen. Was ist ein globales Minimum oder Maximum? Wir nehmen hier nur Minimum. Das ist eine zulässige Lösung, sodass der Zielfunktionswert minimal ist, über global minimal ist.
01:20:24
Also der Zielfunktionswert jeder anderen zulässigen Lösung ist größer gleich dem Zielfunktionswert dieser Einlösung. Ein lokales Minimum wiederum ist eine zulässige Lösung, sodass der Zielfunktionswert optimal minimal ist in der Nachbarschaft.
01:20:43
Es gibt von diesem Punkt aus, in diesem Grafen, von dem ich gesprochen habe, in diesem Nachbarschaftsgrafen, gibt es keinen benachbarten Knoten, den ich mit einer Kante erreichen kann, mit einer solchen algorithmischen Transformation erreichen kann, der noch optimal ist, der, der besser ist.
01:21:06
Die schönsten Fälle sind natürlich die, wo wir uns um diese Unterscheidung keine Sorgen machen müssen. Und damit werden wir uns auch ein bisschen befassen mit diesem schönsten aller Fälle. Das, da nennt man diese Nachbarschaft exakt, wenn jedes lokale Minimum auch ein globales Minimum ist.
01:21:26
Das heißt, wenn das Bild nicht so aussieht, sondern wir hatten es beim letzten Mal, konvexe Funktion. Wenn das Bild beispielsweise so aussieht, wenn es keine lokalen Nebenminimal gibt, dann können wir starten, wo wir wollen.
01:21:45
Wir kommen immer, da wir immer in einem lokalen Minimum ankommen, kommen wir automatisch im globalen Minimum an. Ich habe das jetzt hier Minimum genannt alles, natürlich für Maximum ist alles dasselbe.
01:22:01
So, der erste Algorithmus, und dennoch noch so einfach, viel zu einfach, wird komplizierter. So, das was ich eben mündlich skizziert habe, für das TSP beispielsweise. Wir beginnen in der Initialisierung mit irgendeiner arbitrary, mit einer beliebigen zulässigen Lösung.
01:22:25
Solange wir in der aktuellen Lösung, für die aktuelle Lösung erstellen, einen Nachbarn S finden, also den wir in den Nachbarschaftsgrafen mit einer kann erreichen kann, der einen echt besseren Zielfunktionswert hat,
01:22:45
dann nehmen wir so eine Lösung, und das wird unser neues Stern. Und mit diesem neuen Stern gehen wir wieder in diese Weilschleife hinein, bitte.
01:23:09
Ja, Sie müssen sagen wir so, ja genau, Sie haben schon einen wesentlichen Punkt angesprochen, die Definition der Nachbarschaft ist oft genug heikel, oft genug nicht ganz trivial.
01:23:24
Wenn Sie die Nachbarschaft zu groß wählen, dann kostet Sie jeder einzelne Schritt unheimlich viel Zeit. Wenn Sie die Nachbarschaft zu 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 Nachbarschaftsgrafen von jeder Lösung zu jeder anderen Lösung kommen könnten.
01:23:41
Betrachten Sie zum Beispiel Folgendes, betrachten Sie folgende Problemstellung. Sie haben eine Menge von irgendwelchen Stücken, das ist Stück 1 bis Stück N,
01:24:18
mit Länge A1 oder Gewicht A1 und Gewicht A1, und die wollen Sie halbe halbe aufteilen.
01:24:30
Das ist der Input, Output, Aufteilung in zwei Mengen.
01:24:46
Denken Sie an eine Scheidung und die A's sind Kostenwerte der einzelnen Güter und Sie wollen halbe halbe die Güter, die Sie haben, nach den Kostenwerten aufteilen.
01:25:02
Das ist ein blödes Beispiel, aber mir fällt auch kein besseres Beispiel für diese vereinfachte Version einer allgemeinen Problemstellung ein. Ziel, möglichst nah an halbe halbe zu kommen.
01:25:26
So, jetzt gehen wir auf diese Art und Weise vor, Sie haben eine Aufteilung. Hier zum Beispiel 5 drin, hier haben Sie 3 oder 3 drin und Sie definieren jetzt als Nachbarschaft Austausch,
01:25:46
dass Sie hier ein X und ein Y haben und diese Aufteilung geht in eine neue Aufteilung über, indem Sie das X und das Y miteinander ersetzen.
01:26:02
Das soll hier ein Y sein. So kann man die Nachbarschaft definieren, schön einfach algorithmisch handhabbar. Was ist zu dieser Nachbarschaftsdefinition zu sagen?
01:26:22
Genau, der Nachbarschaftsgraf, um es wieder in grafen-theoretischen Begriffen zu sagen, der Nachbarschaftsgraf ist hochgradig unzusammenhängend, zerfällt in einzelne Zusammenhangskomponenten, das heißt Sie können mit einem Weg von solchen Schritten hier niemals zu einer Lösung kommen, wo die Aufteilung nicht 5 zu 3 ist, gemessen an einzelnen Stück.
01:26:43
Aber woher wissen Sie, dass die guten Lösungen wirklich die Aufteilung 5 zu 3 haben? Vielleicht ist 4 zu 4 die richtige Aufteilung oder vielleicht finden sich bei einer Aufteilung 4 zu 4 die besten Lösungen oder sogar bei einer Aufteilung 1 zu 7, wenn ein Stück besonders schwer ist.
01:27:06
Ja, beantwortet das so ein bisschen Ihre Frage? Man hat das Problem in gewisser Weise, da gebe ich Ihnen recht, verlagert, aber verlagert in eine Problemstellung, diese Nachbarschaft zu finden, die man viel besser intellektuell im Griff hat, als jetzt zu versuchen,
01:27:22
irgendwie von der grünen Wiese aus ein Algorithmus für so eine komplexe Problemstellung sich selber auszudenken. Eine Nachbarschaftsbeziehung muss nicht zwangsläufig symmetrisch sein. Die, die wir jetzt hier betrachtet haben, sind es, aber ist nicht zwangsläufig der Fall.
01:27:47
Wobei mir jetzt ganz spontan kein sinnvolles Beispiel für eine nicht symmetrische Nachbarschaft einfällt. Also unsinnige Beispiele fallen mir natürlich sofort ein, aber damit will ich Sie jetzt nicht belästigen, ja?
01:28:07
Okay, ja, genau. Wenn Sie... Okay, vielleicht ist das ein sinnvolles Beispiel. Es ist auch erlaubt, von der größeren Zahl zur kleineren Zahl hin asymmetrisch zu verschieben. Das ist dann keine symmetrische Nachbarschaft mehr, weil Sie ja rückwärts nicht verschieben dürften mehr.
01:28:25
Gut, also das ist der Algorithmus, eine sehr einfache Schleife auf diesem abstrakten Niveau. Und auf diesem abstrakten Niveau möchte ich gerne die Implementation bei Ihnen sehen. Alles, was konkreter ist, möchte ich ausgelagert sehen in Klassen, die dort drin definierte Interfaces implementieren.
01:28:49
Beziehungsweise, wenn Sie nicht Java oder wählen, dann das entsprechende Analoge in Ihrer Programmiersprache. Wenn Sie eine Programmiersprache haben, ins Auge gefasst haben, die sowas nicht wirklich vernünftig erlaubt,
01:29:03
sollten Sie nochmal drüber nachdenken, ob das die richtige Programmiersprache dann für diese Veranstaltung ist. So, für alle Algorithmen möchte ich die Implementation auf diesem Abstraktionsniveau sehen.
01:29:24
Ich möchte in dem eigentlichen algorithmischen Code keinen Hinweis darauf sehen, ob jetzt gerade das TSP oder irgendeine andere Problemstellung gelöst wird. Kein Hinweis darauf, mit welcher Nachbarschaftsbeziehung das jetzt gemacht wird. Das soll alles ausgelagert werden. Wenn mal der Knoten geplatzt ist, dann ist es glaube ich ganz einfach.
01:29:46
Das ist meine Erfahrung, als die Veranstaltung noch Einführung in FOC war. Und das eben eine Pflichtveranstaltung war, mit Pflicht die Aufgabe zu lösen. So, Kommentar, nur dazu, wir müssen uns jetzt beeilen.
01:30:01
Das ist die letzte Folie. Bitte nochmal ganz kurz Konzentration, nur noch eine Minute. Wenn wir eine exakte Nachbarschaft haben, wo jedes lokale Optimum, globales Optimum ist, dann kriegt dieses einfache Schema natürlich schon die optimale Lösung. Denn sie terminiert erst dann, das ist die Abbaubedingung hier.
01:30:22
Die Abbaubedingung ist gleichbedeutend damit, dass wir mit der Lösung, die wir jetzt als letztes konstruiert haben, 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.
01:30:47
Warum? Weil er sich ja von Schritt zu Schritt verbessert. Das heißt, er kommt nie zweimal an dieselbe Lösung. Er kommt in jeder Iteration an eine immer neue Lösung, die er bis dahin nicht gesehen hat. Und da es nur endlich viele Lösungen in dem endlich großen Lösungsraum gibt, heißt es nach endlich vielen Schritten ist Schicht ist finito.
01:31:08
So, finito ist das richtige Wort. Dann danke ich Ihnen. Und wenn Sie Fragen haben zur Vorlesung oder zur praktischen Aufgabe oder zur Organisation, stellen Sie die gerne im Forum.
01:31:23
Ich werde mir jetzt wieder angewöhnen, regelmäßig Forum zu lesen. Ich hoffe, ich werde dann auch immer vom Forum per E-Mail wie bisher auch benachrichtigt, wenn was Neues da ist. Beziehungsweise gerne auch auf anderen Kanälen, entweder nach der Veranstaltung hier oder eben per E-Mail oder sonst wie.
01:31:45
Gut, dann bis nächste Woche. Scheißdreck.