Dynamiske programmeringsegenskaper, eksempel, fordeler, ulemper

De Dynamisk programmering Det er en algoritmemodell som løser et komplekst problem ved å dele den inn i delproblemer, og lagrer resultatene for å unngå å måtte beregne disse resultatene.

Dette programmet brukes når problemer kan deles inn i lignende delproblemer, slik at resultatene deres kan gjenbrukes. For det meste brukes dette programmet til optimalisering.

Dynamisk programmering. Underproblemer overlagret i Fibonacci -suksessen. Kilde: Wikimedia Commons, at: Bruker: Dcoatzee, sporet av bruker: stannert / offentlig domene

Før du løser de tilgjengelige delproblemene, vil den dynamiske algoritmen prøve å undersøke resultatene fra de tidligere løste delproblemene. Underproblemløsninger kombineres for å oppnå den beste løsningen.

I stedet for å beregne den samme delproblemet igjen og igjen, kan løsningen din lagres i noe minne, når du først møter denne delproblemen. Når det vises igjen under løsningen av et annet underproblem, vil løsningen som allerede er lagret i minnet, bli tatt.

Dette er en fantastisk idé å korrigere tid med hukommelsen, hvor når du bruker ekstra plass, kan du forbedre tiden som kreves for å finne en løsning.

[TOC]

Kjennetegn på dynamisk programmering

Følgende essensielle egenskaper er de som et problem kan brukes for dynamisk programmering:

Optimal underbygning

Denne egenskapen uttrykker at et optimaliseringsproblem kan løses ved å kombinere de optimale løsningene av sekundære problemene som utgjør det. Disse optimale understrukturene er beskrevet ved rekursjon.

I en graf vil for eksempel en optimal understruktur bli presentert på den korteste ruten som går fra et toppunkt til et toppunkt T:

Det vil si at på denne korteste ruten R kan du ta et hvilket som helst mellomleder i. Hvis R virkelig er den korteste ruten, kan den deles inn i subruta R1 (fra S til I) og R2 (fra I til T), slik at disse igjen er de korteste rutene mellom de tilsvarende vertiklene.

For å finne de korteste rutene kan du enkelt formulere løsningen rekursivt, og det er det Floyd-Warshall-algoritmen gjør.

Overlagte delproblemer

Underproblemet må være lite. Det vil si at enhver rekursiv algoritme som løser et problem, må løse de samme delproblemene om og om igjen, i stedet for å generere nye delproblemer.

For eksempel, for å generere Fibonacci-serien, kan denne rekursive formuleringen vurderes: FN = F (N-1) + F (N-2), og tar som en grunnleggende sak at F1 = F2 = 1. Da må du: F33 = F32 + F31, og F32 = F31 + F30.

Som det fremgår av, blir F31 løst i de rekursive underkassene til både F33 og F32. Selv om det totale antallet delproblemer er veldig lite, hvis en rekursiv løsning blir tatt i bruk, da dette vil ende opp med å løse de samme problemene igjen og igjen.

Kan tjene deg: De 7 komponentene i et informasjonssystem

Dette tas i betraktning av dynamisk programmering, så det løser hvert underproblem bare en gang. Dette kan oppnås på to måter:

Topp tilnærming

Hvis løsningen på et hvilket som helst problem kan formuleres rekursivt ved bruk.

Hver gang løsningen av en ny subproblema blir søkt, vil den bli gjennomgått i tabellen hvis den tidligere er løst. I tilfelle en løsning er lagret, vil den bli brukt i stedet for å beregne den igjen. Ellers blir subproblema løst, og lagrer løsningen i tabellen.

Stigende tilnærming

Etter at løsningen av et problem er rekursivt formulert i form av underproblemer, kan problemet prøves oppover: Først vil de prøve å løse underproblemene og bruke løsningene sine for å nå løsningene til de største underproblemene.

Dette gjøres også vanligvis i form av en tabell, og genererer iterative løsninger til stadig større delproblemer ved å bruke løsninger til små delproblemer. For eksempel, hvis verdiene til F31 og F30 allerede er kjent, kan verdien av F32 beregnes direkte.

Sammenligning med andre teknikker

En betydelig tilhørighet av et problem som kan løses ved dynamisk programmering er at det skal ha overlappende delproblemer. Dette er det som skiller den dynamiske programmeringen av teknikken for å dele og erobre, der det ikke er nødvendig å lagre de enkleste verdiene.

Det ligner på rekursjon, siden den endelige verdien ved å beregne basisbasis kan bestemmes induktivt. Denne stigende tilnærmingen fungerer bra når en ny verdi bare avhenger av tidligere beregnede verdier.

Eksempel

Minimumstrinn for å nå 1

For ethvert positivt hele antall “E” kan du utføre et av de følgende tre trinnene.

- Trekk 1 fra nummeret. (E = E-1).

- Hvis det er delbart med 2, er den delt med 2 (hvis e%2 == 0, så e = e/2).

- Hvis det er delbart med 3, er den delt med 3 (hvis e%3 == 0, så e = e/3).

Basert på de foregående trinnene, må du finne minimumsbeløpet for disse trinnene å ta og 1. For eksempel:

- Hvis e = 1, resultat: 0.

- Hvis e = 4, resultat: 2 (4/2 = 2/2 = 1).

- Når e = 7, resultat: 3 (7-1 = 6/3 = 2/2 = 1).

Nærme seg

Du kan alltid tenke på å velge trinnet som gjør n så lavt som mulig og fortsette slik, til det når 1. Det kan imidlertid sees at denne strategien ikke fungerer her.

Kan tjene deg: kommersiell programvare

