DYNAMISK PROGRAMMERING: KARAKTERISTIKA, EKSEMPEL, FORDELE, ULEMPER - TEKNOLOGI - 2025

Den dynamiske programmering er en modelalgoritme, der løser et komplekst problem ved at opdele det i delproblemer, lagre resultaterne deraf for at undgå at skulle beregne resultaterne igen.

Denne tidsplan bruges, når du har problemer, der kan opdeles i lignende underproblemer, så deres resultater kan genbruges. For det meste bruges denne plan til optimering.

Dynamisk programmering. Underproblemer overlejret i Fibonacci-sekvensen. Kilde: Wikimedia commons, da: Bruger: Dcoatzee, sporet af Bruger: Stannet / Public domain

Før den tilgængelige delproblem løses, vil den dynamiske algoritme forsøge at undersøge resultaterne af de tidligere løste delproblemer. Løsningerne til delproblemerne kombineres for at opnå den bedste løsning.

I stedet for at beregne det samme underproblem igen og igen, kan du gemme din løsning i en vis hukommelse, når du første gang støder på dette underproblem. Når den vises igen under løsningen af ​​et andet underproblem, tages den løsning, der allerede er gemt i hukommelsen.

Dette er en vidunderlig idé til fastsættelse af hukommelsestid, hvor brug af ekstra plads kan forbedre den tid, der kræves for at finde en løsning.

Funktioner i dynamisk programmering

Følgende væsentlige egenskaber er, hvad du skal have et problem med, før dynamisk programmering kan anvendes:

Optimal understruktur

Denne egenskab udtrykker, at et optimeringsproblem kan løses ved at kombinere de optimale løsninger af de sekundære problemer, der omfatter det. Disse optimale substrukturer er beskrevet ved rekursion.

For eksempel i en graf præsenteres en optimal understruktur i den korteste sti r, der går fra en toppunkt s til en toppunkt t:

Det vil sige, på denne korteste sti r kan enhver mellemliggende toppunkt i tages. Hvis r virkelig er den korteste rute, kan den opdeles i undergrænserne r1 (fra s til i) og r2 (fra i til t) på en sådan måde, at disse igen er de korteste ruter mellem de tilsvarende knudepunkter.

Derfor, for at finde de korteste stier, kan løsningen let formuleres rekursivt, hvilket er, hvad Floyd-Warshall-algoritmen gør.

Overlappende delproblemer

Underproblemrummet skal være lille. Det vil sige, enhver rekursiv algoritme, der løser et problem, skal løse de samme underproblemer igen og igen i stedet for at generere nye underproblemer.

For at generere Fibonacci-serien kan vi for eksempel overveje denne rekursive formulering: Fn = F (n - 1) + F (n - 2), som et grundlæggende tilfælde at F1 = F2 = 1. Så vil vi have: F33 = F32 + F31 og F32 = F31 + F30.

Som du kan se, bliver F31 løst til de rekursive undertræer i både F33 og F32. Selvom det samlede antal delproblemer virkelig er lille, hvis du vedtager en rekursiv løsning som denne, vil du ende med at løse de samme problemer igen og igen.

Dette tages i betragtning ved dynamisk programmering, så det løser hvert underproblem kun én gang. Dette kan opnås på to måder:

Top-down tilgang

Hvis løsningen på ethvert problem kan formuleres rekursivt ved hjælp af løsningen af ​​dets underproblemer, og hvis disse underproblemer overlapper hinanden, kan løsningerne til underproblemerne let huskes eller gemmes i en tabel.

Hver gang der søges i en ny underproblemløsning, kontrolleres tabellen for at se, om den tidligere blev løst. Hvis der opbevares en løsning, bruges den i stedet for at beregne den igen. Ellers bliver underproblemet løst ved at gemme løsningen i tabellen.

Bund-up tilgang

Når løsningen af ​​et problem er formuleret rekursivt med hensyn til dets underproblemer, kan der gøres et forsøg på at omformulere problemet på en stigende måde: Først vil vi forsøge at løse delproblemerne og bruge deres løsninger til at nå frem til løsninger på de større delproblemer.

Dette gøres også generelt i tabelform, idet det generativt genereres løsninger til større og større underproblemer ved at bruge løsninger til mindre underproblemer. For eksempel, hvis værdierne af F31 og F30 allerede er kendte, kan værdien af ​​F32 beregnes direkte.

Sammenligning med andre teknikker

Et væsentligt træk ved et problem, der kan løses ved dynamisk programmering, er, at det skal have overproblemer, der overlapper hinanden. Det er det, der adskiller dynamisk programmering fra skillet og erobringsteknikken, hvor det ikke er nødvendigt at gemme de enkleste værdier.

Det ligner rekursion, da den endelige værdi kan beregnes induktivt ved beregning af basissager. Denne bottom-up-tilgang fungerer godt, når en ny værdi kun afhænger af tidligere beregnede værdier.

Eksempel

Minimum trin for at nå 1

For ethvert positivt heltal "e" kan et af de følgende tre trin udføres.

- Træk 1 fra tallet. (e = e-1).

- Hvis det kan deles med 2, er det divideret med 2 (hvis e% 2 == 0, så e = e / 2).

- Hvis det kan deles med 3, divideres det med 3 (hvis e% 3 == 0, så e = e / 3).

Baseret på ovenstående trin, skal minimum antallet af disse trin findes for at bringe e til 1. F.eks.:

- 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).

