Merken

Ein FPAS für das Rucksackproblem

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
P-Wellen lud ich nach Eck er sich willkommen zur
heutigen Vorlesung der Herr Matthes heute verhindert dass im Grunde wenn ich die Vorlesung halten sie hatten ja in der letzten Vorlesung über Approximation Saarbrücken gesprochen insbesondere im über 1 Gerling Problem welches dann am Ende mit dem randomisierten Algorithmus nur 1 Komma 5 8 Performance Garantie geliefert hat was uns heute angucken wollen ist ein anderes approximiert an einer als eine Approximation es also wird man für das nun ein 0 1 Netzwerkproblem Rucksack Problemen und das er sein die Pollen wird einmal Volksmärchens gehen und ich möchte ganz gern am Anfang erstmal über die Motivation im sprechen wie man eigentlich auf die Idee kommt in Approximation es Algorithmus in der Form zu modellieren zu Design und 2 ist also bei den 0 1 zu Rucksack Problem Hammelburg sagt der Länge bei der größte wählen und wir haben Elemente DE verschieden viel Platz benötigen das ist sollen wird wollen 3 und die danke zusätzlich zu den Platz noch verschiedene Kosten haben C 1 C 2 und C 3 und wir möchten jetzt sollen also möchten dessen Rucksack so parken dass die Kosten minimal maximal werden je nachdem wo Sozi Funktion gewählt haben ja also finde optimal ist eine optimale Konfiguration oder ist also mal der Scenic IX ihm von mir maximal wird ja möchten also dieser diese Gewichte oder diese Gegenstände der Rucksack packen wir möchten die Objekte auswählen die dann unser Zielfunktion maximieren Herr Sorge haben auch schon gesehen dass wir das ganz mit einem mit Problem löst dann geht das ganz O von nmal des Bubi wobei die die größtes Rucksacks ist und was man sich es überlegen kann ist dass wenn wir viele viele weit sind haben die wir in den Rucksack packen wollen also eine große Liste von diesen Elementen dann können uns auf 1. mal auf die Elemente konzentrieren die sehr hoher den sehr hohen Nutzen für uns bringt also die bei der Maximierung von dieser
zieh Funktionen möglichst wie Beitrag liefern können deren sogar mal so verschiedene Elemente die wir Rucksack packen wollen und teilen jetzt diese Elemente in 2 Mengen auf zum Beispiel so und so und das sind die Elemente denn in große Szene haben und das sind die Elemente mit dem kleinen wer ja ich hab also dieser Elemente die den Rucksack packen möchte ich damit sie eben Element die Kosten oder den Nutzen an der dieses Element mit sich bringt und detailliert in 2 Mengen auf einmal die gegen kleines Szene haben das sind die rechten einmal die den großes sie haben und die die es jetzt die das 1. mal versuchen möglichst optimal die mit dem großen Zeh zu packen und wir da noch Platz über haben dann irgendwie den Rest verpacken und das verpacke es 1. macht man normalerweise mit dem Prix Algorithmus und dann schätzt man hat das dann die Lösung immer rausbekommt nicht zu schlecht ist und für den für diese großen Elemente benutzt man eine mit Problemen ja das und wird dann so man hat üblicherweise das ist einig das Vorgehen auf fast allen Approximation SWR geritten 2 Parameter S und T der Parameter S der mit dazu benutzt um die Kodierung muss länger von diesen Elementen CE zu verkleinern ja Herr das also eine Approximation der Codierung der C da ich vielleicht außer zu es Teil Detail funktioniert um das geht es einfach nur die Grenze die definiert was groß und klein ist ja wann mit dem sie mit dem T 1 das ist das einfach also diese Unterscheidung ist groß kleines funktioniert so über haben 2 Mengen wenn wir die eine einfach mal groß das sind alle I in Ehe n n so das C größer gleich TS und die kleine Elemente sind genau die Elemente oder ist sie kleiner als das ist ja nicht Teil also wirklich einfach meine meine eitel muss anhand dieser Zeit auch alle die größer als die sind das sind meine großen Elemente für die ich möglichst optimale lösen möchte und alle die die kleinen sind dessen die kleiner als die sind immer dem wie Algorithmus in machen um es ist aber so dass diese Elemente CID groß sind unter Umständen recht große Kosten haben können und uns überlegen wie der Greedy Algorithmus funktioniert aber wieder das damit Problem funktioniert wenn es so dass die Laufzeit von den deine mit Problem Linie 1 B ist das wie ist die größtes Rucksacks was es also machen wollen es wir wollen im Endeffekt dass es dazu benutzen um diese Kostenstruktur zu verändern werden das also das ist hier T benutzt was mit dem 1. macht ist folgendes man guckt sich die Kosten an oder auch andere Parameter 1 Approximation es Problem die durch das es und rundet das ab damit approximiert ich sozusagen die Kosten der Welt das ganze Ziel damit es multiplizieren würde ich nur Vielfache von es betrachten ja aber kann das also so vorstellen ich wäre ein 1. Beta ist S 4 S 2 S 3 S und so weiter und so fort und ich teile meine Kosten immer zu diesen Punkten zu also Kosten in dem Intervall legen dann nämlich den wir dafür wenn die ich hier liegen dann nämlich den Wert und man hier liegen dann nämlich den Wert um das genau was diese Operation macht beteiligt es schneide fraktionalen Anteil ab dass es nicht genau diese Anteil zum Beispiel hier und da haben wir mal gute Beziehungen mit dem 1. das heißt hier schieben diese Kosten immer zur Linken Grenze der Folter ist etwas wo man macht ist der dass man sozusagen die Kostenstruktur des kritisiert ja das ,komma andere Parameter so zu sein wie wir später sehen werden aber die wer weiß einfach nur diskret kritisieren diese paar mit Struktur in dem wir nur diskrete Werte zu lassen hier Vielfache von S und der Vorteil davon ist das welches es weglasse brauche ich weniger Kodierung Svenja und diesen Parameter darzustellen und damit sind die Algorithmen die in irgendeiner Art und Weise Laufzeit Kodierung Svenja haben schneller und das ist genau das was den Test eine nicht vor dem schnell noch machen und das einig das allgemeine Vorgehen bei einen Approximation so Algorithmen was vielen wir haben Flechten eine mit Problem was das gesamte Problem löst das hat aber der Laufzeit die vielleicht in irgendeiner Art und Weise von der Kodierung Sven abhängt dann teilt man die Input Daten 2 Mengen auf eine die großes ID kleines also die Werte großen sind und wo die Kleinen sind ich es möglichst optimal für die großen Werte lösen und für die Kleingärten mach ich irgendwas ja und diese großen Werte billig eine Approximation so wie hier das heißt ich dich das kritisiert die Kostenstruktur weil dann kann ich mit der Kürzung Gudjons länger arbeiten mehr wenn es im Detail sehen wie das bei dem Rucksack Probleme funktioniert so ha dort aber gut es gibt so werden unsere Inputparameter sind 3 J c J das sind einfach unsere Eingabeparameter das sind also die Größen die Gewichte verbrauchen werden die zu zugeordneten kosten das J ist von 1 bis n ohne Einschränkung nehmen wir an dass die schon vor sortiert sind das also C 1 geteilt durch A 1 größer gleichzieht zweigeteilt ich A 2 und so weiter und so fort es ansonsten wird bekäme die nach und haben der Output
ist der approximative Lösung das Fell eines Rucksack Problem wie gütiger und jedes Algorithmus sprechen wir hinterher weil das hängt ab von dieser Parameter weil es den Tibetern geschickt durchführen müssen da sie noch 2 weitere Parameter das ist es und Tee und das sind wenn einfach mal Approximation Parameter so was den 1. Schritt machen wir sehr schätzen die optimale Lösung ab das von Z wie folgt seit K der maximale Index so das die Summe von mir gleich 1 bis kahl J Vergleich ist der wieder also von vorne durch die Liste durch und packen so viel Elemente 3 wir können wir bevor wir mit einem weiteren Element er wenig zulässige Lösung konstruieren würden und wir definieren jetzt in Scherz dafür die Zielfunktion als die Summe von Jad gleich I bis K +plus 1 eine bittere 1 1 mit mehr rein was man sich leicht überlegen kann erst wenn die Struktur wie hier gewählte ist sprich Fine Art absteigende Kette von Gewichts dichten haben dann ist die Lösung hier besser als die optimale Lösung des EP ist das liegt einfach daran wenn man sich diesen Rucksack vorstellt und dem was wir wollen ihnen das den maximieren wollen ist sozusagen in gewinnen pro Platz in den Rucksack der wenn er es hier verschiedene Fächer haben und verschiedene Gewichte haben die verschiedenen Größen hier in Anspruch nehmen da möchte so Gedichte maximieren und das war der Grund warum man sich diese Quotienten anschaut das heißt wir maximiert also dieser Wert hier ist der in dem wir hier das Element mit der höchsten Dichte Eigentum also C 1 durch A 1 das 7. wissen Platze Anspruch zum Beispiel bis hier das heißt eine sehr hohe Dichte hier es um das Element mit der zweit höchsten Dichte dass es vielleicht hier man schon und es um das Element der Bericht betritt höchsten Dichte und das ragt vielleicht über diese über die Rucksack Christina aus ja und damit bekomme Lösung in jedem Fall eine obere Schranke für die optimale Lösung ist die wir von dem LP erhalten würden das EP würde mich einfach diese letzte variabel hier diese Zuweisung des XI was 0 0 1 1 kann frag zna? wählen und zum Beispiel X gleich nur ,komma 2 wählen das heißt sie würden den Rucksack mit Elementen vor befüllen sodass die Dichte maximales also die Gerichtskosten Dichte damit ist diese diese dieses C 1. wird eine obere Schranke für und so optimale was RTL als Nation sorgen ja jetzt machen wir genau den Schritt den ich oben schon angedeutet habe wir zerlegen Instanz ok und zwar so dass wir uns einmal die großen Elemente definieren zum großen Elemente und wir dürfen die kleine Elemente können so und das kann man vielleicht auch mal jetzt anhand des spezifischen Problem sich kurz vor Augen führen dass immer mehr dieser Rucksack optimal packen wollen wir diese Menge an Elementen in in einmal die große Elementen die kleine Menter aufgeteilt haben dann ist die Lösung Ort des die Lösung optimal die sozusagen ich kenne ich keine einfach mal die optimale Zielfunktion nur für die großen Elemente bestimmen unter gewissen Restgröße dich überlassen Rucksack für die kleinen Elemente dem denen einfach mal des im Moment der und das des ist die Restgröße im Rucksack meine fest der restliche Platz und das D läuft dann natürlich 1 bis B Zeißig ich in den Rucksack nur lege mir jetzt mein Ding ich möchte ich hier eine große Elemente reintun das dafür nicht mehr in Platz von den und das ich für die kleinen Elemente herum da kann ich jetzt Optimallösung konstruieren indem ich mich alle möglichen Wahlen von des Laufer für jedes des die große meinte optimal verpacke und für den restlichen Platz die kleine Elemente optimal verpacke und wie bei nicht optimal für Lösung finden die dabei gewesen ist wo ich das genau so einrichten kann ja welche Optimallösung aber wissen wir dass die irgendeinen Platz für die großen Elemente des und genau für dieses des erhalte ich die Lösung ja das genau wie Instandsetzer zerlegen werden wir gegenwärtig jedes dieser dies durch und Berechnung für jedes dieser die optimale in optimale Lösung für die großen Elemente wir diese Lösung haben versuchen wir dann die kleine Elemente im restlichen Platz zu verpacken und da Lösungen abzuschätzen besonders auch Stars 1. Problem das 1. so Problem Juroren ich Schritt dass man
hier zu sein zu Beginn des Personals so also gelesen dass folgende Rucksack Problemen darüber hat für denn aus gleich 0 bis unseren geschätzten Teilkosten geteilt durch es abgerundet und das genauer das was wir von gesprochen haben über das ganze Problem es wir jetzt schauen ob wir für jeden möglichen Kosten die hier in diesem Intervall liegen müssen ja und es hier ob wir für diese Kosten eine den Rucksack packen kann dass er genau diese Kosten hat genau diese Kosten und dann aber die Kosten jetzt gleich so Runden werden so wie es oben gemacht haben brauchen uns eben halt nur eine kleine Menge an potenziellen Gesamtkosten anzuschauen nämlich genau die Diebe approximiert haben dichtest heimlich essen abrunden das heißt alle möglichen Kosten auftreten können so wie oben die verschieben wir einfach auf diskretes Gitter wir Kokons 0 an diesem diskreten Gitterpunkten die Kosten an und mit seinen hinterher dass die andern kosten wenn sie weiter rechts liegen klein sind Ho er das Siegen ist anders also als das als die normalen Rucksack Problem weil wir jetzt im Endeffekt die Rolle von der Zielfunktion und der Größe der der Elemente vertauscht haben ja normalerweise würde man die Kosten maximieren unter der Maßgabe das ist die Summe des Platzes nicht verbraucht habe kleiner dich PS und hier rechnen alle Problem eigentlich aus über seine Art du alles Probleme wir wollen eine feste Kosten feste Kosten festhalten also die Kosten des und wollen schauen ob wir bei Kosten des den Rucksack noch packen kann oder nicht ja wir gehen also sozusagen über alle möglichen kostet Kostenwerte werde so dass es das Gitter von oben wir haben Kosten nur 1 bis die Abschätzung der Kosten geteilt ich es abgerundet und habe verschiedene Schritte auf diesem Gitter und für sehr Gitterpunkte möchten wir wissen was das wie viel das Blatt über ist also wenig dass sie ausrechne reichen aber Rucksack optimal gepackt bei exakten Kosten des beim beharrlich Platz über im Rucksack bewegen -minus diesen Term um genau diesen Platz wenn es um die kleine Elemente zu verpacken mehr macht na und so er habe da mehr das ich so vielleicht einfach noch einen schon ziehen vorweg warum das Sinn macht das so zu machen wenn man sich überlegt was die Laufzeit von den dynamischen Programmes was im Rucksack .punkt Problem dazugehört wann wissen was das O von NLD ist ja und das Delikara maximal 10 1. mitgeteilt ich es abgerundet sein das es geschickt werden sprich die Kodierung Dienstränge kleinmachen und damit dass das der 1. mitgeteilt ich es kleinmachen da kann man auch des Algorithmus erhöhen müssten Parameter es geschickt einstellen so dass die Laufzeit von Algorithmus Polen mehr wert war und das geht nur indem wir vor die Kuh die Jungs länger angepasst haben so wir könne so wird das einfach mal annehmen dass für vieles des in diesem Intervall das Problem da oben gelöst haben und wir zu jedem dieser Probleme im Ordner Optimallösung erhalten haben am ist diese XJ denn sind ja die optimale Lösung gefiel es lösen von dem Programm da oben erhalten für jedes die in diesem Intervall nun dass es passiert genau das was wir eigentlich auch vorhin schon bildlich gesprochen haben wir können es einfach für diese großen Elemente für die wir optimale Lösung haben ausrechnen wie viel Platz die verbraucht haben ja der Verbrauch des Platzes genau AJ XJ die der damit genau diese Elemente eiert XRD zugewiesen oder Teile davon zu gewähren den Platz den Verbrauch es genau diese Summe um das kleiner als B ist danach war Folgendes wenn man den wichtigsten Greedy Algorithmus und wenn in einer auf das folgende Problem wir wollen maximieren das zehrt XJ jetzt aber mit dem JMS das sind so die kleinen Elemente die wir noch nicht benutzt haben
unter der Maßgabe dass AJ XJ spricht der Platz den die kleine Elemente verbrauchen der muss kleiner gleich sein denn B des die größtes Rucksacks Minis den Platz den weshalb für große verbraucht haben XJ ist wieder einmal 1 und J in es ja wir machen also wirklich in der Tat diesen 2 Stufen Woodstock wegen Prozess den wir angedeutet haben wir lösen das Problem für die großen Elemente optimal bezüglich dieser leicht werden Kosten Tour dann aber Platz über mit Platz 7 über haben dass es genau die Differenz von dem wie und dem Platz der verbraucht haben und bezüglich diesen übergebliebenen Platz wenn man wie die also anpacken kleine Element in irgendeiner Art und Weise kann wieder ein kennt sorgen und die Lösungen für jeden dieser Läufer Zeichen auch mit exakt den und damit erhalten dann insgesamt Lösungsweg Tag X die Art des mit ihr hat denn 1 bis n und dass eine Lösung des Rucksack Problems wir haben also wirklich nur diese beiden Lösungsteil genommen die Lösung von dem von der 1. Lauf in dem das optimal Figos Elemente gelöst haben für jeden dieser Leute bekommen eine Lösung für die noch übergebliebenen kleine Elemente mit Heften Lösung einfach aneinander und jede dieser aneinander gehefteten tolles Listen enthalten Lösung von dem 0 1 Rucksack Problemen bei bei Konstrukten Nachkonstruktion genau der Staatsdiener verbraucht haben nicht überschritten worden ist und die Frage ist einfach nur die gute Lösung ist die wir erhalten haben so Sender 8 zweifach gibt die beste Lösung vor die beste Lösung aus und das sind maximal zuerst es halte ich es das eine Lösung brauchen gut was wir sehen werden ist dass der Algorithmus für geschickte Wahl von SMT verschiedene Approximation Skythen geben wird und den scheine punktet hinter seinen zu zeigen ist der Algorithmus in polynomieller Laufzeit hat uns abholen nunmehr nicht nur also also Polen mir imponiert insbesondere Naproxen Einsicht Approximation spielte also dann wirklichen voll koloniales Approximation Schema hier gut wir versuchen den beweisen einzelne Stücke zu zerlegen in der Hoffnung dass dann der Mechanismus warum weiß funktionierten
bisschen klarer wird 1. zeigen werden ist das die Lösung die wir konstruieren das CK dass die Lösung die wir aus unserem es geht das kommt nur maximal kleiner er also ist nur minimal kleiner ist als auf die optimale der und das ist diese Differenz ist genau hier beschrieben und das halten Quotient aus dem 1. den Tee meine wirklichen Optimallösung plus dem Tee und ich Geschichte war für später ,komma genau dadurch die Approximation es Garantie herstellen gut bezeichnet X Stern die optimale Lösung zu dem eigentlichen Probleme die wir nicht kennen was jetzt machen werden ist werden wir wir behaupten ja dass für irgendein des was wir hier oben geschickt wählen genau diese Approximation Garantie eingehalten wird das alles machen es raten geschickt dass die Insel klar warum es diese wenn es gewählt wird weil Algorithmus genauso Konzeptes dieses die zu finden um er hat mehr ab ja ja bei er ob war also dass wir das machen müssen es müssten Display Daten und dafür werden wir jetzt erstmal dem gleich der Sommer der großen Elementen oder über die großen Elemente sehr hart gibt halte ich es weil XJ Stern Rentner und das erhalten ist folgendes ist des es kleiner gleich 1 durch S mal der Sommer über die größten Elemente 10 J XJ Stern abgerundet das liegt einfach daran dass ich wenn ich das Runden nach außen Ziele der Terror serviert das hier ist aber unser optimale C gewesen ob also halten wir einst durch C Ort und das wiederum nach der eingangs erwähnten Abschätzung nicht dass sie es tun wird erhalten wir dass es kleiner ist als 1 durch erstmal C fest so damit geht nun aber war das viele Kandidaten Lösungen x 1 Square des Xn quer erhalten mit kosten CJ gibt halte ich es weil XJ quer ja wir haben also für dieses des Hamel Algorithmus ausgeführt und wir haben auf in dem dann Programm dann für die großen Elemente wie Lösung gefunden dass die Gesamtkosten des sind und die Lösung hierzu gehört ist der Kandidat die Lösung dafür und existiert immer halt weil wir über den gesamten Bereich es ist ist ja kleiner als unser ab geschätzter Wert und diesen über alle Werte von 0 bis genau diesen Wert gegangen haben die einzelnen weil abgetastet so was machen ist folgendes ich will das mal an aus das ist der Kandidaten Lösung aus unserem Approximation es Algorithmus ist ist sicherlich dass die optimale Lösung wieder ausgerechnet haben das CK es größer gleich als der Summe der C jagt XJ quer vielleicht gleich 1 bis 1 1 damit sie denn deren
Einlösung konstruiert mit denen einige daher mit Programm und dann Verpackungen wie kleine entdeckt kleinen Elementen kommende Lösung was jetzt hier als allererstes behaupten ist das die optimale Lösung konstruieren ist größer gleich der Kandidaten Lösung das ist klar aber die Lösung bezüglich der Kosten 10 optimal war das also nur eine von vielen gewesen weil die beste ausgewählt haben so das aber kann man liefert umschreiben das gleicht optimale Lösung -minus die ja mir erst mal und dass der Fehler denn auf den großen Elementen gemacht haben ja also hier die Kosten sind sie Funktionswert den optimalen Zielfunktion sodass den großen Elementen das was überall läuft und den viele Dinge gemacht dann auf den großen Elementen es genau der optimale ziehst und sonst auf den großen Elementen -minus und Ziel Funktionswert auf unser Kandidaten lösen war das also der Fehler auf den großen Elementen nach anderen Fehler auf den kleinen Elementen gemacht das sind die J in 1. wird ja nicht genau so aus ja und das also der Fehler aus dem kleinen Renten ja wir haben also unsere Kandidaten Lösung geschrieben ist die Funktion werden unsere Kandidaten Lösung hat als der optimalen Konfiguration wieder noch nicht berechnet haben aber hier an zu kennen -minus ne fehlen auf den großen Elementen gemacht haben und wer auf den kleinen gemacht haben es kann durchaus sein dass das geht dass das der 1. tänzerischen Negatives am Ende sozusagen auf den großen Elementen besser gewesen sind aber auf die klein schlechter an das kann ich auch bisschen aber sind es Mal die die Differenz der nur den Fehler beschreiben kann was es machen wolle so wollen jeden dieser Einzeltermine hier geschickt abschätzen und dann zu zeigen dass das CK größer gleich C Optimie aus Estrich durch T Mahlzähne ob +plus T ist um 1. mal ab der 1. Teil Abschätzung das Delta und das ist der L Teil das sie und mit einer 1. werden wir haben also die Summe der CLJ XJ Stern man Minister der Summe der CIA hat der XJ quer wir in J und wir möchten genau diesen Teil abschätzen oh dazu machen folgendes vor ich schreib erst mal hin und dann dann dann denke ich wir in werden wir sehen warum das so richtig ist so und was wir eigentlich nur gemacht haben ist eines geschickt und geschrieben der C MIR und der Termin der hier drin steckt das sozusagen als wir mit 0 gewesen ja die beiden nämlich genau weg der mir untertänig in bestehen hat heben sich genau weg und was wir hier stehen haben das ist in Wirklichkeit dieser Termin hier abgeschätzt wir doch mal überlegen was diese Funktion macht er sich erst Teile Abrundung multipliziere das heißt ich verschiebe auf diesem diskreten geht der die Punkte einfach nur nach links haben dass man die teils für durch diese es generiert habe und ich hab jetzt sind sie aber so hier liegt wahrschinlich dieses zehrt an diese Stelle kann was sollen Wirklichkeit machen es wird ziehen hier C ihr heute XJ quer ab und jeder dieser thermisches S 3 multipliziere ist aber kleiner durch wird nach links verschoben habe welche diese nur größer und das der Grund warum man Vergleich steht aber warum warum macht es Sinn dass wir hier gemacht haben Na ja das liegt daran dass dieser Themen hier der ist Nachkonstruktion gleich unseren des gewesen war genau so dass die gewählt und der Termine hinten wer hier es aber auch gleich die gewesen dass ich unsere Kandidaten Lösung ja fast der einzige Zweck der hier drin steckt ist der dass wir wirklich diese Differenz des Fehlers leicht umschreiben in dem aber nur hinzufügen und diesen Termin hier durch die Approximation hier abschätzen und dann ist der vordere Thermen genau der gleiche hinter der wer genau so haben es die gewählt ist das die optimale Lösung bezüglich diesem optimalen des habe für die großen Elemente der Kandidaten Lösung gewählt und damit fallen die weg und so in die diese Art von Trick von selber fast alle Approximation es also Algorithmen ich rechne Optimallösung aus hat dann die Differenz der viel erklären und ich geschickt das Abschätzen der der bei der optimale Lesenswertkandidaten Lösungen durch die Runden der Kosten der mir kann ich Trick von dieser vormachen so was bleibt da wir jetzt über nachdem wir das gemacht haben das ist was also über bleibt es genau damit hinter mir
und bevor ich das einschätze können wir einfach mal überlegen was da steht was dieser Termin hier Mitte Terni übergeblieben ist sollten der und nochmal steht eigentlich in hält ist die Differenz der Kosten orginal kosten zur abgeschätzten Kosten über überdies kritisiert haben wir rechnen also aus was war jetzt das werde kosten würde ich dieses nach links schieben gemacht haben was also auch bei ist vieles Gebete Element XJ was den Rucksack getan einen echten optimale Lösung Rechnung aus was der Fehler gewesen ist und der Fehler aber genau dieser einen Schieber so genau diese Differenz hier und das ist genau der Teil I und besteht so wie groß keine Fehler aber sein es war was immer es Intervall also Länge Breite den Wales ist es das heißt wir jeden dieser seither aber keine Fehler maximal es gewesen sein ja und damit erhalten dass der Gesamtfehler es XJ Stern gewesen ist und so wir also jetzt erst mal im 1. Schritt den Fehler auf den großen Elementen der Zielfunktion abgeschätzt beste mich maximal 1. XJ Stern leider kann aber mit dem mit dem externen das Kinder halt nicht ist also eine Stelle und nicht wie groß der Fehler ist und dass er stets dass es noch einmal weiter ab also wir haben es mal Itzhak Stern als Fehler gehabt falls anschließend viele Fehler gehabt und was jetzt machen es wir schätzen dass es ab durch es gibt halte ich T mal initiiert Stern das lag einfach daran die Elemente die über sind die CIA das sind genau die die groeßten als das T so heißt CJ gezeitigt des ist größer als 1 so anders konstruiert er also das geht 2. sehr gezeitigt ist größer gleich 1 für alle sie sind war genau das waren die großen Elemente gewesen war so aber das was ähnliches optimale Lösung das heißt ist kleiner als es geteilt durch die wird sie oft ja und das neue 1. Teilen Abschätzung werden ja behauptet dass das CK ist größer gleich sie Ort -minus es durch den Wald sie Ort er also außerdem gewesen und 1. Teil 4 größten irdischen hergeleitet Zeiss der Feder auf den großen Elementen ist in der Tat es gezeitigt jemals die Art einfach nur schon als Hinweis damit man sieht dass der Term wirklich der Termin hier ist eine Abschätzung sein das heißt die Hälfte haben wir geschafft einfach dadurch dass wir jetzt die großen Inter abgeschätzt haben was übrig bleibt hat die Abschätzung der kleinen Elemente auf besorgen die kleine Elemente die Differenz steht aber hier oben das heißt dass des abschätzen müssen ist die Summer der CLJ XJ Stern -minus 10 J XJ quer und das wird ist in dem es der das also der Fehler den wir oben auf den kleinen Elementen gemacht haben könnten so dazu bevor behaupten wir Folgendes die Lesung die der Göldi Algorithmus auf dem es Elementen liefert es größer gleich der optimale Lösung -minus dem maximalen Element sie J wir dort gleich 1 wird in einem ja das wir behaupten also damit optimale Lösung nehmen und das Element mit dem maximalen Kosten abziehen weiß die Lösung des Kuli Algorithmus ist besser was klar ist ist wenn alle verbleibenden Elemente den Rucksack reinpassen dann ist die Lösung ist genial würden was vielleicht optimale Lösungen aber ich kann einfach alle Elemente einpacken das heißt in dem Fall gilt die Behauptung das liegt einfach daran in dem Fall ist es die optimale Lösung ist wie Algorithmus gleicht echt optimale sommerlich alle Elemente einpacken kann wenn ich jetzt von dieser Optimallösung ein Element abziele ist die optimale Lösung Minis diesem Element natürlich kleiner als die Lösung ist wie Algorithmus ist wenn das nicht gilt dann wissen wir dass 0 ist kleiner gleich den -minus denn Elementen die wir haben einpacken können mit dem Gewinn des Algorithmus und das aber kleiner als das nächste Element das ist klar die durch Algorithmus packt Elemente solange Rucksack rein bis das nächste Element das eine Liste kommt nicht mehr rein passt das heißt der Rest Platz hier ist kleiner als die des nächsten Element ist das ist eingepackt was ist damit gilt es aber dass die optimale Lösung ich erhalten kann es kleiner als die Parlamente dicht aufaddieren kann die also auch einen Rucksack eingepasst haben ja ich dir der höchsten Dichte gewählt habe bloß B -minus der Rest also wegen des dem dem Verpacken Elementen also der Restkapazität geteilt durch den AG AK +plus 1 mal 10 J +plus 1 C +plus 1 ja was also machen hier ist
ja einen Rucksack befüllen arbeiten wie Algorithmus solange es geht mit absteigenden dichten bei Sammlern steht hier über hier in der steht passt das Element das nächste Element das AK +plus 1 nicht mehr rein wir können wir sozusagen so viel von dem AK +plus 1 reinpacken überein wie reinpasst um die hat Anteil von im AK 1 rein tun können ist genau die Restkapazität das ist der Kern der verteidigt die echte Länge von dem Element das also genau dieser graue Kasten hier und die Kosten über den Erhalt des SDK +plus 1 weil die zugehörige Zuweisung variabel XK K +plus 1 ist Intervall 0 1 gewählt ist und Fraktion ist das heißt der Zielfunktion dir die Summe der CLC EXE ist man eben halt wenn die Kosten hat genau mit dieser Restkapazität hier multipliziert damit ist die Lösung der das entspricht der optimale Lösung des LPs ist natürlich größer als die optimale Lösung der ist der ganzzahligen Lösungen so und das letzte hier ist aber zusätzlich kleiner als die durch die Lösung das maximale Element 10 J mit J wir haben also die Elemente verpackt dass also die Pille so und die durch die Lösung +plus den maximalen nennt ist größer als das der war mindestens ein Element reingetan das 1. das ist größer als alle von der Elemente und das habe nochmal zu begraben so mit der Abschätzung können wir aber jetzt also mit der Einschätzung hier es soll wissen dass die Geld glaubten kleiner gleich zu der dass der das mit Stern so was alles Wissen mit der Abschätzung ist das die Leser von Beginn der Algorithmus was genau diese Summe der Ciliat XJ quer über den kleine lehnten ist dies echt größer oder nicht größer als Ort -minus dem maximalen Element war und das maximal maximal Element zehrt hier aber ist größer als das P herum das Element hier ist größer gleich T das Makro ausführen wenn daraus folgt aber auch das ist sehr hart Ministerien es kleiner gleich der Kollege Lösung und das ist genau diese du Somalia wir haben also jetzt gezeigt dass auf den oft nur auf den auf den kleinen Elementen dass die Bilder so maximal T schlechter ist auf den kleinen Enten der er vielleicht also da die Lösung dass sie ab bezieht sich wirklich auf die optimale Lösung zu den zugehörigen Netzwerkproblemen wie kleine sollte vielleicht auch dazu schreiben lassen ja das wirklich dass Sie ob das wirklich der der optimal Wert Frenzel Ringe Rucksack Probleme so das Fürchten trug sorry ja mal so gesehen das sich der Elbtal abschätzen es durch es gibt halt ich die mal Ort wir erstmal wissen wir das sich das abschätzen lässt dass sich dieser Fehler abschätzen lässt durch The das steht hier und damit Kinder genau die abstürzende und stetig hat das ist noch mal hier einmal sauber hin der Bau Summen was also haben aus der Abschätzung der oben ist das T ist größer als das C Ort man das C Greedy und das ist aber nichts anderes als das das aber größer als das CIC hat auf den 1. das Sex Stern Ministerien dem CZ quer das sich erklärten keine Daten Lösung gewesen ist nicht nur weniger sie optimale Lösung sein musste sollen folgt dann insgesamt das CK das größer als C Ort -minus
es gibt halte ich den The Art löste in das kommt von Eltern und das der Komfort im 1. und damit 1. Satz gewesen so wärmere gezeitigt das diese Approximation sah Algorithmus für von SMT wirklichen Lösung ck liefert dessen Fehler gegeben dass ich diesen Termin der und das er ausschließlich bestimmt durch S und T und optimale Lösung The zeigen werden es ist eine S unter geschickt wählen dass sie damit in der Tat in einen vollen Erfolg kolonialen Approximation es also etwas erhalten er hat so sei er schon größer als 0 ist umso Approximation Scythe die wir Forell wählen dann setzen wir es als Epsilon 3. Quadrat und T gleich er ist ein Drittel geführt haben zuerst mal der entsprechenden geschätzten sie Funktionswert Mehr alle schätzen sie Funktionswert ab das ist die 1. mit und dann definieren wir es als 1. 3. Quadratmeilen abgeschätzten Wert und dass sie einfach nur er zum 3. Mal ende abgeschätzt wert ja normalerweise wird man es durch Rechte dann würde am Ende sehen das ist etwa so groß gewesen SMS-Apps ,komma dass er ersetzen genauso wie müssen als auch machen würde n sollen im 1. Schritt sein als dass der Algorithmus Laufzeit von Algorithmus 6 9 wer ist auch von allen erlaubt N +plus oh von allen mal einzig Epsilon Quadrat und für die optimale Lösung gilt er das CK größer gleich 1 -minus Erbsen und malt sie ab das das bewiesen haben dann am ende Taten folgten als Approximation schlimmer weil die Laufzeit Polen Mehr in Dimension und einst durch der Approximation SQLite ist und dieser Jahren wenn wir gleich sehen da kommt eigentlich nur von sortieren es kann sein dass wenn es unser sehr großes dann kriege ich hier fast lineare Laufzeit ich hab aber etwas mehr Sinn der Laufzeit Rechte Füße Tieren der Eingangsdaten brauche so ist der Termin nochmal extra Jahr für Jahr für vernünftige Größen von y ist Laufzeit ich den Termin hier gegeben zur Schritt 1 und 6. Algorithmus sein Satire Schritte mehr benötigen oh von Emma laugh allen für desertieren soll Schritt 3 Schritt 3 es ist der Name schon Programm was wir wissen müssen und angesehen bei dynamische Programmierung das sich das Rucksack es eines Rucksack dynamische Programm lässt sich lösen und von allen mal des vorbei wie die rechte Seite war seine Yen leicht anderes dynamisches Programm betrachtet man kann sich aber leicht überlegen das das exakt der gleiche Algorithmus auf und sei mit dem einzigen Unterschied dass wenn wir auf Gleichheit bei dem Renzi Funktionen schauen das hier wenn die Bedingung Letzteres potenzielle Kosten endlich einführen den Phonds nur exakt der gleiche Algorithmus unterdessen seine B aber gewesen dass des also in unserem Fall er haben wir erstmal von mal die gehabt dass die war aber immer Gewicht aus diesem Intervall CSD mitgeteilt ich es abgerundet und das ist aber kleiner als O von allen mal geteilt durch es abgerundet und wenn es einfach jetzt einsetzt also wir haben das es war definiert als er zum 3. Quadrat geteilt ich zuerst wir das ist also hier einsetzen und wird das CS draus und das dreht sich um wir bekommen 3 Epsilon Quadrat mal n Restlaufzeit die 3 , wegfallen lassen als in Faktor ist also das das gleich wo von allen 1 durch Apps Quadrat und das ist also von 1 geteilt durch Apps und Verrat das Wiederverschließen mische Programmen n und hat ja hat nein das ist wahr ab ja ab ja ja hatten ja und so den Schritt 4 das wird
mit berufen wenn wir Algorithmus auf das machen wir wovon 1 durch erst zum Quadrat weil oft sehr gibt sich genau wie vorher durch abschätzen dass dies nach es denn mal wer also CS gibt halte ich es mal das war nur einzig Epson dergleichen 1 1. Kodak genau wieder oben argumentiert und das Ganze Aufruf waren vollen Gewichts abdichten Greeley und das in Glieder gehört selber hat Laufzeit von o von allen hat soll fort auch in dem Fall der Gesamtlaufzeit von o von Einmaleins durch Apps Conrad ja jetzt das heißt aber daraus folgt jetzt unsere Gesamtlaufzeit es mal allen für das Sortieren gewesen das wir machen müssen wir aus n geteilt durch Erbsen Quadrat und damit ist der Satz bewiesen und das ja das typische Vorgehen Approximation es also wird man designt also fast aller Ports mations Algorithmen runden die Eingabedaten entweder so wie es hier gemacht haben dass wir sozusagen die Eingabedaten sozusagen du bist kritisieren auf einem Gitter das in Einheit S funktioniert was man auch oft macht ist dass man das ist ist sozusagen die indes dass ist das ein arithmetisches Gitter in dem Sinne als dass hier steht einmal S hier steht zweimal es dreimal es das heißt unser geht der Schritte sind kann man es wer verkeilen enden das heißt es geht es ist in dieser in dieser Hinsicht eine tief das war auch sehr oft macht also insbesondere in erweist Gerling Anwendung ist dass man kein IT Gitterbetten multiplikative später und leises halb so ja das das dieses gibt ein exponentielles Wachstum hat daher haben wir es hoch 1 hier ist doch 2 es hoch 3 so 4 und so weiter sollte das geht als geometrisches nämlich metrisches getan war und das Inkrafttreten Mensch ist ja mehr ja er Wasserstellen an diesem geometrischen getan ist das wenn man zeigen kann da ist wenn ich es gleich 1 +plus Epson Wille das meine Zielfunktion irgendwo in diesem 1 +plus sollen geht daran irgendwo hier liegt dann ist der Fehler aber das ist wenn das Ziel Funktionen Funktionen schaffe so zu konstruieren dass ich zeigen kann dass die Zielfunktion denn so steht auf dem 1 was Apps angeht da liegen ist der Fehler von diesem sie Approximation es wird hier maximal 1 +plus 11 soll aber als Faktor ja es geht also sobald es ja keine IT wieder mehr essen die Feder multiplikativ und zwar 1 bis 11 sollen maximal das heißt ich schaffe und Gitarre so zu konstruieren dass geometrische so meint sie von abbildet aber 2 tionslösung konstruiert die immer auf diesen Punkt liege und hier man optimale Lösung ist dann liegt hier so optimale Lösung hier zwischen und das einzusetzen und 3 das heißt wir 4 das heißt der Fehler die diese Lösung haben keinen diese im Vergleich zu dieser ist kleiner als ein dass es als Faktor das ersichtlichen Approximation es gern Tee direkt vorne weg das andere uns alle retten zu konstruieren ja das geht leider bei dem Beispiel hier also nicht aber ist sehen halt noch vielleicht ne ganz nette Technik für viele andere approx Massons also kann es uns gelingen ja direkt die Approximation es Garantie Geschenk Krieger aus der Wahl es geht das ja ich wird das auch ganz kurzen Überblick geben über der anderer Approximation es Technik ich denke wenn ich das letzte Details erschaffen werden ja zu ja ja
ja mehr da sein Na ja der war ich will vielleicht einfach erst nur die Motivation heute geben eine große andere Klasse von Approximation es Algorithmen sind die so genannten Primal dualen Algorithmen ja ja die wir hinter steckt ist die folgende will eine LP betrachten am da wir haben und des Apple lösen dann keine eigentliche Wirklichkeit immer 2 Lösungen Huhn kriegen eine prima Lösung x mehr wir ,komma auch automatisch wir alle Lösungen war die gültig ist das Dual was wir wissen ist wenn man sich das so bildlich vorstellt und wie er minimieren dann immer mehr depri Male Lösung so und dem .punkt und was sie synchron machen es war dann Simplex also etwas ist das auch eine duale Lösung maximieren herum und wir wissen dass wir optimal sind wenn Primal gleich duale ist also sowas wie y mal B ist das gleiche wie 10 also mit der Stern mehr da sind optimal ja das ist die Lösung des Duals mal 7 1 1 mit der rechten Seite die rechte Seite 10 kosten und das die Bremer Lösung meine Kunst weiter es ist so das Optimalität Kriterien der Fall haben dass diese Bedingung vom schwachen Schlupf auf schwachen komplementären schluckt was die Medien aus sagt ist folgendes er der Firma 2 zusätzlich variabel ein einmal T das sind die reduzierten Kosten und es des der Schlupf er dann wissen wir das wir haben und der Schlupf von einer Ungleichung es E mal in der dualen variabel y das bedeutet dies ausgewählt um die optimale sind zu konstruieren muss 0 sein er dass eine der beiden Bedingungen was wir denn aus sagt ist das wenn ich das selbst wenn die gleich 0 Sätze spricht diese ungleichen benutzt werde um diese optimale Lösungen als zu konstruieren weil nichts anderes bedeutet das dass Anthony ungleich 0 ist danach die war danach diese ungleichen kein Zweck gehabt haben das heißt die liegt ja also ist ja in kein Zweck gehabt das ist die 1. von den beiden Dingen die andere Dinge SAS orthogonal dazu und die Sachen einfach dass wird immer eine variabel und gleich 0 gewesen ist dann müssten die reduzierten Kosten nicht nur gewesen sein wenn das so und das gibt es da keine Kriterien dafür Wandel so optimal ist nicht nahmen die beiden Bedingungen erfüllt sind ja ja wenige Sterne dran sind mehr das geht sehr schön länger brauchen den Fall dann aber in Täterprogramme haben da es diesen Bedingungen nicht mehr notwendigerweise erfüllt weil unser Gleichungssystem nicht genügend Facetten enthält und jede und um die ganzzahlige Seele abzutasten das sieht also so aus wir haben hier unsere Polittalk und in diesem Polito Parma das PEI also die ganz Heiligenbilder und und so ungleichen außen warum erlauben uns in für Dual nicht hoch genug zu kommen ja wenn das die LP Lösung hier ist dann ist die IP Lösung die Marquis irgendwo liegen diese also erstmal Dual nicht zulässig was da einige wenig gewogen Gleichung haben weil sie die ganze Regel nicht richtig beschreiben und deshalb kann man nicht erwarten dass wir diese Bedingungen gleich sicher fühlen können waren sie was fehlt er sonst viel Ungleichungen das die so genannten Karten Pläne seien auch oder Teile davon sind genaue Karten glänzt die es erlauben hier hoch zu kommen die fehlt uns und so was wir jetzt macht um Approximationen hat aber 2 zur Lösung zu konstruieren ist wir fange an mit einer Lösung die eine der beiden Bedingungen erfüllt ja das kann man sicher stellen wir zum Beispiel kosten größer gleich 0 haben dann dieses immer sehr einfachen zulässige duale Lösung zu Konzerne einfach Epson und nicht nur so und was wir versuchen ist aus dieser duale Lösungen die Versuche mal so lange wie möglich gültig zu halten und prima dazu zu konstruieren bis 1 .punkt ankommen wo weitere Male so konstruiert haben die gültig ist außer duale Lösung das heißt es
ganz prima Loral Ansatz man Relax eine von den beiden denn je nachdem wo man es macht und versucht dann die andere sozusagen also entweder gelegt sieht man diese Bedingungen hier dass Syrien kommen müssen tastet man sich Sony Lösung dran und mal der Lachse die andere Bedingung und tastet man sich so eine Lösung drann und das ist das dass wenn der nächsten Vorlesung mit machen werden ja
Objekt <Kategorie>
Länge
Gewicht <Mathematik>
Randomisierter Algorithmus
Vorlesung/Konferenz
Zielfunktion
Element <Mathematik>
Konfigurationsraum
Ecke
Computeranimation
Mathematische Größe
Parametersystem
Obere Schranke
Gewicht <Mathematik>
Punkt
Verschlingung
Momentenproblem
Quotient
Laufzeit
Betafunktion
Besprechung/Interview
Berechnung
Element <Mathematik>
Linie
Dichte <Physik>
Index
Summe
Lösung <Mathematik>
Menge
Kettenregel
Vorlesung/Konferenz
Zielfunktion
Funktion <Mathematik>
Parametersystem
Laufzeit
Term
Summe
Lösung <Mathematik>
Menge
Rundung
Gitterpunkt
Abschätzung
Vorlesung/Konferenz
Zielfunktion
Normalvektor
Mechanismus-Design-Theorie
Summe
Lösung <Mathematik>
Negative Zahl
Quotient
Rundung
Abschätzung
Vorlesung/Konferenz
Zielfunktion
Element <Mathematik>
Optimierung
Konfigurationsraum
Länge
Gewichtete Summe
Element <Mathematik>
Term
Ganzzahlige Lösung
Dichte <Physik>
Lösung <Mathematik>
Summe
Elementare Zahlentheorie
Stochastische Matrix
Abschätzung
Vorlesung/Konferenz
Zielfunktion
Kerndarstellung
Mathematische Größe
Faktorisierung
Quadrat
Dynamik
Dynamische Optimierung
Laufzeit
Vorlesung/Konferenz
Funktion <Mathematik>
Ebene
Approximationstheorie
Faktorisierung
Simplex
Gewicht <Mathematik>
Punkt
Laufzeit
Klasse <Mathematik>
Einmaleins
Gleichungssystem
Optimum
Gleichung
Lösung <Mathematik>
Quadrat
Ungleichung
Vorlesung/Konferenz
Zielfunktion
Dualitätstheorie
Funktion <Mathematik>
Vorlesung/Konferenz

Metadaten

Formale Metadaten

Titel Ein FPAS für das Rucksackproblem
Serientitel Diskrete Optimierung (Optimierung II)
Teil 22
Anzahl der Teile 26
Autor Pokutta, Sebastian
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/31775
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2009
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...