Merken

Heuristiken: Der Greedy-Algorithmus

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
sauer wär Höhle wie dies ja das war ein wir gut man kann
aus meiner Sicht loslegen werden das letzte Mal das kann würde Kapitel abgeschlossen Schranken oder Lachs ierungen aber sagen 3 4 4 verschiedene Verfahren kennen gelernt die mir Relax bestimmt wie man es vielleicht auch effizient bestimmen kann angefangen von Elpida Platzierung wird für der Ganzheitlichkeit übersteht Ebenen Überlack Räucherlachs Siedlung Galaxien von der anderen Bedingungen und Rückführung in die Zielfunktion bis hin zu Dancing größten Teil daran Bedingungen aus dem Rückführung über die Formulierung und das gleiche bei Benders wenn dann gesehen dass zumindest LP Fall agrarisch Bänder und Danzig Wulff eigentlich denselben Wert liefern wenn das das duale zu Danzig Wohlstand sie wohl wissen wesentlichen dasselbe die viel rasch agrarisch bestimmt die Werte über so gravierenden Verfahren und Danzig durch über Spalte generieren 2 vielleicht nochmal als Rückblick zu den Relax sierungen und das letzte mal die 1. Sätze darüber verloren über die andere Seite die alles sei die beständig möglich schnell und gut gute Lösungen für ein Gemisch ganz Programas von Haus aus wie schwer es und der Hammer ist offenbar Vorbemerkungen dann angefangen 1. paar Sätze zu dem sogenannten Greedy Algorithmus hat dazu äußern und da wo ich jetzt heute ansetzen die formalen Definition dazu einzufühlen Algorithmus Ihnen vorzustellen und dann vor Nachteile dieses Algorithmus zu diskutieren gibt es aber bis dahin vom letzten Mal noch Anmerkungen oder gut das nicht der Fall ist dann also wie gesagt Kapitel 4 heuristische Verfahren hat mir die Überschrift schon 4 1 wer dann der Greedy Algorithmus und wenn was man paar formale Definition ist sieht erst mal etwas spezialisiert also werden dann sehen dass unter diese Definition ziemlich viel an Problemfällen fehlt und auch ja letztendlich die ist nicht man zur transformieren kann das sie dann darauf anwendbar sind also dass die Definition 4 1 der diskreten optimieren machen was in endlichen Mengen zu tun sei E endliche Grundmenge in der dann auch in dem Fall Grundmenge des IE kommt gleich schon bisschen als Assoziation zu Grafen Probleme häufig werden solche Probleme auch oder ein Problem mit Kylie Algorithmen Hand die sich auf grasten formulieren lassen wir schauen uns eine Teilmenge der Potenzmenge an sei ihn stört es mal so also soll die Menge aller Teilmengen von ihr seinen Namen die Kardinalität und der 2 hoch N also angefangen von der leeren Menge 1 EL in wenigen Tagen einen 2. nennen und so weiter bis bis in inwendigen Teilmengen und daraus nehmen uns eine beliebige Menge heraus ja so ne Menge heißt Unabhängigkeits ist denen 7 bestimmte Eigenschaft hat heißt Unabhängigkeit ist denn ja falls folgende Bedingungen erfüllen des Falles mit G Teilmenge von F und Element aus ihnen folgt das auch G Element von is Sommer steht hier also was es heißt immer man nicht haben ich habe Menge FDI Element dieses die diese dieser groß man is also Elftal Teilmenge von I und ich nehme keine heraus dann muss es auch eine unabhängige Minister also diese Mengen die in diesen Uneinigkeit Systems in man unabhängige man also wenn ich nen unabhängige Menge hab ich jene Teile von unabhängigen jeder muss die auch unabhängig sein also bezüglich Teilmengen Inklusion bleibt diese Eigenschaft erhalten so woher kommt dieser Name mag also als Beispiel dass alle kennen es aus der linearen Algebra eine lineare Unabhängigkeit sie Menge von Vektoren haben die Länder unabhängig sind sie Teilmenge heraus wie auch wenn unabhängig wir haben daher auch sozusagen verwandt halt von dem Begriff letztendlich ist es ein Stück weit mehr mathematische Abstrahierung von dem Begriff im Jahr der Unabhängigkeit ihres 1. wie Algebra kennen was man auch sofort sehen ist kann das durch diese keinen Eigenschaft dass dass die leere Menge auch meine unabhängige Menge ist nach der Definition gut mit der Begriff eben dazu geführt gebraucht sein jedes Element aus ihr heißt unabhängig also 11 Element e er ist unabhängig und 11 nicht aus ihn das heißt abhängig machen gibt es noch den Begriff einer Basis also eine Teilmenge 11 mit erfahren 2 11 aus dann heißt und zwar so schönen 4 11 aus E heißt eine Teilmenge von 11 in die in keiner anderen unabhängigen enthalten ist in keiner anderen unabhängigen Menge enthalten ist Basis von E von 11 also sie können im Moment gerne einmal lineare Algebra denken klassische Begriff lineare Unabhängigkeit wird einen ist in unabhängige maximal in der unabhängigen Mengen heißen barsten genauso wie in der linearen Algebra 1 sind an der was musste Lilian Algebra kennen ist dass die Basen immer gleiche Kardinalität haben also wenn Intervention in Wien gibt es maximal n linear unabhängige Vektoren jede Basis besteht auch aus aus solche Vektoren dessen interessante Eigenschaft ist die Vektoren erfüllen aber aber die nicht alle Unabhängigkeit Systeme erfüllen also diese bist aber gleich sie dieser Begriff des Unabhängigkeit System ist hier aber deutlich allgemeine stellt noch keine Forderungen an die Basen an dieser Stelle wenn man nachher auch sehen was die optimieren betrifft es sich genau da der Knackpunkt Orte ob zum Problem einfach zu lösen so oder
nicht erstmals schauen was mit Zielfunktion an alles sei Zähne Zielfunktion die geht von e nach einem Jahr dann heißt es sollen wir uns das anschauen Maximiliane sie von ihm die Teilmenge von Ihnen das Maximierungsproblem über Unabhängigkeit System also Maximierungsproblem über den Unabhängigkeit System I und genauso gibt es das Problem minimieren C von B und Wesel Basis als minim Jungs Problem über einen Basis ist ihnen heißt man Jungs Probleme über einen das ist denn was ist es denn wenn in dem Zusammenhang dann auch gerne zum Kalibo grafischen B bezeichnet so damit Hammer der deckt also schon einige alle Definition zusammen die wir brauchen also vielleicht jetzt nochmal hören wir jetzt im im Sinne von lineare Algebra haben in dem Sinne auch keine Optimist Pobleme gehabt wenn man eine Idee und der Vektoren anschauen dann aber gleich welche kennen lernen was mir vielleicht zusätzlich der Tiere noch anmerken sollte ist es folgen denn das wird nach entscheidend sein dass diese Basis Eigenschaft bezüglich jeder Teilmenge der Grundmenge gilt also was es heißt es nicht nur für den vollen Lohn genauso im Sinne Liliana gebrauchen da kann man unter Vektorraum definieren Jahren in diesem unter Vektorraum gilt wieder die gleiche Eigenschaften er mich Vektoren aus dem Unterdeck darum kann ich wieder hab ich wieder Lenya Unabhängigkeit maximale lineare Unabhängigkeit in diesen und Vektorraum gibt eine Basis und dort auch essen unterwegs darum alle Basen gleichen Kardinalität also diese Eigenschaft ja diese maximale Eigenschaft Ziegel bezüglich jeder teilnehmen gut beispiele erkennt dennoch Beispiele außer dass er sich gesagt hat aus der linearen Algebra also lineare Algebra das haben wir schon aber was gibt es dafür Beispiele ja minimale sparen wollen mehrere Mahnungen minimale auf spannende neue erst mal Hamann Unabhängigkeit System was es da das Unabhängigkeit System mit Zika also die Grundmenge es die Kanten erstmal was ist Eigenschaft unabhängig zu sein kein klar ist nun mal so nur Kreis ab sowie Teilmärkte kein Greis intelligente Teilmenge Gefangenen Intel und sie auch kein Greis also ich damit locker dieses Unabhängigkeit Kriterium erfüllt soll jetzt was in die was sind jetzt die Basen den Sinn das in den maximalen kreisfreien nennen zum welche kann denn dessen genaue aufspannen beugen das Ausspannen bauen will bedient die alle Knoten sind alle Knoten verbunden und es kreisfrei sobald sie ein zusätzlich der zumindest vorbei wenn es heißt also damit haben wir auf jeden Fall wissen wir was die Basen ich brächte aufbauen wollen also es einmal minimiere Suppe überm was ist es denn es genau das minimale ausspannen Baum Problem wir sehen es auch interessante Eigenschaft schon bei dem ausspannen Bäume gilt auch diese Eigenschaft die Masse Lilian Algebra kennen ihn Zusammenhängen Graph Fab Gefüge bekannten enthält so minimal auf spannender Baum mit laut hätten genau ansah Knoten -minus 1 1 das heißt jeder Ausspanne Baum hat wieder diese Eigenschaft dass sie Kardinalität gleich sind nur so also das ist schon mal einen positiven Fall der genau mit der leeren Algebra übereinstimmt ja weitere Beispiele ab der Vorleser hat schon paar kennen gelernt im übrigen Grafen was man da schon alles gemacht haben bald wir stabile Mengen an wissen das stabile Mengen stabile Menge jeweils 2 paarweise 2 Knudsen nicht benachbart jede Teilmenge der vornehmen ist die Eigenschaft mich auch da es maximale stabile Mengenproblem ist finden wir maximale stabile Mengen Grafen also stabile Mengen so da in der Eigenschaft die um auch haben 1 alle maximal stabilen Mengen gleiche Kardinalität auf Mehr es zu bremsen schauen wir einfach mal diesen diesen Graph an was die maximal stabilen Mengen Wiesengraben also lernen das man maximal stabile Mengen weil ich keine keine keine keine Knoten dazu nehmen ohne dass der sozusagen das die paarweise miteinander verbunden sind oder aber ihnen die da ja deswegen schon denn er hat Kardinalität 3 während die stabile Mängel und eine stabile Menge Kardinalität 1 um alle daran sehen wir schon dass diese Eigenschaft das ist ein 1. Beispiel wo diese Eigenschaft nicht erfüllt ist nein das alle maximalen also alle Basen gleiche Kardinalität haben wir und das ist genau daher die Eigenschaft die wollen wir raus arbeiten oder die Streu vom Weizen trennt er gewisse diese maximale stabil man Probleme müssen endlich schweres Problem das Ausspanne bauen und Bremsen nicht da gibt es immer auch gleich kennen lernen auch nochmal Algorithmus dafür aber dass es genau liegt an dieser Eigenschaften wolle man auch herausarbeiten gut es gibt weitere Beispiele Rucksack sagt Problemen ne das gleiche kann seinen Rucksack
Problemen sie eine Menge die die passt Rucksackreise Teilmenge von den Pass und sich auch an es aber Unabhängigkeit System an auch dort gilt nicht diese Eigenschaft dass alle maximalen gleiche Kardinalität haben an das Beispiel geringste ist mein Problem am 1. 1. erreichen können muss man ein bisschen tricksen mit was Unabhängigkeit System Walter Riester ist man es also 2 kann man doch alle Städte gehen werden sowie oder doch alle Knoten wie definiert man sich dann Unabhängigkeit System während sich meinen sich die Menge aller teilnehmen die zu einer Tour erweiterbar sind nun über mit Teilmenge von kannten mich aus der noch eine Runde Reise machen kann dann nämlich das welches den unabhängigen waren offensichtlich ist es so von einer unabhängigen keiner in denen keine die auch die Arbeit an ok und da wird es ein bisschen kniffliger eine diese Eigenschaft die Frage ist ja und das Wiener nicht erlaubt dieses damit dieser Basis Eigenschaft die maximal unabhängigen Mengen in diesem Fall 10 der die Tour Mehr wenn ich alle Städte Menander verbunden Anfrage haben dort alle Basen gleiche Kardinalität ja ich genau also ist wichtig Mehr wenn ich den gesam gaben an Charme alle Touren offensichtlich n kannten mehr als ,komma aber noch mal darauf zurück was hier steht nicht es muss für alle Teilmengen gelten ok also wenn sie irgendein Grafen in also und die SPD ja ich sagen ich mal dass er den ganzen Graph nicht mehr mit einem genauso wie sieht's so aus wie eine Ruine der vollständigen Grafen ich hab hier 5 Knoten ok und es gibt noch viel mehr hier ich nehme dabei hier als als F ja diese 5 kann sowas in der 7. die maximal und an wen man da drin sie müssen jetzt tue überlegen wären die am Schluss muss es ja tun gegen Aldi siegten Punkte die glauben einer verbinden wir fragen was es verschiedene Touren überlegene Teilmenge dieser diese 5 morgen welche Möglichkeiten gibt es wenn Tour laufen kann ja immer richtig wenn man es so der Name ist in 3 wir also so ne der Kardinalität 4 1 und beide sind zu touren erweiterbaren irgendwie Reise richtig so waren und genau so es andere auch Na also dass wegen dieser Eigenschaft das vergisst man leicht das diese Eigenschaft Basis zu sein und gleiche Kardinalität Eigenschaft die man nachher noch herausarbeiten wollte wie die Teilmenge gelten muss und können so wie sie das diese Gebiete dieser Algorithmus ist aus dieser Greedy Algorithmus er was der jetzt macht ist 1 zu sein so wie es letzte mal gesagt haben was so eine Lösung zu konsolidieren in dem ohne Bewertung vor ja unsere Einzelelemente wir packen solange ein solange es geht er also wissen die leere Menge ist unabhängig also wirklich Staaten mit nichts soll es mag man dann einer Elemente aus R ein Jahr welche Partner einer angenehmen sozusagen Gewichtung diese Elemente wir können direkt die Zielfunktion 10 aber wir könnten uns andere Gewichtung vorstellen wir gleich noch sehen und wie die so lange ein solange zu zeigen man unabhängig bleibt und die einfache entlang dieser Gewichtung vor das ist alles ok und das ist genau das was der Kollege macht mich einmal beide Varianten auf Reiseliste der Algorithmus 4 2 einmal für Unabhängigkeit Systeme für Unabhängigkeit Systeme also was man macht ist lass mal Input-Output weg waren am 1. 2. doch Ingenieuren Input Problem der um bei dem Skript hat sie mir 4 1 oder an der Tages stets rechts oben dann Output ok ist Nährlösung I Kuli die unabhängige S was man macht 1. Welle Gewichts Funktion wäre der Funktion W von ihn nach einer das kann das des sein muss aber nicht sein und sortiere sodass man I 1 kleiner gleich wie von ihr 2 kleiner gleich wir von EMS soll Anfang an 2 der stellt unser IgE wie setzt man auf die leere Menge und dann packen einfach ein 3. Fall ist nicht immer einfach der Reihe nach durch vor K gleich 1 so nun falls EC-Karten größer 0 ist und zur IG vereinigt diese kannte ECA Element is also unabhängig ist ja und dann setzte die den gleich ihn die vereinigt in ja das was eigentlich auch schon und das letzte ist dann 4. es wird ein bisschen Energie IG aus also nix mehr mal nix anders als wir sortieren haben dann auch einfach in dieser Reihenfolge beobachten solange die positiv ist also wir können spätestens dann aufhören sollte die sollen immer negativ werden bin dass das natürlich nix wendet die Funktion lassen so weg solang die Eigenschaft GG ist dass die Gewichte positiv sind und wie unabhängig bleiben wenn ich das Element der zunehmend Fakten was dazu ja egal was danach kommt .punkt so ähnlich sieht es aus für ein Dichter gleich Algorithmus gelegen wenn der wenn wir das für Minimierung für Basissysteme anschauen mit also das praktische gleich
Algorithmus nur das nur der Basis wollen das Algorithmus 4 3 Kreditlinien für Basissysteme also Input Problem 4 2 also laut Skript beziehungsweise so Mehr ihre früher Bases sind formuliert haben was gerade rechts unten noch stand Output eine Basis www so ungemein genau das Gleiche 1. wählen W von eine sortiere wie E 1 kleiner gleich um Fehler gemacht sehe ich gerade wir wollen ja maximieren dass er ist deshalb mal umdrehen größer gleich böse gleich maximieren wollen den dicksten Fisch zu erst anfangen zur bei mir nochmal Sesam umgekehrt kleine nicht wie von EM dann setzt man wieder Bilgri auf die leere Menge so der 3. Schritt ist jeder genau der gleiche vortragen ich 1 du in Falles falls Pellegrini ab also die aktuelle Lösung vereinigt EK was ist oder zu einer erweitert werden kann also das das steht dem Skripten bis 10 bis verstehen oder eine Basis enthält Na also gemeint er so das ist vermisste Personen oder zu einer Basis erweitert werden kann das so ist es genau 1 zu 1 Basis erweitert werden kann .punkt ja dann setzen Ansätze Negri gleich Wege wie vereinigt ja und dann der 1. steht des wiedergeben diese Lösung aus ist ok also gesehen recht einfache Algorithmus aber sehr häufig verwendet und wir wollen es auch an ein paar Beispielen anschauen Mohr funkt sie wohl nicht funktionieren von der Laufzeit her ist es auch der einzige Knackpunkt anschauen sortieren kennen wir ja also je nachdem wenn man es gut macht und dann gibt es dort dann geht's in in lockt Endzeit wenn man es nicht so gut nachmachen aber bis Ort oder in der in den den kleinsten suchen nach 2 kleine suchen nach vorne so weil der hat quadratische Laufzeit im Quadrat was praktisch sehr schnell ist der Quicksort aber kann auch im Quadrat Laufzeit hat aber sortieren gelingen erlaube in ASG geht damit besser als er nur denjenigen die schon bisschen Informatik da gemacht haben und es vielleicht damals ausgiebig untersucht das Sortieren da sich nicht in kürzerer Laufzeit das n log n die zu langen auf paarweisen Vergleich baut an gut des Eises einziger laufen die noch einmal im dürfen jedes Element schauen und dann nur noch einmal an ja hier das einzige was wir jetzt hier überprüfen müssen ist das Ziel also müssen ein wird überprüft ist Basis wird zur Basis erweiterbar ja oder wie hier ist noch unabhängig machen und das ist das einzige was teuer sein kann aber das bestimmt wird ist die Laufzeit also Beispiel geniale Jahre Unabhängigkeit in Linien Algebra müsse es also überprüfen indem man die Verleger und Ring trauern es war noch 1 zu ist das neue System aber immer unabhängig und was müssen wir schlimmsten Fall tun Gleichungssystem lösen an also da kann die Laufzeit dann eben noch ja wie nach dem wie gut man das wieder implementiert ich sag es mal in hoch 3 im schlimmsten Fall kostet uns ist am Ende aber das der einzige Knackpunkt ich war es einfach mal 2 Beispiele an genau 2 solche Beispiele wo sich die die die Spreu vom Weizen trennt wenn ich einmal groß Funktionieren einer muss nicht funktioniert dieser Algorithmus leider auch nochmal meine Bemerkung vom letzten Mal die aufgreifen der Mann zieht zuzusagen was Greene letzendlich macht noch mal aus dem Englischen des Gierek gefräßig macht eine Sortierung nach dieser Gewichtung ja und dann geh ich einfach nicht geht einfach in dieser Reihenfolge egal was danach noch kommt und es kann eben doch aus seiner Sicht mit Dini am Anfang kaputt macht dich nein nicht mehr reparieren kann dieser Algorithmus geht nie mehr zurück er guckt auch eine nach vorne außer dass einmal die Gewichte sortiert er das aber auch dieser Begriff Prioritäten Optimierung was mir ich mache mir Prioritätenliste das ist das Sortieren man ging diese Prioritätenliste vor man sich wirklich mal beobachtet dass sich sehr viele Leute wenn sie irgendwie Handlungsentscheidungen treffen die sehr viele gehen nach dieser nach dieser Prioritäten optimieren pro Jahr überlegt sie was sie mir so wichtigstes mach ich zuerst das was 2 diesmal als nächstes und so weiter dass genau dieser Algorithmus eigentlich gut schauen was man verlangen was funktioniert und es funktioniert genau für auch spannende Beueler funktionierts also Anwendungen wir mal ausspannen Mord auch Bäume der also der Satz dazu formulieren gleich ist der Satz 4 viele Kolleginnen liefert mir mal ausspannen bauen in Laufzeit O Formen mal Ende zur Beweis da fangen wir Laufzeit eine schien noch alles da wie das mit der Laufzeit es alles nur sortieren wir sortieren kostet uns allen Block zur dann brauchen wir weil es mir das jetzt laufen also die Schlei gelaufen auch mein +plus n sollen jetzt was kostet mich jetzt bei lieber ausspannen Baum zu überprüfen ob es unabhängiges werden vorher schon gesagt unabhängig bei wollen heißt kreisfrei weil wir angegebene Teilmenge der erkannten wir wollen jetzt getragene kann dazu und wolle entscheiden ist die neue Struktur kreisfrei oder nicht kann man das machen nämlich schon Grafen Algorithmen der damals einer der 1. Algorithmen die so zum Beispiel an das man
läuft einfach wenn wenn ein Knoten an dem die 1. beste kannte läuft die dann ist am nächsten Knoten in der die 1. beste kann der läuft die wenn wenn es nicht mehr weitergeht nämlich die 2. Ereignisse oder Reinfall diesem einen Knoten haben auf die 2. und so weiter und entweder ich kommen irgendwann mal einen Knoten zurück wo ich schon mal war als muss gereist haben aber wenn das nicht der Fall ist ein kranker Greis drin sein wird und ich würde jede kannte nur einmal oder auch Werks noch mal beim zurücklaufen also je zweimal aber das geht im Kosovo die Zweige ist groß und das was wir behalten es ist n ja also mal in so ,komma jetzt auf es ist einmal enden nicht ganz normal zehnmal falsch gemacht oder man falsch abgeschätzt eines der deren kann nun endlich der Knoten alle vorne gelegen gleich mal weg oder das N wie groß is en maximal wandte man sich im Quadrat Kantner ich in über 200 Mehr als Elber zweier wenig dem Grafen also ich bin großzügige in Quadrat also kann ich mal maximalen im Quadrat schreiben wir die 2 geht vor den Block und danke damit geht's ins o ok also Dinge die 2 weg können ja auch noch ändern er also aber schon mal n log n aber wir dummerweise in immer und mal entstehen dass mein noch zum Ende machen wie man das sehen in den ,komma etwa bei dann auch mir die Gurus dort also muss man den noch mal bisschen nachdenken zumindest überprüfen auf gereist Freiheit kann das heißt wie viel Kanten hat in dieser Graph der auf kreisfreie überprüft da hat maximal n ja aber wenn er mehr als Ende der den Kreis drinne hier auf er also hier in dem konnte kleben Fall überbrühe jeweils nur Strukturen höchstens n kannten mentalen also kann ich dann in den Schatten und damit habe man die Laufzeit da unten danke so damit habe die Laufzeit soll es ist die Frage wie gehen wir die Korrektheit hin alles machen wir induktiv Korrektheit bei Induktion ja und zwar dass es soll die Induktion so aussehen nach Karten schadet nach Karten Schritt existierten minimal auf spannender Baum weg wäre mit der Eigenschaft dass Bett wäre wenn ich nur die 1. kannten anschaue E 1 SEK die deckungsgleich sind =ist gleich Bethge wie die geschnitten E 1 bis E K nur also ich schaue mir das einfach an immerhin den Karten Schrittes Algorithmus und als Kriterium nämlich nur die kann ich bislang angeschaut aber nur so wenn ich dann am Schluss gab bei trage ich bin habe ich alle kannten ihn der Mengen damit ist der minimal Ausspanne Baum ist =ist gleich gleich der Wiege wie eh und je zum K gleich 0 ist ok weisen beide leer da ist die Welt in Ordnung machen es gehe man vom kamen S 1 auf K die nur also nur 2 Fälle unterscheiden alle packen jetzt weg die kann Dekade zu und jetzt ist der 1. Fall bekannt enthält unklar ist enthält das heißt wir packen wir nicht dazu das heißt SEK Argumente nicht zu dem Gebiete zu nehmen bis Kanyes eines übergegangen Charlie kann Dekan wir zu Anderson und BKA hier vereinigt EK enthält im Kreis ja dann packen das nicht dazu so nachdem die auf den 1. kamen das Einscannen übereinstimmende weg währender BG und und dem BG bislang noch keine anerkannten also 1. kam es 1 sind muss das Baby auch im Kreis enthalten also daraus folgt sozusagen weg wäre vereinigt eCar enthält auch graues wir haben daraus folgt es auch nicht in diesem optimalen drin war so Einfall fallen der 2. wir packen denn tatsächlich ein also Wege die EK enthält keinen Kreis das heißt kommen 3 in das Baby und soll's wieder da einfach fallen Fall B 1 kann ist auch in den Weg werden ist die Welt in Ordnung ein weiterer das an der Fall ist der 2. und das ist auch das muss normalerweise alle andern scheitert ist wir packen jetzt nach diesem Krieg Kriterium 1 1 1 kannte und optimale Lösung ist die nicht drin weil das könnte es nehmen jene Konstruktion gegen die hinten irgendwas kaputt macht und zwar am anfang Lokal und gewinnen sie bei denen die billigste kannte die Nummer noch möglich ist aber es kann sein diese billigste keine macht der später eine bessere Konstruktion kaputt wo ich sozusagen haben
eigentlich es eine Anzahl an der Kante wird Mindestsumme besser sind als wenn ich die jetzt nehmen dafür nachher teilnehmen muss ja und da braucht man genau diese Eigenschaft dass am Schluss alle Basen gleiche Kardinalität Hammerich gibt das ist sozusagen n bereits jetzt sozusagen mal von intuitiv das Argument warum ich da nix kaputtmachen kann nun also schauen wir uns das mal an soll dieser ist nicht so warum wenn der nicht in der optimalen Lösung drin ist nicht wieder zu nehmen muss den Kreis haben also das sei es daraus folgt ich Weg wäre nehmen und vereinigt EK ja dann Intel dessen Kreis ja die Situation irgendwie so mein Baum und jetzt kommen diese kann Dekan mach Kreisen ist hier ja als wenig bekannte EK dazu wenn wie hier und hab ich hier im Kreis drin ist ein Bildquelle so gezeichnet schau ich mir diesen Kreis an ich weiß dieser Kreise ist nicht in dem BGB wir weil sonst hätte hier zum selig denn gar nicht genommen werden das heißt wenn ich mir das jetzt auf diesem Weg hier anschauen wir diesen Kreis hier anschauen ja unter diesen kranken muss es eine geben die später in der Sortierung kommt kann also daraus folgt es existierten L wenn das Volk es existiert in L größer als ja mit ILS ist Element und bei C der eindeutige Kreis in die Quere vereinigt IKS also irgendwo steht dieses l sondern sie jetzt einfach machen kann diesen einfacher Austausch will ich schaue mir jetzt neue minimal ausspannen warum ich da noch einen Baum an wenn ich den eine und Bilder aus und ich erwidern ausspannen bauen es gibt genau diesen einen Kreis ich muss eine kann der rausnehmen damit bleibt alles aufsparen soll daraus folgt es mal die doppelt gleich vereinigt Eklat e l ist ebenfalls und auch spannender bauen ja und das Geld für die Gewichte RC von billig wäre =ist gleich c also C von der doppelt wir das gleiche Ziel von wie wer +plus c von -minus T von E L nachdem des L weiterhin in der Sortierung kommt ja ist das nicht größer gleich gehen was ist das kleine gleich C von Big wer also muss es auch mal ausspannen sollen nur also ist später Rückkehr auch man mal und wir haben ja die Eigenschaft erfüllt von uns der Induktion so anhören und dann stünde jetzt auch doppelt quer bedrücke übernimmt jetzt die Rolle von den Weg wäre um beide enthalten die Kante Tatsache ist sogar so dass der eher gleiches Gewicht haben muss nun wieder icann sonst geht Lösungen und keine also das Sie mir diese in der die Eigenschaft die minimal Ausspanne Bäume haben wer die man von der Struktur her global nix kaputt und hat funktioniert dieser Collie Ansatz Ton gut gibt es dann noch Fragen dazu nicht schauen uns zum Beispiel an muss nicht funktionieren an roten zurück sagt Problemen so wird nicht gut und an also noch mal zur Erinnerung nein maximiere C und XJ ich wenngleich die IP Formulierung ja gleich 1 bis n A XJ keine gleichen B obgleich 1 bis n sollen XJ soll aus 0 1 1 in AJ zum Video zu an die Eier zum des B alle größer gleich 0 und das war das Rucksack Problemen so was wir jetzt machen also was so offensichtlich nahe legt ist ja wir sortieren jetzt nach der Zielfunktion und das wird sozusagen genau plastisch Collie angewandt um mal Variante des Einzelnen sich Zielfunktion Scully erfahren wieder der leeren Menge an wir sortieren die einfach in in absteigender nicht aufsteigender verfolge die CD das packen einfach rein es geht an wir schauen dass man so ein Beispiel an ist das passiert maximieren n mal x 1 +plus Summe gerade in sind wir nicht alle hat gleich 2 ich habe mal ein Element mehr dazu genommen damit es noch leichter zum Rechnen ist n +plus 1 n -minus 1 mal XJ also das dem Gewicht von allen die an einem allen die nicht von N -minus 1 wir und Name n x 1 +plus Summe der XJ ja kein Gewicht gleich
1 bis n +plus 1 kleiner gleich n so was würde gerieben haben Elemente packt der reinen dies zuerst Zielfunktion hat werden n was die optimale Lösung alle anderen machen eh Opt =ist gleich 2 bis n +plus 1 sehr genau Stück offen wird mir das Ding ausglich Zielfunktion billig -minus 1 mal n so wie bis ins Verhältnis setzt er ist sozusagen kann ist die optimale Lösung Faktor N besser als der Kollegin ich kann das nicht mal also geschweigen das optimale Lösung finden wird beliebig schlecht wenn es groß genug wähle er wird dieses Verfahren beliebig schlecht sich keine meine konstante sprang die angeben was der nächste Schritt wäre wenn ich keine optimale Lösung sind vielleicht einige konstante eingehen dass ich sag ich bin höchstens zweimal so schlecht wird dreimal oder so was geht nicht mehr zuletzt mehr die er sagen es war ja auch doof also man muss es so sagen dessen bis ins Verhältnis setzen QC immer auf die Zielfunktion ja ohne zu gucken wie viel mir dass der von meiner Kapazität unser denn damals wurde die LP Relax Jungen machen während aber auch gesagt das ist optimal LP Erziehung ist ein Gesetz ins Verhältnis also was bringt mir pro Einheit von der Kapazität viel bringt mir das in der Zielfunktion waren auch das können wir versuchen es nennt man Gewichts dichten Kelly Weise ja also immer und es habe ein 1. Beispiel für andere die wie ich den Mann sortiert einfach nach sie doch in wenn man schaut sich an was kostet mich das pro Einheit Mehr also sortiere gemäß dieser Reihenfolge das packt gemäß dieser Reihenfolge rein nein sagen kann man kann als auch wieder aufkreuzt legen diesen Beispiel maximiere x 1 +plus als x 2 Hunde schreiben x 1 +plus als mal x 2 ist kleiner gleich Alfa sowas Partners macht der Gully wir werden in dem Fall sind beide gleich ich keiner dich jetzt so wie sortiere ich keiner dem Epsilon mehr spendieren so sodass garantiert in der Sortierung der einen Tag vor dem 2. ist ja dann packte IG wieder 1 1 ein ja wir Nike den 2 1 1 1 ist er fertig Zielfunktion ist 1 ja und die optimale Lösung wir sollten natürlich als vor größer gleich 1 werden man in den zweier und die Funktion des Alfa so wenig als war beliebig groß machen wird auch diese Verfahren beliebig schlecht also A 7 und A 7 zum Stück zu sagen ich am Anfang Entscheidung darf ohne zu gucken welche Konsequenz ist danach hat keine sei nicht verbauen einfach Lösungen die nicht mehr gut machen kann 7 eigentlich was es mir jetzt mal einfach ohne die wissen draufkommt würden wir jetzt einmal denken wenn man die Rucksack Struktur so schwer ist die eigentlich gar nicht mehr ich hab da die Zahlen so ein bisschen den schon in wenn die Oma wie meine graben Struktur und funktioniert dieser einfache Ansatz und hier funktionieren nicht wer Untergrundes wirklich diese Eigenschaft zu sagen die Kardinalität Eigenschaft von Basen hier um sich ihren dem Beispiel sehen wir das gut das das ist ne Basis ist ein Element das der was ich kann keine weiteren packen und genau das ist auch mir was ist da und die haben eben unterschiedlich Kardinalität Fall sogar drastisch unterschiedliche enthält hier kann man noch ein bisschen was helfen wenn man will wenn man kann wenn man an ganze Zahl erlaubte nicht den 1 dann das waren aber später sehen kriegt meine 2 Approximationen kann man zeigen dass dieses Verfahren nachdem wir hier vorgehen höchstens doppelt so schlecht ist die optimale Lösung an es liegt auch ein Stück weit an 1 fixiert fast so scheint es ist das was es LP Macht ja und wenn es den letzten würde des LP brechen Jahr der letzte der kann Mehr der kann höchstens Gewicht haben so viel wie alle anderen davor sonst werde weiter vorne gekommen das sieht man schon relativ einfach warum kann es sozusagen 2 approximativ ist ja aber ich ganze Zahlen erlaubt mit 0 1 kann ich nur wie man hier sieht einfach so schon aufs Kreuz legen zur diese Eigenschaften diese zusätzliche Eigenschaft immer brauchen wir soll die Unabhängigkeit Systeme dass genau das das alle Basen gleiche Kardinalität haben oder spricht man von Amato Tui soll es wollen anschauen dann gibts netten Satz dazu der erst als sie sagt ja in dem Fall hat finden auch dann wenn der immer die optimale es also ein Unabhängigkeit System der I mit der Eigenschaft dass wir alle 11 eine von die und und B Strich Basen von F folgt dass die Kardinalität von D leichter Kardinalität von -minus ist nur heißt Madrid dann diese Eigenschaften Skript an denn die Nummer hier 3 also wichtig an der Stelle nochmal also immer gern vergessen auch Prüfung oder so als hier noch mal ist für alle Teilnehmer nicht nur für die Erntemenge es so die Gesamtmenge E habe am Beispiel der TSB gesehen dass es da dass es nicht reicht es nur für die Gesamtmenge zu fordern zum per Definition noch es war der Satz formulieren dass die Definition 4 6 also wir definieren den Rang
einer von 11 soll die maximale unabhängige Menge sein also P Basis von 11 wir an von 11. alles daran von 11 und genauso kann man den unter den Rang definieren und unten von 11 ist definiert als das Minimum er war im Bett Basis von 11 ja so und das weiß einfach was man Madrid ja und ist die nächste Bemerkung für Madrider gilt ist dann ein von 11 gleich in einen unteren Rang von es für alle S Teilmenge von E 2 zur Richter vergessen hinzuschreiben heißt unter oder Bank von der so er ist unter beraten in allen beim Madrider jählings stets nur als jede Teilmenge gefordert egal welche Basis nehmen dem gleich Kardinalität also muss Materie das gelten nein sollen es gibt netten Satz von Jenkins der folgendes aus sagt so wir uns das ist wie Brok also das in den wie Algorithmus anschauen will folgende Eigenschaften guten das Minimum über alle diese S schau mal das Verhältnis von unter den Rang zum dann an 1 kann denn das kann immer nach unten abschätzen sie funktions jedoch die optimale Lösung und das ist kleiner gleich 1 also ich armer Verhältnis kollidiert optimale Lösung an offensichtlich keine Gebühr maximal so groß sein so gut sein wie optimale es wenn die Kleinen gleich 1 der schwierige Teil ist das Ziel das gilt für jedes beliebige Maximierungsproblem und Unabhängigkeit System ist auch eine interessante Abschätzung auch das kann man überlegen für stabile Menge natürlich selbst ein Problem damit wir denn diesen Rang abschätzen diesen unseren ragen damit wir sofort mit Qualitätsaussagen für das Verhältnis von dieser Collie Lösungs zu optimales und Madrid haben will aufgrund dieser Eigenschaft steht immer 1 das heißt wie muss sie optimale Lösungen so also das Geld das macht das Ding zu beweisen können wir das noch sollte noch ungefähr hinkriegen also schauen was man dabei sein also wir
gehen davon aus dass einfach C 1 größer gleich dass die schon in dieser Reihenfolge sind wir gleich 10 wir für machen an allen das 1. Element ein ja das Setzen auf 0 wird können auch davon ausgehen dass die alle größer gleich 0 sehen wollen wir werde nie eher negative Elemente reinpacken weil doch die Zielfunktion verschlechtern Sorge definieren jetzt über die 1. Mengen 1 bis soll ei soll einfach die 1. I Elemente seien von einer Grundmenge wobei mir eben diese Sortierung schon voraussetzen und der Einfachheit halber setzen auf Koh genau dieses Verhältnis hier also das Minimum über 11 und doch von F ja also die Eigenschaft zu soll ich noch sagen gilt auch also was man aber sich noch dazu kann sagen als 2. Eigenschaft jedem die es existiere 0 1 Gewichte sogar so es nur das an um wird ja also dem Iran Bedingungen ist also so ungleichen sah tatsächlich scharf ja also mit anderen Worten wenn wir nicht zeigen wenn ich weiss ich hab ne Basis den den Rhein echt kleine seist du oben obendrein dann weiß ich es gibt immer ein Problem dazu für das Ascoli nicht die optimale Lösung finden hallo was brauch meine kleine umformen also ich Teilmenge es habe eine folgende Beziehungen also C von F das ja nichts anders als die Summe über alle INF 10 von ihnen ja das den 3. Kindes kann man nur so schreiben Scheibe 2 Tricks sind wie man das auch formulieren kann I aus 11 soll zu mir ich über ja gleich 1 bis n sie hat -minus J +plus 1 ja das immer wenn ein drauf und dann wieder abziehen Namen des aus Polen witzige sie genau das wieder hin im Moment aber wir sehen dabei I anfangen wir und das können auch anders schreiben alles so man ihn gleich 1 bis n Kardinalität 11 geschnitten II mal CI -minus CIO +plus 1 das kann man sich einfach überlegen es haben wir schon oft zubeißen wenn Operation gesehen haben also trauen die unterschiedliche Schreibweise des gleichen Abschätzung können so wird ein paar Eigenschaften zu
für optimale Lösung und also was wir auf jeden Fall wissen ist nicht die optimale Lösung anschauen und ich schaue mir die auf den 1. I Elementen an ja das ist sicherlich eine Teilmenge von I Ort ja die ob eine unabhängige also folgen
Sie Unabhängigkeit Eigenschaft dass das Ding auch unabhängig ist ja also ob geschnitten Ei ist auch unabhängig nein so ist die 1. Eigenschaft die wir haben die 2. 8. das es auch unabhängiges wissen sofort dass wenn ich mir die Kardinalität von dem Ding anschaue ja dann ist dies sicherlich kleiner gleich dem ja Bank von ja das der maximale an oder den des unabhängigen ist muss der kleine gleich sein so was man auch wissen ist das Ei Greene ja aufgrund der Vorgehensweise es immer maximal unabhängige Menge auf diesem System also das Ding ist Basis von ja meine Pagen ja immer wenn geht mag man einwenden dass es genau dieser Algorithmus also wissen wir das wenn ich mir die Menge an anschauen ist sicherlich größer gleich im unter den Rang von Ihnen warum
sollen damit wir insgesamt also Igli geschnitten II ist sicherlich größer gleich ich weiß dass man solche was dazu ihr Ort geschnitten Ei mal und dann von Ida allein von ihnen so Dame jetzt was alles eingepackt einmal des IGE wie dies Köser gleich den er das haben wir hier und des I ob das kleine wenn hier wir diese beiden ungleichen haben es genau hier sozusagen verbraten so und das das Ding hier bis Kunden ist das Minimum überall ermöglicht sollte Mengen also insbesondere aber die Menge ihr also es ist größer gleich I ob geschnitten III mal Q 1 größeres Minimum über alle möglichen Teilmengen also gilt diese Beziehung also uns Hamas werde schon fertig er solche zum ab Zielfunktion Greeley =ist gleich mehr als wir die Darstellung die wir hier haben ist nichts anderes als Summe i gleich 1 bis n Ike wie geschnitten Ei mal éliminés -minus CI +plus 1 dann nehme diese Abschätzung ihres größer gleich um das QC nach 1. das 1. Handy gleich 1 bis n um mal die Option abgestellten II bald CI -minus CI +plus 1 cool so unabhängig vom Index ist können wir nach vorne packen und dann wenn wir wieder die Formel an die hier steht also ist das gleich um mal sie von ihr ob der so ist genau das was wir zeigen wollten nicht dass es auf die andere Seite bringen Funktion gliedert optimal Ziel Funktionswert ist größer gleich diesen Coup wir so und es den Zusatz den 7 auch relativ einfach einig sagte vielleicht mündlich dazu warum wir dessen angenommen wir was man einfach macht ist wir nehmen uns in dem uns mit Teilmenge F nehmen uns sollen 11 Herodes Minimum angenommen wird das gibt es an das ist eine Teilmenge F ja zu den Detail 2 11 also die Menge das Minimum nie angenommen wird und ob seines einfach die 1. Elemente der 1 Biskra und untergehen hey jetzt die mit den unter denen dieses F hat Base unterschiedlicher Kardinalität und die 1. P viele wer mag ich so maximale unabhängige Menge die genau diesen Unterlagen annimmt ja unergiebig als die Funktion dort über alle 1 drauf diese gesamte was macht der Guidi der Pakt genau diese 1. P Elemente der und damit genau diese und Wagen an ja die optimale Lösung ist aber dann der in der wurde dann er und damit hab ich genau und Beispiel konstruiert und als Zielfunktion 0 1 hat nämlich markiere genau diese 1 Niere war und damit hab ich hier kann ich den Glider einlegen kann die Park einfach die Elemente nach vorne Mehr die dies und dem Drange gegen gibt den ein Gewicht 1 und wir maximal daran auch auf Kunde sortieren Sie ein Smigal und packt es genau in dieser Reihenfolge kriegen in die obere Lösung die optimale sind die unteren wird genau das Verhältnis also damit kann man ja auch so reinlegen damit das nächste Mal vielleicht das Kapitel wird noch mal anfangen wir haben praktisch ist damit an der Tafel wird aufstehen man kann die optimale Lösung findet man man eine Charakterisierung über warten jede wir sehen das genau an dies an an an dieser Stelle hier sehen das geliefert nachdem das Ding hier angenommen wird wer liefert Greeley Kinder und dann in eine optimale Lösung wenn der unter der Wagen gleich dem oberen ist der alle Teilmengen von es war alles genau die Eigenschaft von Madrid also Greeley liefert optimale Lösungen dann und nur dann wenn der hindern Madrid steckt und es einen entscheidenden Aussagen haben bei mir jetzt ein Problem charakterisieren wollen es ,komma nochmal doch kommen diese per litäten optimieren die die gerne sozusagen der Praxis verwendet wird funktioniert nur für Madrider zur sagte dem nicht mal der Mann der nicht was Mix aus Madrid ist aber wenn uns mal die Beispiele nochmal anschauen selbst so einfache Sachen wie die Rucksack Problem oder so oder der man oder oder stabilen wegen mir das sind alles keine Matuidi da kann man leicht des Einfalls Beispiel geben wo das nicht erfüllt ist dann war weiß sich optimiert funktioniert garantiert nicht mehr essen tioniert im Wesentlichen nur für solche einfachen Strukturen in der linearen Algebra linear Unabhängigkeit kommt die Ursprünge der Fiktion oder sowas wie es sozusagen auf spannende worden wären das ist aber eine der ganz wenigen Fälle muss tatsächlich funktioniert auch solche Netzwerk Geschichten also das vielleicht zu sagen jetzt außerhalb der Mathematik vielleicht noch ein Stück weit im Hinterkopf zu behalten dass Bildwelten optimieren wird nicht nur funktionieren Madrid hat und mathematisch gibt es ja nur ganz wenige Fälle wo das auch tatsächlich dann funktioniert wie im Fall ausspannen wollen aber wie die meisten des alten finde in der Praxis auf ihrem täglichen Leben auftauchen sind keine materielle und dann funktioniert auch diese Bildwelten optimieren nicht so viel für heute vielen Dank Entschuldigung für die leichte überziehen
Ebene
Lineare Abhängigkeit
Endlichkeit
Momentenproblem
Vektorrechnung
Algebra
Potenzmenge
Heuristik
Formation <Mathematik>
Computeranimation
Teilmenge
Lösung <Mathematik>
Endliche Menge
Menge
Ganze Abschließung
Lineare Algebra
Stützpunkt <Mathematik>
Lineare Geometrie
Vorlesung/Konferenz
Zielfunktion
Optimierung
Inklusion <Mathematik>
Unabhängige Menge
Schranke <Mathematik>
Kreis
Zusammenhang <Mathematik>
Gewicht <Mathematik>
Welle
Algebra
Minimierung
Baum <Mathematik>
Kante
Computeranimation
Wiener-Hopf-Gleichung
Energie
Knudsen-Zahl
Lineare Geometrie
Stützpunkt <Mathematik>
Vorlesung/Konferenz
Zusammenhängender Graph
Zielfunktion
Unabhängige Menge
Lineare Abhängigkeit
Graph
Vektorrechnung
Gewichtung
Reihe
Vektorraum
Spannender Baum
Teilmenge
Menge
Rundung
Lineare Algebra
Gebiet <Mathematik>
Aggregatzustand
Parametersystem
Kreis
Gewicht <Mathematik>
Graph
Algebra
Laufzeit
Gewichtung
Baum <Mathematik>
Stellenring
Gleichungssystem
Kante
Paarvergleich
p-Block
Spannender Baum
Teilmenge
Quadrat
Menge
Homogenes Polynom
Stützpunkt <Mathematik>
Vorlesung/Konferenz
Optimierung
Gebiet <Mathematik>
Struktur <Mathematik>
Kreis
Approximationstheorie
Faktorisierung
Kreisfläche
Gewicht <Mathematik>
Baum <Mathematik>
Rang <Mathematik>
Kante
Rechnen
Zahl
Dichte <Physik>
Summe
Lösung <Mathematik>
Menge
Ganze Zahl
Stützpunkt <Mathematik>
Vorlesung/Konferenz
Zielfunktion
Teilmenge
Lösung <Mathematik>
Menge
Minimum
Abschätzung
Vorlesung/Konferenz
Rang <Mathematik>
Unabhängige Menge
Teilmenge
Summe
Gewicht <Mathematik>
Momentenproblem
Minimum
Scheibe
Abschätzung
Vorlesung/Konferenz
Zielfunktion
Element <Mathematik>
Unendlichkeit
Lineare Abhängigkeit
Mathematik
Aussage <Mathematik>
Rang <Mathematik>
Teilmenge
Index
Summe
Lösung <Mathematik>
Menge
Minimum
Lineare Geometrie
Abschätzung
Vorlesung/Konferenz
Zielfunktion
Struktur <Mathematik>
Unabhängige Menge

Metadaten

Formale Metadaten

Titel Heuristiken: Der Greedy-Algorithmus
Serientitel Diskrete Optimierung (Optimierung II)
Teil 17
Anzahl der Teile 26
Autor 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/31783
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2009
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...