Dynamisk programmering

Dynamisk programmering i kontrolteori og computersystemteori er en måde at løse komplekse problemer på ved at opdele dem i enklere delopgaver. Den er anvendelig til problemer med optimal understruktur, som ligner et sæt overlappende underproblemer, hvis kompleksitet er lidt mindre end den oprindelige. I dette tilfælde kan beregningstiden, sammenlignet med de "naive" metoder, reduceres betydeligt.

Nøgleideen i dynamisk programmering er ret enkel. For at løse problemet kræves det som regel at løse separate dele af problemet (delproblem), og derefter kombinere løsningerne af delopgaverne til én fælles løsning. Ofte er mange af disse delopgaver de samme. Den dynamiske programmeringstilgang er kun at løse hvert delproblem én gang og derved reducere antallet af beregninger. Dette er især nyttigt i tilfælde, hvor antallet af tilbagevendende delopgaver er eksponentielt stort.

Metoden til dynamisk programmering fra oven er en simpel huske af resultaterne af at løse de underproblemer, der kan støde på igen i fremtiden. Dynamisk programmering nedefra involverer omformulering af et komplekst problem som en rekursiv sekvens af enklere delproblemer.

Historie

Udtrykket "dynamisk programmering" blev første gang brugt i 1940'erne af Richard Bellman til at beskrive processen med at finde en løsning på et problem, hvor svaret på et problem kun kan opnås efter at have løst problemet "forud" det. I 1953 forfinede han denne definition til den moderne. Feltet blev oprindeligt grundlagt som systemanalyse og teknik, som blev anerkendt af IEEE . Bellmans bidrag til dynamisk programmering er blevet udødeliggjort i navnet på Bellman-ligningen , et centralt resultat af dynamisk programmeringsteori, der omformulerer et optimeringsproblem i en rekursiv form.

Ordet "programmering" i sætningen "dynamisk programmering" har faktisk næsten intet at gøre med "traditionel" programmering (skrive kode) og giver mening som i udtrykket " matematisk programmering ", der er synonymt med ordet "optimering". Derfor betyder ordet "program" i denne sammenhæng snarere den optimale rækkefølge af handlinger for at opnå en løsning på problemet. For eksempel omtales en bestemt tidsplan for begivenheder på en udstilling nogle gange som et program. Programmet i dette tilfælde forstås som et gyldigt hændelsesforløb.

Ideen om dynamisk programmering

En optimal understruktur i dynamisk programmering betyder, at en optimal løsning på mindre delproblemer kan bruges til at løse det oprindelige problem. For eksempel kan den korteste vej i en graf fra et toppunkt (angivet med s) til et andet (angivet med t) findes som følger: først betragter vi den korteste vej fra alle hjørner, der støder op til s til t, og tager derefter under hensyntagen til vægten af de kanter, der forbinder s med tilstødende hjørner, vælger vi den bedste vej til t (hvilket toppunkt er bedst at gå igennem). I det generelle tilfælde kan vi løse et problem, der har en optimal understruktur ved at udføre de følgende tre trin.

Opdeling af en opgave i mindre delopgaver.
At finde den optimale løsning på delproblemer rekursivt ved at udføre den samme tretrinsalgoritme .
Brug af den opnåede løsning af delopgaver til at konstruere en løsning på det oprindelige problem.

Delproblemer løses ved at dele dem op i endnu mindre delproblemer, og så videre, indtil de når frem til det trivielle tilfælde af et problem, der kan løses i konstant tid (svaret kan siges med det samme). For eksempel, hvis vi skal finde n!, så 1! = 1 (eller 0!=1).

Overlappende delproblemer i dynamisk programmering betyder delproblemer, der bruges til at løse en række problemer (ikke kun én) af større størrelse (det vil sige, at vi gør det samme flere gange). Et slående eksempel er beregningen af Fibonacci-sekvensen , og - selv i et så trivielt tilfælde, har vi allerede talt beregningerne af kun to Fibonacci-tal to gange. Hvis du fortsætter videre og tæller , vil det blive talt to gange mere, siden igen og vil være nødvendigt for beregningen . Det viser sig følgende: En simpel rekursiv tilgang vil bruge tid på at beregne en løsning på problemer, som den allerede har løst. $F_{3}=F_{2}+F_{1}$ $F_{4}=F_{3}+F_{2}$ $F_{2}$ $F_{5}$ $F_{2}$ $F_{5}$ $F_{3}$ $F_{4}$

For at undgå et sådant hændelsesforløb vil vi gemme løsningerne på de delproblemer, som vi allerede har løst, og når vi igen skal bruge løsningen på delproblemet, vil vi i stedet for at genberegne det blot hente det fra hukommelsen. Denne tilgang kaldes memorisering . Du kan også udføre yderligere optimeringer - hvis vi for eksempel er sikre på, at vi ikke længere skal løse en delopgave, kan vi smide den ud af hukommelsen, frigøre den til andre behov, eller hvis processoren er inaktiv, og vi ved, at løsningen af nogle delopgaver, som endnu ikke er beregnet, vi skal bruge i fremtiden, kan vi løse dem på forhånd.

Sammenfattende ovenstående kan vi sige, at dynamisk programmering bruger følgende egenskaber ved problemet:

overlappende underopgaver;
optimal underbygning;
evnen til at huske løsningen af hyppigt forekommende delopgaver.

