Dynamisk programmering, grunnleggende prinsipper

Å velge den optimale løsningen når du utførerprogrammeringsoppgaver trenger noen ganger å gå gjennom et stort antall datakombinasjoner, som laster minnet til PCen. Slike metoder inkluderer for eksempel "divide and conquer" programmeringsmetoden. I dette tilfellet sørger algoritmen for separering av oppgaven i individuelle små undertaker. Denne metoden brukes kun i tilfeller der de små delene er uavhengige av hverandre. For å unngå unødvendig arbeid i tilfelle at subtasker er gjensidig avhengige, brukes metoden for dynamisk programmering foreslått av American R. Bellman på 1950-tallet.

Essensen av metoden

Dynamisk programmering består i å bestemme den optimale løsningen av et n-dimensjonalt problem, og dele det i n separate trinn. Hver av dem er en deloppgave med hensyn til en variabel.

Den største fordelen med denne tilnærmingen erå vurdere at utviklere er engasjert i endimensjonale optimaliseringsoppgaver av deltakere i stedet for det n-dimensjonale problemet, og løsningen av hovedoppgaven er samlet "fra bunnen av".

Det er hensiktsmessig å bruke dynamiskprogrammering i de tilfeller hvor deltakene er sammenhengende, dvs. har felles moduler. Algoritmen gir en løsning på hver av deltakene en gang, og svarene lagres i et spesialtabell. Dette gjør det mulig å ikke beregne svaret igjen når det oppstår en lignende underoppgave.

Oppgaven med dynamisk programmering løserspørsmålet om optimalisering. Forfatteren av denne metoden R. Bellman formulerte prinsippet om optimalitet: uansett den opprinnelige tilstanden ved hvert trinn og løsningen bestemt ved dette trinnet, velges alle følgende for å være optimale med hensyn til tilstanden som systemet tar ved slutten av trinnet.

Metoden forbedrer ytelsen til oppgaver som løses ved å søke varianter eller rekursjoner.

Konstruksjon av algoritmen til problemet

Dynamisk programmering antarkonstruksjonen av en algoritme for problemer der oppgaven er delt inn i to eller flere deloppgaver, slik at løsningen kan dannes fra den optimale løsningen av alle deltakene som er inkludert i den. Videre blir det nødvendig å skrive et tilbakevendingsforhold og beregne den optimale verdien av parameteren for problemet som helhet.

Noen ganger, i det tredje trinnet, må du huske i tillegg noen tilleggsinformasjon om fremdriften i hver deloppgave. Dette kalles omvendt.

Anvendelse av metoden

Dynamisk programmering brukes når det er to karakteristiske funksjoner:

• optimalitet for deltakere;
• Tilstedeværelse av overlappende deltakere i problemet.

Løse optimaliseringsproblemet ved hjelp av metodendynamisk programmering, må du først beskrive løsningens struktur. Problemet er optimalt hvis løsningen av problemet består av de optimale løsningene av delene. I dette tilfellet anbefales det å bruke dynamisk programmering.

Den andre egenskapen til problemet, viktig for en gittmetode, et lite antall deltakere. Den rekursive løsningen av problemet bruker de samme overlappende delene, hvorav antallet avhenger av størrelsen på den opprinnelige informasjonen. Svaret lagres i et spesialtabell, og programmet sparer tid ved å bruke disse dataene.

Bruken av dynamiskProgrammering, når, på fordelene av problemet, må avgjørelser gjøres i etapper. For eksempel, sett et enkelt eksempel på oppgaven med å erstatte og reparere utstyr. Anta at dekkene på støperiet til et dekkproduksjonsanlegg produseres samtidig i to forskjellige former. Hvis en av skjemaene feiler, må du demontere maskinen. Det er klart at det noen ganger er mer fordelaktig å erstatte den andre skjemaet for ikke å demontere maskinen i tilfelle, og dette skjemaet vil være ineffektivt i neste trinn. Videre er det lettere å erstatte begge arbeidsformer før de begynner å mislykkes. Metoden for dynamisk programmering bestemmer den beste strategien i spørsmålet om å erstatte slike former, med tanke på alle faktorer: fordelen ved å fortsette driften av skjemaer, tapet fra tomgangsmaskiner, kostnaden for avviste dekk og mer.