Dynamische Programmierung und Greedy - Grundlagen
JuSa
https://www.youtube.com/watch?v=wAn1kY2loHU

Transkript (automatisch erstellt)

0:00 haye ist sarah hier heute erzähle ich euch etwas zur dynamischen programmierung und kreativ erfahren wann wir diese anwenden und was das überhaupt
0:09 ist fangen wir an mit der dynamischen programmierung der ursprung von der dynamischen programmierung liegt in die
0:17 wartung conquer das kennt ihr vielleicht von verfahren wie zum beispiel dem merger sword im prinzip haben wir mehrere schritte am anfang haben wir
0:25 unser problem in unabhängige teilproblem anschließend lösen wir diese probleme und im letzten schritt setzen wir unsere teillösungen wieder zusammen und haben
0:33 daraus unsere gesamt problem gelöst der unterschied zwischen der dynamischen programmierung und die weithin konkret sieht wie folgt aus
0:40 bei die weiteren konkret würden wir identische probleme immer und immer wieder lösen bedeutet wenn wir das gleiche problem zehnmal haben dann
0:48 würden wir es zehnmal lösen bei den dynamischen programmierungen müssten wir was die lösung von diesem teil problem ist werden sie einmal berechnen und
0:55 anschließend wieder verwenden das bedeutet wenn wir viele identische probleme haben dann ist die dynamischen programmierung besser als die weitere
1:03 konter aber für was für eine art probleme eignet sich dem dynamische programmierung überhaupt das sind so genannte optimierungs problem das
1:14 bedeutet wir haben probleme bei denen wir zum beispiel ein minimum maximum finden möchten beispiele dafür wäre zum beispiel die
1:20 matrix ketten multiplikation oder wenn wir eine gemeinde die längste gemeinsame teil folge von zwei strings zum beispiel finden wollen würden das wären probleme
1:29 die man sehr gut mit der dynamischen programmierung lösen kann vor allem ist ein problem gut mit der dynamischen programmierens lösen bei
1:37 denen wir viele abhängige teil probleme haben so wie ich eben schon erklärt habe merken wir uns nämlich diese probleme können sie immer und wieder
1:43 wiederverwenden und eben genau das ist die grundidee wir speichern die lösung von problemen dafür können wir zum beispiel tabellen
1:54 verwenden identische probleme müssen so nicht doppelt gelöst werden woraus folgt dass wir eine laufzeit verbesserungen haben und diese laufzeit verbesserung
2:02 ist nicht zu unterschätzen wenn wir vorher ein problem haben dass wir eine exponentielle laufzeit lösen müssten was unfassbar schlecht ist wie ein computer
2:10 das problem kann bedürftigen schon programmierungen nun im polynja laufzeit lösen war es wiederum super für den computer ist aber wie gehen wir vor
2:19 wenn wir ein problem mittels der dynamischen programmierung lösen möchten wir haben insgesamt vier schritte im ersten schritt überlegen wir uns was
2:28 denn die struktur einer optimalen lösung ist im zweiten schritt überlegen wir uns eine rezensions gleichung im dritten schritt brächte wir den wert einer
2:37 optimalen lösung spricht das minimum oder das maximum wenn wir beispielsweise einen weg von a nach b berechnen möchten dann würde uns
2:44 dieser schritt sagen die strecke ist beispielsweise 200 kilometer lang wenn wir den kürzesten weg finden wollen die kürzeste weg sind 200 kilometer
2:51 der vierte schritt er würde dann einer optimalen müssen konstruieren das wäre dann sozusagen aus unserem vorherigen erkenntnissen würden wir hingehen uns
2:59 dann wirklich diese route überlegen beziehungsweise würden diese gute nachvollziehen und dann zum beispiel mit unserem navigationssystem eben von a
3:06 nach b kommen innerhalb dieser 200 kilometer der vierte schritt kann beispielsweise aufgefallen wenn die ja weg dann aber
3:14 gar nicht interessant ist unbeweglich nun herausfinden möchten was ist dann sozusagen unsere minimale router oder unsere minimale distanz von punkt a zu b
3:23 so jetzt habe ich euch die grundlagen zur dynamischen programmierung erklärt und möchte im folgenden etwas auf glee die eingehen wann und wofür verwenden
3:32 überhaupt rudi wie die ist genauso wie die dynamische programmierungen ein verfahren mit denen wir optimierungs probleme lösen können
3:38 das bedeutet wir wollen wieder ein minimum oder im maximum finden im allgemeinen kann man sagen dass algorithmen bei den begriff verwenden
3:46 eine kürzere laufzeit haben als die all gruppen mit der dynamischen programmierung allerdings haben wie verfahren auch ein
3:53 nachteil sie haben nämlich höhere anforderungen an das problem zumindest wenn man die probleme optimal lösen möchte bei credit gehen wir nämlich volk
4:02 vor wir lösen teil probleme lokal das bedeutet wir nehmen die lösung die uns zu einem gewissen zeitpunkt am besten erscheint ohne das globale wissen
4:10 bedeutet wir schauen uns nicht jede mögliche lösung an das bedeutet wir treffen zuerst eine entscheidung und werden unser
4:18 teilproblem erst danach bei den dynamischen programmierung ist das genau andersherum die kritik können wir so uns lösungen
4:26 annähernd für np hatte probleme können diese probleme aber immer noch nicht optimal lösen so nun überlegen wir uns wann wir eine optimale lösung erhalten
4:34 wenn wir die diebe nutzen und zwar haben wir da im prinzip zwei voraussetzungen und zwar brauchen wir bei credit einmal die teilproblem eigenschaft die muss
4:43 erfüllt sein das bedeutet sozusagen das werden wir unsere teilproblem optimal lösen dann haben wir unser gesamtproblem auch
4:49 optimal gelöst sprich die zusammengesetzten teil problemlösung ergeben unsere lösung für das gesamtproblem dass es die teilproblem
4:56 eigenschaft und die wie die eigenschaft besagt dass wir dies sehr ähnlich dass wir die lokal gelösten teil probleme optimal lösen
5:04 das bedeutet dass wir auch wenn wir kein globales wissen über unsere teil probleme haben dass wir sie trotzdem lokal optimal lösen können
5:12 das erfüllt es dann kriegen wir mit kuli eine optimale lösung die dynamische programmierung ist etwas einfacher
5:18 bei der brauch wir nur die teilproblem eigenschaft das bedeutet wenn die erfüllt es dann die von uns die dynamische programmierung eben eine
5:26 optimale lösung wie gesagt der nachteil hierbei ist dass die dynamische programmierung in der regel länger braucht als greely verfahren
5:33 zusammengefasst wann also verwenden the greedy und wann die dynamische programmierung wie verwenden wir genau dann wenn die grün die eigenschaft
5:41 erfüllt ist oder wie möglichst schnell zu einer lösung kommen möchten zum beispiel bei einem mp hat ein problem und die optimale lösung zweitrangig es
5:50 spricht wir wollen nur eine annäherung und nicht das genaue ergebnis die dynamische programmierung verwenden wir genau dann falls wir eine optimale
5:58 lösung erzielen möchten und uns die laufzeit erst mal egal ist oder zweitrangig das waren so die wichtigsten punkte zur dynamischen programmierung
6:08 und sowie die wissen und wann er welches verfahren verwenden sollte ich hoffe das video hat euch gefallen in zukunft werde ich nochmal darauf
6:15 eingehen welche probleme man mit den jeweiligen verfahren zu lösen kann wer da einige beispiele geben und die mal von vorn bis hinten zeigen wie das ganze
6:23 funktioniert wenn ihr fragen habt dann schreibt die gerne in die kommentare und ja wir hören uns wieder