For eksempel, hvis e = 10, ville trinnene være: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 trinn). Imidlertid er den optimale måten: 10-1 = 9/3 = 3/3 = 1 (3 trinn). Derfor må alle mulige trinn som kan gjøres for hver verdi av n bevises, og velge minimumsbeløp av disse mulighetene.

Det hele begynner med rekursjon: f (e) = 1 + min f (e-1), f (e/2), f (e/3) hvis e> 1, tar som basisvakt: f (1 ) = 0. Når du har tilbakefallsligningen, kan du begynne å kode rekursjonen.

Imidlertid kan det observeres at det har overlagret delproblemer. I tillegg avhenger den optimale løsningen for en gitt inngang av den optimale løsningen av dens delproblemer.

Som i memorering, der løsningene av underproblemene som løses, lagres for å bruke dem senere. Eller som i dynamisk programmering, begynner den nedenfra, og går videre til den gitte e. Neste, begge kodene:

Memorering

Dynamisk programmering oppover

Fordeler

En av hovedfordelene ved å bruke dynamisk programmering er at den akselererer behandlingen, siden referanser som tidligere ble beregnet er brukt. Som en rekursiv programmeringsteknikk, reduserer den programlinjer.

Vorace Algoritmos vs dynamisk programmering

Voracious algoritmer ligner på dynamisk programmering i den forstand at begge er verktøy for optimalisering. Voraz -algoritmen søker imidlertid en optimal løsning i hvert lokalt trinn. Det vil si at den søker et grådig valg med håp om å finne en global optimal.

Derfor kan glupske algoritmer gjøre en antagelse som ser optimal ut på den tiden, men det blir dyrt i fremtiden og garanterer ikke en global optimal.

På den annen side finner dynamisk programmering den optimale løsningen for delproblemer og tar deretter et informert valg ved å kombinere resultatene fra disse delproblemene for å virkelig finne den mest optimale løsningen.

Ulemper

- Mye minne er nødvendig for å lagre det beregnede resultatet av hvert delproblem, uten å kunne sikre at den lagrede verdien vil bli brukt eller ikke.

- Mange ganger lagres utgangsverdien uten noen gang å bli brukt i følgende delproblemer under utførelse. Dette fører til unødvendig bruk av minne.

- I dynamisk programmering kalles funksjonene rekursivt. Dette gjør at batterivinnet forblir i konstant økning.

Rekursivitet vs dynamisk programmering

Hvis du har begrenset minne for å utføre koden og behandlingshastigheten ikke er bekymret, kan rekursivitet brukes. For eksempel, hvis en mobilapplikasjon utvikles, er minnet veldig begrenset til å utføre applikasjonen.

Kan tjene deg: Mixed Devices: Egenskaper og eksempler

Hvis programmet er ønsket å utføres raskere og det ikke er noen minnebegrensninger, er det å foretrekke å bruke dynamisk programmering.

applikasjoner

Dynamisk programmering er en effektiv metode for å løse problemer som ellers kan virke ekstremt vanskelig å løse på rimelig tid.

Algoritmer basert på dynamisk programmeringsparadigme brukes i mange vitenskapsområder, inkludert mange eksempler innen kunstig intelligens, fra oppløsningen av planleggingsproblemer til stemmegjenkjenning.

Dynamiske programmeringsalgoritmer

Dynamisk programmering er ganske effektiv og fungerer veldig bra for et bredt spekter av problemer. Mange algoritmer kan sees på som anvendelser av glupske algoritmer, for eksempel:

- Fibonacci Numbers Series.

- Hanoi Towers.

- Alle de korteste rutene par av Floyd-Warshall.

- Ryggsekk.

- Prosjektprogrammering.

- Den korteste banen av Dijkstra.

- Robotikkflykontroll og kontroll.

- Matematiske optimaliseringsproblemer.

- Delt tid: Programmer arbeidet for å maksimere bruken av CPU.

Fibonacci Numbers Series

Fibonacci -tall er tallene som er funnet i følgende sekvens: 0, 1, 1, 3, 5, 8, 13, 21, 34, 55, 89, 144, etc.

I matematisk terminologi er FN -suksessen av fibonacci -tall definert av gjentakelsesformelen: f (n) = f (n -1) + f (n -2), hvor f (0) = 0 og f (1) = 1.

Topp tilnærming

I dette eksemplet initialiseres en søkematrise med alle startverdier med -1. Hver gang løsningen på et underproblem er nødvendig, vil det først bli søkt i denne søkematrisen.

Hvis det er den beregnede verdien, vil den verdien bli returnert. Ellers blir resultatet beregnet for å lagre det i søkematrisen og dermed kunne gjenbruke det senere.

Stigende tilnærming

I dette tilfellet, for den samme Fibonacci -serien, F (0), deretter F (1), F (2), F (3), og så videre beregnes først. Dermed vil løsningene av underproblemene fra bunnen bygges.

Referanser

1. Vineet Choudhary (2020). Introduksjon til dynamisk programmering. UNVOOPER -innsider.Hentet fra: DeveloperInsider.co.
2. Alex Allain (2020). Dynamisk programmering i C++. C programmering. Hentet fra: CPROGRAMMMING.com.
3. Etter akademi (2020). Ide om dynamisk programmering. Hentet fra: Afteracademy.com.
4. Aniruddha Chaudhari (2019). Dynamisk programmering og rekursjon | Annerledes. CSE -stabel. Hentet fra: csestack.org.
5. Kodekokk (2020). For dynamisk programmeringsopplæring. Hentet fra: codhef.com.
6. Programiz (2020). Dynamisk programmering. Hentet fra: Programiz.com.