Merken

Exakte Verfahren II: Dynamische Programmierung, Anwendungen Approximationsalgorithmen

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
so weil wir dann muss ihr da er nur je gut herzlich
willkommen zu Teil 2 der exakten Verfahren Vorlesungen die am Montag gestarteten ich würde darauf aufmerksam gemacht dass sich am Montag das Wort brennt bauen bauen die ganze Zeit verwendet hab und es nie so richtig definiert hatte er damit meinte ich immer den Baum entsteht wenn man eben das Problem aufsplittet nach einer Variablen in 2. Teil Probleme und dort liegt die Grenzen die Schranken ausreichend so wie wir das gesagt haben sie dieser Baum der dabei entsteht die nämlich einfach brennt der Baum Baum nur falls es vielleicht bei manchen noch unklar war gut aber damit waren fertig wir sind jetzt bei der dynamischen Programmierung erst mal nochmals um wieder erinnern was das war also wir minimieren ganz normal oder Maximilian dem eine Zielfunktion die aber additiv über die Zeit ist nur deshalb funktioniert dieses Minimally tät's Prinzip das Teilstrategien auch Mathem minimal sein müssen das was wir suchen sind diese y ist n für die x Variablen die Zustandsvariablen soll gelten dass die funktionale vom Zustand vorher und der Steuerung variabel man das heißt wenn wir die Steuerungs Variablen haben können wir jeweils den Folgezustand aus einem Zustand bestimmt weiterhin soll gelten ich das für ausgezeichnete Mengen haben es kann sein dass der Staat Zustand sogar klar definiertes und ich aus der Menge dann sollen die jeweiligen Zustände unterwegs auch aus entsprechend zulässigen Mengen sein und unsere Steuerungs Variablen dürfen auch nicht beliebig setzen seine kam auch aus zuvor definierten Mengen gut so sah also unser dynamisches Programm aus und wie gesagt das wichtige oder das essentielle ist das eben dieses Prinzip der Optimalität was darauf basiert dass man sich eine Gesamtstrategie aus optimal ein optimale Gesamtstrategie aus optimalem Teilstrategien zusammensetzen kann gilt also das war gesagt Dilthey Stratégies optimalen das impliziert auch dass Entscheidungen immer nur vom jetzt Zustand abhängen also unsere Steuer Variable y sozusagen hängig von dem ab was wir vorher entschieden haben wie kann daraus jetzt einer algorithmische ID entstehen ja wir haben also etwas das so aussieht und wollen in in der vom Leibe Rhythmus finden der uns so ein dynamisches Programm Lust und das wollen uns dabei zunutze machen und die Idee die man verwendet ist dass man das Feld rückwärts aufrollt dass man praktisch damit startet was man gerne am Ende haben möchte im Endzustand sich dann rückwärts vor arbeitet das wäre der optimale vorletzte Schritt sozusagen gewesen die und das funktioniert eben genau nur deshalb weil wir wissen dass unsere Entscheidungen zu einem bestimmten Zeitpunkt nicht von den vorherigen Entscheidungen abhängen ja deshalb kann ich sozusagen 1 1 n Stück meines Entscheidungsprozesses anschauen und erst mal darauf schauen wie verhalte ich mich mit meiner Strategie optimale die dann erweitern zu der Gesamt optimal Strategie das ist also das packt es Teil 1 unter 2 ist n und gut wie sieht so ein Algorithmus dann aus wenn wir den möglich auch schreiben wollen ich wir wollen so ein dynamisches Programm wie in der Definition lösen und das was wir gerne hätten es sowohl den optimalen Wert also wenn wir beispielsweise kurzes Wege Problem lösen wollen was dem Beispiel später sein wird oder ein Rucksack Problem dann möchte man natürlich den Wert des Rucksackes beziehungsweise die Länge des kürzesten wirksamer aber wir möchten eben auch dass neben gekommen sind und das ist genau die Strategie es gibt gut ja immer gesagt wir wollen rückwärts anfangen und es ist klar in unserer Zielfunktion haben wir ja end Kosten für Zustände die unabhängig sind von unserer Entscheidung weil das eben unser letzter Zustand ist das heißt die haben wir sowieso schon zur Verfügung für jeden Endzustand aus unserer Menge der Endzustände das heißt die können wir einfach setzen und J von Tee oder t von XT sollen wir jeweils die den Wert der optimale Lösung zu diesem Zeitpunkt t enthalten und J 0 1 rückwärts gelaufen sind wir praktisch insgesamt in optimaler dann enthalten wird und das rückwärts auf beziehungsweise das ist die Opti der Werte optimalen Teilstrategie ab dem Zeitpunkt der hier im Index steht und Endzeitpunkte das natürlich einfach nur wenn gesinnten irgendeinem enden Zustand und die Kosten dafür das so und jetzt wollen wir den optimalen vorletzten Schritt zu jedem Endzustand finden also das machen wir für alle Endzustände jetzt laufen wir
rückwärts durch unsere Domain dynamisches Programm und suchen uns genau den optimalen vorletzten Schritt in dem wir Folgendes machen was wir hier stehen haben in der Klammer das eigentlich genau XT +plus 1 gut diesen Wert nach unsere kussionen den haben wir das ist das was uns gegeben ist wann bei T minus 1 andere haben wird groß T das existent das ist das was wir haben und jetzt suchen wir uns aus allen also für jeden Zustand aus der Menge vorher prüfen wir ob wir mit einer Steuerungs Variablen hier ein übergangen konstruieren können so dass wir genau bei diesem also deswegen kann ich hier nicht allgemein XT +plus 1 hinschreiben weil dieses XT +plus 1 wirklich genau dasjenige ist nicht mach mal gut rüber was sich durch Auswertung dieser Funktion dieser Übergangsfunktion ja halte was eben von den XT was sich hier mehr anschaue gerade abhängt dieser Berechnung findet wirklich für jedes XT aus dem aus der Zustands Menge zum Zeitpunkt die Stadt ja und ich schau eben was wäre hier der optimale vorletzter Schritt gewesen wenn ich im vorletzten Schritt bei XT gewesen wäre Xtra kein er ist sofern sie die beste vorhergehen Entscheidung ja und das letzte ist geb ich das was ich gefunden hab hab aus und zwar einfach wird von x 0 damit habe ich mir dann einen Startpunkt .punkt ausgesucht der praktisch der optimale also für jeden Staat .punkt aus groß x 0 hab ich dieses diese Rekursion lang ausgeführt dass sich jeweils hier die rechte Seite optimiert hat über meinen möglichen der Strategie Variablen ich hab ich jeden optimal Wert für diesen Ausgangs haben für diesen Staat der Zustand sich und dann ich natürlich auch die Strategie aus und zwar sind das dann wirklich die y 0 die ich hier auf der rechten Seite also nicht y 0 sondern die Steuerung des variablen ich auf der rechten Seite durch die Minimierung erhalten hat gut also ich nutze das das weiß ich einfach durch meine Zielfunktion schon gegeben habe dadurch dass diese Zielfunktion Nebenzeit Zeit additives und ich am Schluss nur noch kosten für den Endzustand habe das nehme ich mir und betrachte dann für jeder möglichen vorhergehenden Zustand wie sieht der optimale übergangen zu einem Folgezustand aus und diese Werte der Folgezustände hab ich dann immer jeweils schon in jeder ltration ich durch diese Schleife laufen warum funktioniert der Algorithmus das war mit beweisen es gibt der ohne Fragen oder ok es wird behauptet dieser Algorithmus löst seinen am Programm wie das da oben gegeben das und wir machen ja so etwas wie wir naht Rekursion nunmehr verlassenen sehr darauf dass wir einen Wert schon haben und versuchen dann optimale vorhergehende Schritte zu kriegen also dass die beweist die des bei sowas Induktion erst mal je mehr und zur nur dann optimal Wert irgendwo unterwegs und das diese jetzt einfach mal der Raum aller möglichen Strategien sein die ich hätte anwenden können ich habe ich über mich her und schreien drin ist es leer ich bin ok also ich schau mir einen optimalen Wert für die letzten Schritte in einem dynamischen Programm ab Zeitpunkt heran das heißt ich minimiere über die Zielfunktion ab Zeitpunkt t ist groß also ab Zeitpunkt des Großzehe und ja fertig den hab ich jetzt erst mal gegeben und von dem möchte ich zeigen dass dieses J sperren an allen Zeitpunkten mit meinem J was sich in dem Algorithmus definiert hat übereinstimmenden hier sag ich in mich in mir wirklich einfach über alle möglichen Strategien ich hätte werden können werden ab gut mir zwar Induktion nach Tee machen das ist klar das wenn wir im Endzeitpunkt sind also wirklich nur noch den Schluss Zeitpunkt anschauen da da meine Steuerung keinen Einfluss auf die Zielfunktion hat muss das was sich in dem Algorithmus gesetzt hat mit dem optimal wird übereinstimmen das ist die Induktion S der Nutzungs Anfang ich bin ab dann wird gesagt weil das eben unabhängig von der Strategie ist es klar was ist unseren Options annahmen ja wir glauben einfach wir haben einen kleinen Zeh echt vor groß ein einen späteren Startzeit früheren Startzeitpunkt soll das die bisherig im bisherigen Werte die wir mit dem Algorithmus am haben mit dem optimal wer glaubt man übereinstimmen und wollen dann für den vorhergehenden Zeitpunkt für Klein T minus 1 zeigen 1. auch optimal war und wie gesagt wir machen diese
Berechnung immer für alle kleine x 10 x kleinen T die in der jeweiligen Zustands Menge die zulässig ist drin sein und Jahr das ich sage ab diesem Zeitpunkt t also für T +plus 1 und alle weiteren soll gelten das hier schon die optimale Strategie mit der durch den GP Algorithmus gefundenen Strategie übereinstimmt beziehungsweise der Wert davon falls sie 2 Strategien hätten die sozusagen zum gleichen Wert Filmemachen Zeit nicht an der Strategie an den y werden fest dann wirklich an der Auswertung der Zielfunktion am Wert Hilfe an ich kann gut was wir zeigen wollen dass dann auch für den Zeitpunkt vorher also wir gehen davon aus dass das T +plus 1 geltendes wollen für den vorhergehenden Zeitpunkt zeigen dass es auch stimmt wer was es unser optimale hat Moment ich brauch als man bisschen Notation ok also ich nenne meine Teilstrategie einfach da kann ich den 1. werden wir praktisch rausholen und in dieser Kette dahinter steht die Teilstrategie ab Zeitpunkt die +plus 1 das ist aber nur dass ich mir das den Kopf den 1. nächste Strategie Schritt mehr rausholen kann ab und die warm spielte ich jetzt das alles so auffällig möchte den vorhergehenden Strategie führt mehr anschauen da die andere Teilstrategie bereits optimal war verwende ich die die hintere von der ich diese Annahme gemacht hat dann hab ich hier den Endzeitpunkt hier den Teil der durch die alte Strategie abgedeckt ist und hier ist nur der eine Schritt der von meiner Entscheidung die Kosten von meine Entscheidung jetzt gerade abhängen gut dann wissen wir ja wie gesagt was sich sachte mit dem Prinzip der Qualität dass diese Entscheidung unabhängig ist von dem was wir vorher passiert das also kann ich das weiter auseinander ziehen nach diesem Prinzip der Optimalität der und hab eigentlich als Optimierung wirklich nur noch im letzten Schritt es bleibt einfach und unterhalten dann wäre ich jetzt mehr das Minimum über alle möglichen Teilstrategien ab dem Zeitpunkt die +plus 1 Moment den Kunstlicht nicht oft na ja das was hinten rauskommt sollte auf jeden Fall in der optimal wir vorher schon hatten also das y Stern von XT der x-te +plus 1 und das was der vorne kriegen bleibt einfach da und das wissen wir aber hinten über über diesen Wert mehr nach unseren Options Annahme mussten und entspricht das den Wert den wir aus der dynamischen Programmierung erhalten haben aus dem Algorithmus Na ja und das was hier es ist genau der Schritt über der dynamischen Programmierung als genug C als Rekursion Schritt sozusagen steht kriegen wir hier genau den Wert der dynamischen Programmierung zum Zeitpunkt X T heraus und damit wissen das der optimal Wert im Sinne davon dass wir hier über alle möglichen Strategien minimieren derselbe ist den wir auch bei der dynamischen Programmierung erhalten so war und damit das nicht ganz so Na ja luftleere steht wollen wir jetzt 2 Beispiele anschauen ich möchte mit dem 2. Beispiel anfangen von den beiden weil das in der Notation wirklich ganz genau übereinstimmt mit dem was wir hier verwendet haben das ist das über die die 0 1 Rucksäcke bei den kürzesten Wegen kann ich gleich vor der passt die Notation nicht ganz weil da fangen wir in Wahrheit in der Notation die sie da gewählt das halt doch vorwärts an was aber an dem Optimalität Prinzip der Teil wegen dem keinen Abbruch tut aber das immer danach hat ich mich mehr Smiley Tafel damit ich sinnvoll Platz hat für das Beispiel das wird werden mit und ok es ist nicht immer ganz einfach sich klar zu werden wie man sein Problem in dieses Setting überhaupt ein bekommt ja das ist nicht ganz intuitiv unbedingt wie man das übersetzt von seinem IP Problem in dynamisches Programm deswegen ist es so dass wir für die Übungen auch erst mal einfach die Beispiele wie ich ihn jetzt gebe ohne ein konkretes mit Zahlen ausgefülltes Beispiel zu rechnen sein einfach erklären wie man das in das dynamische Programmen übersetzt sehr genau die auch in den Übungen einfach mal an einem konkreten Beispiel machen lassen man bisschen Gefühl dafür kommt bekommt die dynamische Programmierung einig arbeitet die also wir stellen uns vor wir haben 1 0 1 Rucksack n das Problem kennen man möchten irgendwie den Wert der Gegenstände die Wärme Rucksack mit nem maximieren und wir haben eine Nebenbedingungen
nämlich dass wir unseren Rucksack mich über fehlen dürfen und da ich ich hab gesagt wir 1 Rucksack das soll heißen dass ich pro gegen steh also 7 Gegenstand nur einmal zur Auswahl haben ok GB ist das für uns n den Rucksack befüllen dann verändern wir praktische eigentlich sein Volumen nur setzen hier in eine Variable auf 1 und damit ändert sich wenn wir das auf die rechte Seite bringen die Kapazität unseres Rucksacks das heißt dass könnte oder ist für diese Übersetzung die Zustandsvariablen die sagt uns wie viel Platz es gerade noch in meinem Rucksack jetzt ist die Frage was sollen Steuer Variablen sein mehr Steuern es genau richtig neben einen Gegenstand mit dem man Rucksack oder ich nehme nämlich mit 10 hab ich die Variablen hier auch nicht X genannt beziehungsweise sind denn es gibt ich X genannt sondern gleich y weil das eben genau die Steuerungs Variablen sind hier und sagen wenn Gegenstand mit oder nicht und wie häufig kann ich höchstens etwas mitnehmen ja ich könnte falls dieser Oper falls diese Nebenbedingung praktisch keine Restriktion darstellt alle Gegenstände mitnehmen dann wäre mein Endzustand praktisch das was noch übrig bleibt im Rucksack an Kapazität und deswegen diese diese lebt diesen letzten Schritt dass sich packt Schauer wie viel hab ich übrig nachdem ich mein Rucksack optimal gefühlt habe das mache ich zu meinem Endzeitpunkt wenn ich gucke was bleibt mir noch übrig an Platz und am Rucksack deswegen auch ich für jede Variable wie ich zu nehmen kann einen 2. Schritt also Endzeit Schritte für jede für jeden Gegenstand zu prüfen ob ich denn mitnehmen oder nicht und einen zusätzlichen Zeitschrift war ich mir ein damit ich am Ende schauen kann wie viel Platz hab ich noch immer im Rucksack weil das mein Endzustände sind sich schon noch wie viel Restkapazität ist in Hamburg sagt man dann schau ich zu jedem Zeitpunkt wie viel hab ich zu diesem Zeitpunkt noch in meinem Rucksack übrig am Platz wenn die YJ die Entscheidungs Variablen darüber welches gegen welchen Gegenstand nämlich mit sind in diesem Fall meine Steuer war Abenden hab ich also schon alle alle meine Variablen definiert aber ich muss mir noch überlegen wie die funktionale Abhängigkeit die ich brauche um in einem Folgezustand zukommen aussieht ja und dieser einfach sein ich hatte eine Restkapazität zum Zeitpunkt J und wenn ich im Zeitpunkt der +plus 1 schauen wir wie viel ich da noch übrig aber hängt das davon ab ob ich mein YJ dass ich gerade betrachtet hab Unternehmenssteuer variable mitgenommen hat also zieh ich eben genau je nach Variablen von der Kapazität des Rucksacks das weiß ich noch dazu eingepackt habe aber gelange so in meinem nächsten Zustand was wieder die Restkapazität zum Zeitpunkt der +plus 1 anderer dann wie komme ich mit dem Steuer Variablen also die Steuer Variablen sind ja die die mir die Kosten verursachen ja und da hängt meine Funktion gar nicht von X ab sondern ich hat einfach nur Kosten wenig ein Gegenstande man Rucksack dazu Parker ja das ist also falls sich zum Zeitpunkt J die Variable ja ein Packer bei folgender Restkapazität dann hab ich einfach diese Kosten nicht zu erklären wie sehen und so zulässigen Mengen aus ja jedem Zeitpunkt kann ich im Rucksack entweder gar kein Platz noch eine 1 Platz haben bis zu höchstens viel Platz was meine rechte Seite war und am Anfang möchte ich eine wirklich den vollen Rucksack zur Verfügung haben ist die Frage welche Restriktionen hab ich in meine Steuer variabler ja ich kann ein Gegenstand nur einpacken als zum Zeitpunkt eines vorher das einen Druckfehlern Skript hat zum Zeitpunkt eines vorher die Kapazität noch groß genug war das sich den Gegenstand J überhaupt noch einpacken kann nur dann darf ich hier 1 werden logischerweise ein und 0 sonst aber es ist klar dass unsere Entscheidung ob wir denn Gegenstand einpacken in einem Rucksack einer bestimmten Größe unabhängig ist ob das von der Warte der Variable der Restkapazität 2 aber genau zum Zeitpunkt der -minus 1 oder sonst irgendwann das also hier ich hier stehe besteht ja praktisch Unabhängigkeit das meine zulässigen Werte für meine YJ variabler der in der Form von meinem Zustand wenn es vorher abhängen dass es aber für für den Verlauf des gesamten Algorithmus einfach nicht also es macht die das Prinzip der Optimalität nicht kaputt weil die Vorentscheidung M ok also für diesen für diese Restkapazitäten den Sinn so nicht die Rolle spielt ja das ist einfach das funktioniert einfach alles weiterhin so wie wir das haben wollten mit dem Prinzip der Optimalität gut und wie sieht jetzt möglich das dynamische Programm brauchst ja eigentlich bräuchte es wird sich noch mal genau schreiben eigentlich steht nämlich schon hier unsere Zielfunktion wird hier einfach aufsummiert über die Zeit außer dass wir die Kosten im Endzeitpunkt gleich 0 sind denn dem Endzeitpunkt ist umso Zustandsvariablen einfach nur die Restkapazität am Ende der Befüllung des Rucksacks dafür bezahlen wir natürlich nichts mehr wenn wir da noch Platz und übrighaben dann entstehen und dadurch keine Kosten mehr also geh groß von X Großzeh mit gleich 0 sein die aufsummiert ergeben die die Zielfunktion meine Übergangsfunktion sich hier um eine zulässigen Mengen hab ich ich auch das denk ich noch mal untereinander schreiben die spannende Frage ist jetzt wie sieht der Algorithmus aus und wie kann man da die wiederfinden das wirklich Teillösung genutzt werden nein also für jede beliebige recht Restkapazität zum Zeitpunkt n +plus 1 zahle ich nichts weil das ist genau die Restkapazität meines Rucksacks Martinichen fertig gefühlt haben jetzt ist die Frage was mache ich mit dem Rucksack der zum Zeitpunkt I noch des Restkapazität des hat ich und hier steht jetzt ein letztendlich
genau den -minus A E y e u vor und das hier ist praktisch der Wert denn nicht mit allen vorhergehenden Steuer Variablen noch erreichen kann wenn die Restkapazität zu dem Zeitpunkt ja +plus 1 nur noch so viel wie hier was dem entspricht das sich hier diese Variable Benutzer in zum Zeitpunkt I ich wer und das sind genau die Kosten wenig im Wege stand ihm mitnehmen guten wie wird sich dieser wie wird dieser Rekursion sich auswerten wenn ich sowieso mit dieser Restkapazität den Gegenstand ihn nicht mehr mitnehmen kann das ist klar das ist einfach der alte Wert des Rucksacks bleibt völlig im Rucksack nichts Neues mehr da einpacken können n und selbst wenn dieser Gegenstand noch in den Rucksack passt also wenn meine Kapazität noch ausreicht um Gegenstand ihn mitzunehmen muss sich immer noch entscheiden ist es lukrativ für
mich oder hab ich eine Befüllung jetzt schon gegeben die besser ist als würde ich den Gegenstand mitnehmen und dann die optimale Befüllung mit den weiteren späteren Gegenständen anschauen muss man sich so vorstellen wenn ich praktisch mein Rucksack schon zur Hälfte gefüllt hat und ich Frage mich bringt es mir was mit der anderen Hälfte jetzt noch Viertel vollzupacken dann kann es sein dass der Wert den ich dann bekomme wenn ich diesen Gegenstand man nehme schlechter ist als denn wenn ich ihn mit den vorhergehenden Gegenständen schon so gepackt hat dass er das optimal war eben eh wie lange ich hoffe dass das wenn Sie das Beispiel wirklich auswendig ich meinen vielleicht gleich nochmal ungefähr die Tabelle an wie das wie das sich gut am aufschreiben lässt ich denke dass die Beispiele der Übung gar groß Erhellung bringen werden das hier und habe keinen Platz mehr gelassen sollen meine Gegenstände und die Restkapazität dich übrig hat noch das mag die Runden durch die ich mein ja durch schicke ja ich fang mal n +plus 1 geht zu allen und die weiter bis zu 1 bis sich alle Gegenstände sozusagen ausprobiert habe und dann welche verschiedenen Zustände kann man Rucksack haben na ja wir haben gesagt gut wir haben gesagt werden wie die jeder Zustands Menge kann die Restkapazität vom Rucksack zwischen 0 und sein also muss sich hier immer wenn das ihres kann es sich zu kann was sich hier die von 0 betrachten mit Yvonne 1 es von W ich bin das sind die Werte ich mir anschauen kann ja und ehrlich gesagt am Anfang die Restkapazität vor sagt mir keine Kosten sag ich jetzt meine ganze teilen oder stehen und hier fängt zum 1. Mal Anlass zu passieren ich überlege mir kann ich den Gegenstand Ende mitnehmen und da steht dann falls meine Restkapazität groß genug ist also als des größer als des was der Platz ist den Gegenstand allen in der Runde einen verbraucht man muss sich entscheiden ist mein Werte höher als der Wert den ich schon hatte Freunde in meinem Rucksack oder nicht den Gegenstand mitnehmen und das werd ich im Anfang zu schauen und in welchen in welchen Rucksack passt der Gegenstand schon einmal einen Rucksack der nur Kapazität hat wird niemals ein passt mir bedeckt über die Spalte 0 bleiben aber keine Ahnung ob irgendein Zeitpunkt mit dann vielleicht reinpassen man hat hier mein Rucksack Wert CNN weil ich diesen Gegenstand eingepackt hat im Verlaufe kann aber passieren dass sich hier einen höheren Wert dadurch bekomme dass ich nicht die letzten Gegenstand einer vielleicht den 3. Gegenstand gewählt hätte ja dass dieser zwar den Gegenstand der Größe 5 passt nun mal in Rucksack der größte 5 aber wenn nur eines Wertes und Gegenstand der größte 3 27 Werthers wendet sich das hier im Laufe durch diese Rekursion eben verändern einfach nur damit Sinnbild haben welche Tabelle sie vielleicht auch Einigung der Sinne verarbeiten können ja gut dann machen wir jetzt die Pause nach der Pause gibt die kürzesten Wege gut wenn man uns jetzt noch das Beispiel
anschauen wo wir kürzeste
Wege n dynamisches Programm übersetzen wollen und jetzt wie gesagt von meiner Seite der Vorkommentar hier ist praktisch ist trotzdem so dass wir von je 0 und nicht von der Brust T ausgehen und dann weiter rechnen was aber dem System das Lösung verwenden Gesamtlösung zu konstruieren kein Abbruch tut es schreiben beschreiben wir die Rekursion erstmal allgemeinen erst dann in dieser dynamisch Programm Notation hingeben Sans eingerichteter Graph mit nicht negativ und gewichten dann kann und Gewichte die größer gleich 0 sind und wir suchen von einem bestimmten Knoten es aus kürzeste Wege zu allen anderen Punkten die in unserem Grafen haben dann ist es so das wir so jeweils einen kürzesten Weg wie auch immer der gehen mag nutzen eine bestimmte Anzahl von Knoten unterwegs wären wir haben ihren Weg bin kann ich auch darüber charakterisieren dass sich die Folge Der Knochenmann Schauer der kleine Länge von diesen Weg und über diese länger diese Wege mach ich praktisch meine Rekursion darüber wie ich einen kürzesten kürzesten Weg mit höchstens K +plus 1 Knoten aus am kürzesten Weg und höchstens karg muten wir konstruieren oder so wenig mit DKE die Länge des kürzesten
Weges zum Knoten Yvonne es ausgehend über höchstens K Knoten
nur dann gilt die folgende Rekursionen man also wenn ich für einen Knoten J entscheiden weil was der kürzeste Weg ist der über höchstens K Knoten läuft dann kann es sein dass ich dadurch dass ich einen weiteren Quoten wie die Möglichkeit gebe über einen weiteren nun zu laufen wir ja nichts schenken gar keine kürzeren Weg der machen kann das heißt es kann sein dass ich trotzdem weiterhin nur über höchstens kann -minus 1 Gronau weil der Weg so einfach schon gut gewählt war andernfalls schau ich mir Wege zu angrenzenden Knoten VJ soll heißen dass sie benachbarte C JS in meinem Grafen des schau ich mir wegen der Länge höchstens kann -minus 1 Knoten auf dem Weg an bis zu einem Clooney und geht den letzten Schritt bis zum einen J zu gehen möchte ja wenn ich hier mit etwas Besseres erreichen hält sich hier schon bekommen haben über ihr das 1 Knoten zu laufen dann würde ich das wären in Summen Grafen lohnt es sich halt nicht zum Klonen 2 über 2 kann zu laufen weil es teurer wäre dann würde es mir sagen ok für meine angrenzend wurden von wurden 2 was sie entweder 1 oder 3 sind aber 1 da hab ich ja keinen Weg bin ich bisher gehen Mostar schau ich was kostet das nicht hier laufen 1. kostet mich 5 aber der Weg der Länge 1 kostet hier schon 3 dass macht insgesamt 8 was natürlich mehr als 2 wo ich nur eine Kante ich habe ich aber genau so man es sich hier 8 bezahle wenn ich direkt zu und 2 Laufer dann wäre in diesem Fall genau hier das Minimum kleiner nämlich ich schau mir zuerst ein mit der Länge 1 zu 1 an Grenzen Knoten an wir dann die letzte Schritt über die neue kannte C J ja das ist der neue Knoten das wäre mein Beispiel hier praktisch die 2 wie wäre drein ja aber das ist genau das Gedicht was durch ihren stehen hast verstehst du das ist ja genau der die länger also nach unserem Notation die Länge des kürzesten Weges über so und so viele Knoten bis zur diesen vorhergehenden Knoten und das ist praktisch genau dieser Weg da muss den muss sich ja schon gegangen sein mit einer Kante hier in diesem Beispiel also wirklich nur ganz ganz klein und bisschen zu veranschaulichen wo diese Rekursion herkommen eine Sache auf die man vielleicht aufmerksam machen kann ist was passiert denn also wie lange kann ich ja wir eine ziemlich starke Voraussetzung gemacht das ich nur positive kannten Gewichte zulasse in haben trafen ja das ist ja irgendwie schon starke Voraussetzung ab wann geht man denn diese Rekursion hier kaputt wer wann kann ich nicht mehr dadurch dass ich längere Wege sozusagen Wille da garantieren dass ich dann immer noch das mögliche Minimum rauskriege wie bitte ja nicht zu groß sein so wenig anfangen kann zu kreisen und negative Kosten hat und sozusagen dadurch sich immer weiter einem Kreislauf oder ein negatives Gewicht hat mein Weg immer immer kürzer machen könnte wo ich da sozusagen mehrfach Langlauf ja er soll das das ist das die Abschwächung ließ sich könnte zwar vielleicht nicht unbedingt nur nicht negative kannten Gewicht zu lassen sondern auch allgemein hatten nicht aber dann bräuchte ich mindestens noch die Voraussetzung dass ich keine negativen Preisen negativen ich das hätte gut aber so viel erst mal nebenbei das ist also der Größe und von den Fall die funktionierten jetzt wollen wir das wieder in unser dynamisches Programm übersetzen wer wie viel Knoten kann ich also noch eine Anmerkung ihnen wenig das ist ja eigentlich schon so wie es da steht ein Algorithmus der eigentlich steht hier genau das was ich tun muss jeweils sie schauen einfach erst mal wieder der Länge 0 dann der Länge eines an kann hierüber die Rekursion Aufschrei meine ich brauch ich das dynamische Programm das wird erstmal nur wirklich für uns zur Übersetzung wie man das aufschreiben kann welche Laufzeit hat dieser Algorithmus ja ich muss das hier für alle Knoten jeweils ausrechnen aber hier betrachte ich jeder kannte im Graph nur einmal weil die ist nicht benachbart weil gerichtete kannten nach also ist sie nicht gleichzeitig zu mehreren Knoten der benachbarte kann scheuen wie an die kann ich zu einem Klon hinlaufen hab ich als Laufzeit von dem Algorithmus erst mal grundsätzlich mal einen also Knoten markanten viele Schritte muss ich machen für jeden Knoten muss dies ausrechnen und in jedem Schritt berechne ich hier aber höchstens M er schau ich mir höchstens kann man in diesen Verein gut da jetzt aber zur Besetzung kann über höchstens ein Knoten laufen bei mir hab ich und auch nicht zur Verfügung so in meine Zustands Menge packe ich mir einfach genau die Wege die ich gerade ja sich merk mir praktisch welchen Weg ich mit einer bestimmten nun Anzahl bisher gewählt hat und zu einem zu einem Knoten zu gelangen
nein mehr eine Steuerung muss der darauf folgende Quoten sein dass ich mir einfach überlege welchen Quoten hänge ich praktisch in meinen Weg an um ihn zu verbessern oder eben aber auch nicht also kommen eine störungsfreie haben aus V das heißt nicht dass ich in jedem Fall mein Weg um eine um einen Knoten verlängere ich kann als Steuerungs Variable für einen Weg PJ auch einfach den Knoten J hier wählen was so viel hieß wie bleib einfach in diesem klonen der Weg wird nicht besser dadurch dass sich eine Kante der zufüge die das war das was ich meinte also falls sich hier an den per meinen Lymphknoten werden nochmals versuchen Notenwert nochmal versuchen würde anzuhängen ändert sich der Weg einfach nicht und das ist ich hab den Lernweg falls es den Übergang einfach nicht gibt also falls sich praktisch 1 zu unzulässiger Aussage macht dass ich versuche ein Knoten an einem vorhergehenden Weg Anzeigen der gar nicht auf dem Weg verbunden ist da hab ich auch vergessen dass der Zustands Menge auch der Lehrer weg ein Teil sein muss das sind die Kosten mehr wenn ich hier wirklich eine weitere Kanten zu nehmen dann sind das genau die Kosten für diese kannte seit dem geraten ist wenn ich mich nicht weiter bewegen mein Weg ist es klar dass ich noch keine Kosten haben und ich möchte natürlich unzulässiger Steuerung also unzulässige Folge Knoten möglichst harten Strafen sei wenn also ich mich in meinem eigenen wurden bleibe oder einen kannte Canterville wie möglich im Graben existiert wird sich meine Kosten auf unendlich so und jetzt kommt das dynamische Programm was ich mich der 1. machen wollte weil es ihm nicht ganz zu der Notation passt wie wir sie gewählt haben wir sagt mir eigentlich dass wir zum Zeitpunkt groß The anfangen aber ich kenne keinen Weg der über einen Klon geht und der kürzeste Weg ist bin kann ich nämlich aus der aus der Tüte zaubern ich hab einfach nicht die kürzesten Wege über einen Knoten vorhanden sondern die Rekursion funktioniert eben hier genau andersrum rum das ich mir zuerst kürzere Wege anschauen muss also ich wenn ich praktisch über keine weiteren Proben laufen kann dem kann ich nur die Kanten entlang laufen die aus meinem Quoten es wirklich herausgehen also ist der Wert CSE von erst zu diesem Knoten nie weit diese kannte im Grafen existiert von erst nach wie und für alle anderen Klonen meinen Raven setzt sich den Weg den ich über 0 Knoten zu diesem Knoten es vom kommen 1. Sinfonie reichen und auf bloße endlich völlig einfach noch keine nicht habe ich habe gesagt wir brauchne Lernweg der soll auch Kosten unendlich haben gut dass eigentlich genau das was mit dem des steht ich nehme hier die Kosten für eine Kante nicht zusätzlich verwenden zu und schau mir den Weg an der 1 kürzer aber aber ok hab ich meinen besten Weg nein 1 die Längen über T minus 1 Knoten wenn der hier besser ist als den ich erreichen kann an Tschulligung ich einen angrenzenden Knoten und ein hinzufügen nämlich bei dem bleiben wenn beide sowieso plus unendlich sein dann soll dich auch also das einfach nur Alibi mäßig dabei dann die wertet sich das jeweils aus den Übergangsfunktion Mhm zwar nicht gut das sie ein an wurden mir sagte einfach nur wenn ich hier in der Bewertung von meinem vorhergehenden weg hier den besseren Weg schon mit T minus 1 Schritten erhalten habe und bleibt man Weg so wie er war um einen Fall muss sich die denn PJ Weg den kürzesten Weg abdecken dazu dass sich eine alten P i zu einem Vorgänger Knoten nehme weil es besser war und dann die kannte dich verwendet habe neue und zum Blunier zu gelangen zufüge gut wie gesagt hier ist es einfach so dass wir das Obst nicht rückwärts Hinschreiben sondern vorwärts aber die Rekursion sich ich glaub da hilft einfach nichts das Ursprungs die Ursprungsidee in Erinnerung zu rufen ist eben genau so eine das sich aus Teil wegen optimale gesamt Wege zusammensetzen kann in meinen Weg bis zum Knoten i eben kürzer war auf meinem Weg auf meinem Weg zum insgesamt Knoten J als der gesamte BCJ mit der letzten Kanther dann muss ich das eben so updaten dass ich diesen Weg verwenden gut so viel zu dynamische Programmierung das ist das was sie diese Woche in den Übungen sehen werden das steht jetzt im Skript offiziellen Kapitel 5. Punkt 3 über Primal mit hohen das ist aber noch nicht so weit ausgeführt dass ich dazu was erzählen könnte es gegenwärtig das für nächste Woche einen Martin überlassen und wir schauen uns jetzt einen 1. Einblick in Approximation sei wurden an wir haben ja jetzt zwar exakte Verfahren kennen gelernt sie wissen entbrennt Unbound bauen mit dynamische Programmierung Ende sowas machen können also wenn die Bahn keine grundsätzlich immer machen die Frage ist wie weit kommen wir oder wie groß wird mein Baum wenn ich das Problem immer weiter aufteilen muss schaff ich denn wirklich komplett abzusuchen sind meine meine Schranken wie ich finde so dass ich den so klein halten kann dass sich das wirklich scharf oder schaff ich's eben nicht und bei dynamische Programmierung ist eben die Übersetzung das was man erst mal hinkriegen her diese Verfahren habe ich aber oft ist man schon zufrieden wenn man sagen kann dass sich eben nur so und so viel schlechter werden als die optimale Lösung und solche Algorithmen die eine Art Zertifikat haben wie gut sie wie nah sie an der optimale Lösung sind die nennt man Approximation sei worden der Menschen viele Algorithmen in dem Heuristiken Kapitel kennen gelernt die ihnen Lösung liefern ja da haben Sie zumindest schon einmal eine Lösung aber Sie können in dem Fall nichts darüber sagen wie gut die ist sie haben eben keinen Goethe Zertifikat für diese Lösung und was man versucht es eben immer noch Heuristiken können das ruhig sein zu finden bei denen man aber nachweisen kann dass er ihrer Lösung nur zu einem gewissen Prozentanteile Zahn gewissen Grad schlechter ist als die optimale Lösung ich war ja ab ein wir wollen also das soll so sein dass wir das natürlich eben beweisen können wollen dass die Lösung wie unser Algorithmus und für ein Optimierungsproblem aus spuckt nicht schlechter ist um zu wissen wobei wir hier überhaupt wir reden wollen das vermissen Notation einführen und erst mal zur Erinnerung man kann jetzt Laufzeiten immerhin Kodierung Sleng von dem Problem ja also man schaut sich man hat das Optimierungsproblem in eigener Form c't iX Eicks =ist gleich b gegeben und um Laufzeit von einem Algorithmus der dieses Problem löst zu beurteilen schaut man das immer polynomial in der Kodierung es länger dieses Problems an ja nur zur damit man das wieder beißt wenn ich mit Pierson diskretes Optimierungsproblem notiere dann meine ich damit die allgemeine Problemstellungen zum Beispiel kürzeste Wege oder Rucksack Problem ja wenn ich dann schreibe I aus P mein ich nehme eine Instanz von diesem Problem als ein konkretes Rucksack Problem er also ich kopiere praktisch meine Probleme hier an und für jede Instanz also der Algorithmus funktioniert für die allgemeine Problemstellung und für Instanz liefert der eben einen Wert mehr also ich habe den optimalen Wert und ich möchte jetzt dazu den wer hat dem denn der Algorithmus gibt vergleichen ich zurück ich habe mir Folgendes n ab gut an sich nennen so ein Algorithmus Erzählern Approximation Algorithmus nur dann wenn er erstmal polynomial Laufzeit hat weil was bringt man Algorithmus von dem ich nicht weiß ob irgendwann fertig wird und gleichzeitig sagt dass bei einem Minimierung Ess-Probleme ich höchstens Epsilon dass das Endziel entfachte dieses ein wurden aus dass der optimale Lösung herausbekommen bei einem Algorithmus Oberärztin 1 logischerweise etwas ist das größte Heinzes wenig minimiere und wenig maximiere genau anders rum setzen und kleiner gleich 1 und dann dass sich so viel unter der maximales und ihren ja so wenig Maximierer kann aber wohl nur macht sondern dass ich wenn ich eben minimiere das ist klar dass sich was größeres bekommen will mit irgendeiner Form von heuristischen oder wie auch immer prima dem Algorithmus und wenn ich maximiere eben entsprechend höchstens mehr wir wir die wird Jay werden gut hier ist das sehr einfach so dass meine y für den Algorithmus festgelegt ist ja ich sage also der kann mir höchstens bei einem in den Währungsproblem doppelt so viel ausgeben oder so wenn man entziehen und 2 wären es gibt aber auch Varianten wo ich mich einen konkreten Algorithmus habe seinen in Approximation Schema was sich in gewisser Weise anpassen kann und wo ich sagen kann wie genau möchte ich dass du approximiert ja hier ist der 1. der Knackpunkt der sich für jedes Fest der y sind n der das sagt mir praktisch dass sich in meinem Algorithmus Nonne Stellschraube haben den sagen kann wenn du weitermachst in den davon lokale Suche oder was weiß ich dann weiß ich dass zu sogar diese Garantie erreichen kann sich keinen praktisch vorgeben wie weit ich möchte dass er schaut so wie nahe er an die optimale Lösung anlaufen soll und hier sind wir immer noch polynomial nur eine Eingabe Größe wie wir n war das Ruhrgebiet hier sag ich erstmal nichts darüber was es mich kostet das sich das Epsilon verändere ja dass sich hier ein besonders gutes Epsilon das hat erst mal keinen also interessiert mich nicht ob das Einfluss auf meine Laufzeit hat hier mache ich die zusätzliche Einnahme das Gesetz in allen in der Form in mein Laufzeit eingeht ja das heißt wenn ich dann besonders gutes erzählen aber einsehen möchte das sich da in der Laufzeit eben auch was dazu dass sich Auswirkungen zu erwarten habe sowieso aber dass sich geben beschränken gewisser Art und Weise Ängsten dass die Laufzeit hier nur in höchstens 1 durch Epsilon in polynomial in diesem einst durch y und ich ihn als man selbst sein kann das Satz das man ansonsten NP Probleme auch in Pilsen lösen könnte aber ich glaubte dass ich trotzdem ein Martin am Montag machen
Länge
Dynamische Optimierung
Dynamik
Optimum
Entscheidungstheorie
Computeranimation
Index
Variable
Menge
Zustand
Vorlesung/Konferenz
Zielfunktion
Schranke <Mathematik>
Nebenbedingung
Momentenproblem
Dynamik
Dynamische Optimierung
Minimierung
Berechnung
Optimum
Zahl
Variable
Menge
Kettenregel
Minimum
Rekursion
Zustand
Strategisches Spiel
Vorlesung/Konferenz
Zielfunktion
Optimierung
Nebenbedingung
Variable
Rekursion
Vorlesung/Konferenz
Zielfunktion
Volumen
Optimum
Restriktion <Mathematik>
Entscheidungstheorie
Menge
Tabelle
Rundung
Rekursion
Zustand
Vorlesung/Konferenz
Weg <Topologie>
Länge
Punkt
Gewicht <Mathematik>
Graph
Dynamik
Rekursion
Besprechung/Interview
Vorlesung/Konferenz
Länge
Punkt
Gewicht <Mathematik>
Gewichtete Summe
Dynamische Optimierung
Graph
Minimierung
Laufzeit
Heuristik
Optimierungsproblem
Kante
Gradient
Variable
Quote
Menge
Rekursion
Minimum
Zustand
Vorlesung/Konferenz
Schranke <Mathematik>
Klon <Mathematik>

Metadaten

Formale Metadaten

Titel Exakte Verfahren II: Dynamische Programmierung, Anwendungen Approximationsalgorithmen
Serientitel Diskrete Optimierung (Optimierung II)
Teil 20
Anzahl der Teile 26
Autor Nowak, Nicole
Martin, Alexander
Lizenz CC-Namensnennung - keine kommerzielle Nutzung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen und nicht-kommerziellen 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.
DOI 10.5446/31810
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2009
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...