Dynamisk programmering følger generelt to tilgange til problemløsning:

Top-down dynamisk programmering: Problemet er opdelt i mindre delproblemer, de løses og kombineres derefter for at løse det oprindelige problem. Memorisering bruges til at løse allerede løste delopgaver.
bottom-up dynamisk programmering: alle delopgaver, der efterfølgende skal til for at løse det oprindelige problem, beregnes på forhånd og bruges derefter til at bygge en løsning på det oprindelige problem. Denne måde er bedre end top-down programmering i forhold til størrelsen af den nødvendige stak og antallet af funktionskald, men nogle gange er det ikke nemt at finde ud af på forhånd, hvilke delproblemer vi skal løse i fremtiden.

Programmeringssprog kan huske resultatet af et funktionskald med et bestemt sæt argumenter ( memoization ) for at fremskynde "beregning efter navn". Nogle sprog har denne funktion indbygget (f.eks . Scheme , Common Lisp , Clojure , Perl , D ), mens andre kræver yderligere udvidelser ( C++ ).

Kendt er seriel dynamisk programmering, som er inkluderet i alle lærebøger om operationsforskning , og ikke-seriel dynamisk programmering (NSDP), som i øjeblikket er dårligt kendt, selvom det blev opdaget i 1960'erne.

Konventionel dynamisk programmering er et særligt tilfælde af ikke-seriel dynamisk programmering, hvor variabelforholdsgrafen kun er en sti. NSDP, som er en naturlig og generel metode til at tage højde for strukturen af et optimeringsproblem, betragter et sæt begrænsninger og/eller en objektiv funktion som en rekursivt beregnelig funktion. Dette gør det muligt at finde en løsning trin for trin på hvert trin ved hjælp af informationen opnået i de foregående trin, og effektiviteten af denne algoritme afhænger direkte af strukturen af den variable relationsgraf. Hvis denne graf er tilstrækkelig sparsom, kan mængden af beregninger på hvert trin holdes inden for rimelige grænser.

En af hovedegenskaberne ved problemer løst ved hjælp af dynamisk programmering er additivitet . Ikke-additive problemer løses ved andre metoder. For eksempel er mange opgaver med at optimere en virksomheds investeringer ikke-additive og løses ved at sammenligne virksomhedens værdi med og uden investeringer.

Klassiske problemer med dynamisk programmering

Længste fælles undersekvensproblem : Givet to sekvenser skal du finde den længste fælles undersekvens.
Opgaven med at finde den største stigende undersekvens : givet en sekvens er det nødvendigt at finde den længst stigende undersekvens.
Redigeringsafstandsproblem (Levenshtein-afstand) : givet to strenge er det nødvendigt at finde det mindste antal sletninger, udskiftninger og tilføjelser af tegn, der omdanner en streng til en anden.
Problemet med at beregne Fibonacci-tal
Problemet med rækkefølgen af matrixmultiplikation : givne matricer , ..., , er det nødvendigt at minimere antallet af skalaroperationer for deres multiplikation. $A_{1}$ $A_{n}$
Problemet med at vælge en bane
Sekventielt beslutningsproblem
Problemet med brugen af arbejdskraft
Lagerstyringsudfordring
Rygsækproblemet : fra et ubegrænset sæt varer med egenskaberne "pris" og "vægt" er det nødvendigt at vælge et bestemt antal varer på en sådan måde, at man opnår den maksimale samlede pris med en begrænset totalvægt.
Floyd-Warshall-algoritme : find de korteste afstande mellem alle hjørner af en vægtet rettet graf.
Bellman-Ford algoritme : find den korteste vej i en vægtet graf mellem to givne hjørner.
Maksimalt uafhængigt sæt toppunkter i et træ : givet et træ, find det maksimale sæt toppunkter, hvoraf ikke to er forbundet med en kant.
Opgaven med at planlægge transportøren : der er to transportører, hver med job. Tidspunkterne for arbejdet på hver transportør, påsætning og fjernelse af den, samt tidspunktet for flytning til et nabosted, er angivet. Du ønsker at bestemme den hurtigste måde at samle en del på ved hjælp af begge transportører. $n$

Litteratur

Bellman R. Dynamisk programmering. - M .: Forlag for udenlandsk litteratur , 1960.
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, C. Kapitel 15. Dynamisk programmering // Algoritmer: Konstruktion og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .
Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. algoritmer . - McGraw-Hill Science / Engineering / Math, 2006. - 336 s. — ISBN 0073523402 .
Akulich I. L. Kapitel 4. Problemer med dynamisk programmering // Matematisk programmering i eksempler og problemer. - M . : Højere skole , 1986. - 319 s. — ISBN 5-06-002663-9 .
Bertele U., Brioshi F. Ikke-seriel dynamisk programmering. - NY: Academic Press, 1972. - 235 s.
Gabasov R. , Kirillova F. M. Grundlæggende om dynamisk programmering. -Mn. : BSU Forlag, 1975. - 262 s.

Links

Videoforedrag om dynamisk programmering
Teori, opgaver, testsystem .

Ordbøger og encyklopædier

I bibliografiske kataloger
BNE : XX543843 BNF : 11978098s GND : 4125677-3 J9U : 987007567971605171 LCCN : sh85040313 NDL : 00571739