Fokus

Man kan tænke på altid at vælge det trin, der gør n så lavt som muligt og fortsætte som dette, indtil det når 1. Det kan dog ses, at denne strategi ikke fungerer her.

For eksempel, hvis e = 10, ville trinnene være: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 trin). Den optimale form er imidlertid: 10-1 = 9/3 = 3/3 = 1 (3 trin). Derfor skal alle mulige trin, der kan udføres for hver værdi af n fundet, forsøges, idet du vælger det mindste antal af disse muligheder.

Det hele starter med rekursion: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} hvis e> 1, der tager som basis case: F (1) = 0. Når du har gentagelsesligningen, kan du begynde at kode rekursionen.

Imidlertid kan det ses, at det har overlappende delproblemer. Desuden afhænger den optimale løsning for et givet input af den optimale løsning af dets underproblemer.

Som i memorering, hvor opløsningerne af delproblemerne, der er løst, gemmes til senere brug. Eller som ved dynamisk programmering, du starter i bunden og arbejder dig op til den givne e. Så begge koder:

memorization

Dynamisk bottom-up programmering

Fordel

En af de største fordele ved at bruge dynamisk programmering er, at det fremskynder behandlingen, da der tidligere blev beregnet referencer. Da det er en rekursiv programmeringsteknik, reducerer den kodelinjerne i programmet.

Gådefulde algoritmer vs dynamisk programmering

Grådige algoritmer ligner dynamisk programmering, idet de begge er værktøjer til optimering. Den grådige algoritme ser dog efter en optimal løsning på hvert lokalt trin. Det vil sige, det søger et grådigt valg i håb om at finde et globalt optimalt.

Derfor kan grådige algoritmer antage en antagelse, der ser optimal ud på det tidspunkt, men bliver dyr i fremtiden og ikke garanterer en global optimal.

På den anden side finder dynamisk programmering den optimale løsning til underproblemerne og træffer derefter et informeret valg ved at kombinere resultaterne af disse underproblemer for faktisk at finde den mest optimale løsning.

Ulemper

- Der er brug for en masse hukommelse for at gemme det beregnede resultat af hvert underproblem uden at kunne garantere, at den gemte værdi vil blive brugt eller ej.

- Mange gange lagres outputværdien uden nogensinde at blive brugt i de følgende underproblemer under udførelsen. Dette fører til unødvendig hukommelsesbrug.

- I dynamisk programmering kaldes funktioner rekursivt. Dette holder stakhukommelsen konstant stigende.

Rekursion vs dynamisk programmering

Hvis du har begrænset hukommelse til at køre din kode, og behandlingshastigheden ikke er et problem, kan du bruge rekursion. For eksempel, hvis du udvikler en mobilapplikation, er hukommelsen meget begrænset til at køre applikationen.

Hvis du vil have programmet til at køre hurtigere og ikke har nogen hukommelsesbegrænsninger, foretrækkes det at bruge dynamisk programmering.

Applikationer

Dynamisk programmering er en effektiv metode til at løse problemer, der ellers kan virke ekstremt vanskelige at løse i en rimelig tidsperiode.

Algoritmer baseret på det dynamiske programmeringsparadigme bruges i mange videnskabelige områder, herunder mange eksempler inden for kunstig intelligens, fra planlægning af problemløsning til talegenkendelse.

Algoritmer baseret på dynamisk programmering

Dynamisk programmering er ret effektiv og fungerer meget godt til en lang række problemer. Mange algoritmer kan ses som grådige algoritmeapplikationer, såsom:

- Fibonacci-nummerserie.

- Tårnene i Hanoi.

- Alle par kortere ruter gennem Floyd-Warshall.

- Rygsækproblem.

- Projektplanlægning.

- Den korteste vej gennem Dijkstra.

- Flykontrol og robotik kontrol.

- Matematiske optimeringsproblemer.

- Timeshare: planlægge jobbet for at maksimere CPU-brugen.

Fibonacci-nummerserie

Fibonacci-numre er de tal, der findes i følgende rækkefølge: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 osv.

I matematisk terminologi er sekvensen Fn for Fibonacci-numre defineret af gentagelsesformlen: F (n) = F (n -1) + F (n -2), hvor F (0) = 0 og F (1) = 1.

Top-down tilgang

I dette eksempel initialiseres et søgearray med alle startværdier med -1. Hver gang der er behov for løsningen på et underproblem, søges først denne søgematrix.

Hvis den beregnede værdi er der, returneres den værdi. Ellers beregnes resultatet til at blive gemt i søgearrayet, så det kan genbruges senere.

Bund-up tilgang

I dette tilfælde beregnes f (0) for den samme Fibonacci-serie først, derefter f (1), f (2), f (3) og så videre. Således konstrueres delproblemernes løsninger nedenfra og op.

Referencer

1. Vineet Choudhary (2020). Introduktion til dynamisk programmering. Udvikler Insider taget fra: Developerinsider.co.
2. Alex Allain (2020). Dynamisk programmering i C ++. C-programmering. Taget fra: cprogramming.com.
3. Efter akademiet (2020). Idé om dynamisk programmering. Taget fra: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dynamisk programmering og rekursion - forskel, fordele med eksempel. CSE-stak. Taget fra: csestack.org.
5. Code Chef (2020). Tutorial til dynamisk programmering. Taget fra: codechef.com.
6. Programiz (2020). Dynamisk programmering. Taget fra: programiz.com.