PROGRAMACIÓ DINÀMICA: CARACTERÍSTIQUES, EXEMPLE, AVANTATGES, DESAVANTATGES - TECNOLOGIA - 2026

La programació dinàmica és un model d'algorisme que resol un problema complex dividint-lo en subproblemes, emmagatzemant els resultats dels mateixos per així evitar haver de tornar a calcular aquests resultats.

Aquesta programació s'utilitza quan es tenen problemes que es poden dividir en subproblemes similars, de manera que els seus resultats puguin ser reutilitzats. En la seva gran majoria, aquesta programació s'utilitza per a l'optimització.

Programació dinàmica. Subproblemes sobreposats en la successió de Fibonacci. Font: Wikimedia commons, en: User: Dcoatzee, Traced by User: Stannered / Public domain

Abans de resoldre el subproblema disponible, l'algoritme dinàmic intentarà examinar els resultats dels subproblemes prèviament resolts. Les solucions dels subproblemes es combinen per així aconseguir la millor solució.

En lloc de calcular el mateix subproblema una i altra vegada, es podrà emmagatzemar la seva solució en alguna memòria, a l'trobar-se per primera vegada amb aquest subproblema. Quan el mateix aparegui novament durant la solució d'un altre subproblema, s'ha de prendre la solució ja emmagatzemada a la memòria.

Aquesta és una idea meravellosa per a esmenar el temps amb memòria, on a l'utilitzar espai addicional es pot millorar el temps requerit per trobar una solució.

Característiques de la programació dinàmica

Les següents característiques essencials són les que ha de tenir un problema perquè es pugui aplicar la programació dinàmica:

subestructura òptima

Aquesta característica expressa que un problema d'optimització es pot resoldre a l'combinar les solucions òptimes dels problemes secundaris que el conformen. Aquestes subestructures òptimes es descriuen mitjançant la recursivitat.

Per exemple, en un graf es presentarà una subestructura òptima en la ruta més curta r que va des d'un vèrtex s fins a un vèrtex t:

És a dir, en aquesta ruta més curta r es pot prendre qualsevol vèrtex intermedi i. Si r és realment la ruta més curta, llavors es podrà dividir en les subrutes r1 (des de s fins i) i r2 (des i fins t), de tal manera que aquestes siguin al seu torn les rutes més curtes entre els vèrtexs corresponents.

Per tant, per trobar les rutes més curtes es podrà formular fàcilment la solució de manera recursiva, que és el que fa l'algoritme Floyd-Warshall.

subproblemes sobreposats

L'espai dels subproblemes ha de ser petit. És a dir, qualsevol algoritme recursiu que resolgui un problema haurà de resoldre els mateixos subproblemes una i altra vegada, en lloc de generar nous subproblemes.

Per exemple, per generar la sèrie de Fibonacci es pot considerar aquesta formulació recursiva: Fn = F (n-1) + F (n-2), prenent com a cas base que F1 = F2 = 1. Llavors s'haurà de: F33 = F32 + F31, i F32 = F31 + F30.

Com es pot observar, F31 s'està resolent en els subarbres recursius tant de F33 com de F32. Tot i que el nombre total de subproblemes és realment petit, si s'adopta una solució recursiva com aquesta s'acabaran resolent els mateixos problemes una i altra vegada.

Això ho té en compte la programació dinàmica, de manera que resol cada subproblema només una vegada. Això es pot aconseguir de dues maneres:

Enfocament de dalt a baix

Si la solució a qualsevol problema es pot formular recursivament usant per a això la solució dels seus subproblemes, i si aquests subproblemes es superposen, llavors les solucions als subproblemes es podran memoritzar o emmagatzemar fàcilment en una taula.

Cada vegada que es busqui la solució d'un subproblema nou, es revisarà a la taula si va ser resolt prèviament. En cas que es tingui emmagatzemada una solució, s'utilitzarà la mateixa en lloc de calcular-la de nou. En cas contrari, es resoldrà el subproblema, emmagatzemant la solució a la taula.

enfocament ascendent

Després que es formula de forma recursiva la solució d'un problema en termes de les seves subproblemes, es podrà intentar reformular el problema de manera ascendent: primer s'intentaran resoldre els subproblemes i usar les seves solucions per arribar a solucions als subproblemes més grans.

Això també es fa generalment en forma de taula, generant iterativament solucions a subproblemes cada vegada més grans mitjançant l'ús de solucions als subproblemes petits. Per exemple, si ja es coneixen els valors de F31 i F30, es podrà calcular directament el valor de F32.

Comparació amb altres tècniques

Una pertinença significativa d'un problema que es pugui resoldre mitjançant programació dinàmica és que hauria de tenir subproblemes sobreposats. Això és el que distingeix la programació dinàmica de la tècnica de dividir i conquerir, on no cal emmagatzemar els valors més simples.

És similar a la recursivitat, ja que a l'calcular els casos base es pot determinar inductivament el valor final. Aquest enfocament ascendent funciona bé quan un nou valor depengui només de valors calculats prèviament.

exemple

Passos mínims per arribar a 1

Per a qualsevol enter positiu "i" es pot realitzar qualsevol dels tres passos següents.

- Restar 1 de l'nombre. (I = e-1).

- Si és divisible per 2, es divideix entre 2 (si e% 2 == 0, llavors i = i / 2).

- Si és divisible per 3, es divideix entre 3 (si i% 3 == 0, llavors i = i / 3).

Basat en els passos anteriors, s'ha de trobar la quantitat mínima d'aquests passos per dur ea 1. Per exemple:

- Si i = 1, resultat: 0.

- Si i = 4, resultat: 2 (4/2 = 2/2 = 1).

- Quan i = 7, resultat: 3 (7-1 = 6/3 = 2/2 = 1).

enfocament

Es podria pensar en triar sempre el pas que faci que n sigui el més baix possible i continuar així, fins que arribi a 1. No obstant això, es pot observar que aquesta estratègia no funciona aquí.

Per exemple, si i = 10, els passos serien: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 passos). No obstant això, la forma òptima és: 10-1 = 9/3 = 3/3 = 1 (3 passos). Per tant, s'han de provar tots els passos possibles que es puguin fer per a cada valor que es trobi de n, triant la quantitat mínima d'aquestes possibilitats.

Tot comença amb la recursivitat: F (i) = 1 + min {F (e-1), F (i / 2), F (i / 3)} si i> 1, prenent com a cas base: F (1) = 0. Tenint l'equació de recurrència, es pot començar a codificar la recursió.

No obstant això, es pot observar que té subproblemes sobreposats. A més, la solució òptima per a una entrada donada depèn de la solució òptima dels seus subproblemes.

Com en la memorització, on les solucions dels subproblemes que es resolen es van emmagatzemant per usar-los posteriorment. O com en la programació dinàmica, es comença des de baix, avançant fins l'e donat. A continuació, els dos codis:

memorització

Programació dinàmica de baix a dalt

avantatges

Una de les principals avantatges d'utilitzar programació dinàmica és que accelera el processament, ja que s'usen referències que van ser prèviament calculades. Com és una tècnica de programació recursiva, redueix les línies de codi de el programa.

Algorismes voraços vs programació dinàmica

Els algoritmes voraços són similars a la programació dinàmica en el sentit que tots dos són eines per a l'optimització. No obstant això, l'algorisme voraç busca una solució òptima en cada pas local. És a dir, busca una elecció cobdiciosa amb l'esperança de trobar un òptim global.

Per tant, els algoritmes voraços poden fer una suposició que es vegi òptima en aquest moment, però que es torna costosa en el futur i no garanteix un òptim global.

D'altra banda, la programació dinàmica troba la solució òptima per als subproblemes i després fa una elecció informada combinant els resultats d'aquests subproblemes per trobar realment la solució més òptima.

desavantatges

- Es necessita molta memòria per emmagatzemar el resultat calculat de cada subproblema, sense poder garantir que el valor emmagatzemat s'utilitzarà o no.

- Moltes vegades, el valor de sortida es queda emmagatzemat sense mai ser utilitzat en els següents subproblemes durant l'execució. Això comporta a una utilització innecessària de la memòria.

- En la programació dinàmica les funcions es diuen recursivament. Això fa que la memòria de pila es mantingui en constant augment.

Recursivitat vs programació dinàmica

Si es té memòria limitada per executar el codi i no és preocupant la velocitat de processament, es pot usar la recursivitat. Per exemple, si s'està desenvolupant una aplicació mòbil, la memòria és molt limitada per executar l'aplicació.

Si es desitja que el programa s'executi més ràpid i no es tenen restriccions de memòria, és preferible utilitzar la programació dinàmica.

aplicacions

La programació dinàmica és un mètode eficaç per resoldre problemes que d'altra manera podrien semblar extremadament difícils de resoldre en un temps raonable.

Els algoritmes basats en el paradigma de programació dinàmica s'utilitzen en moltes àrees de les ciències, incloent molts exemples en intel·ligència artificial, des de la resolució de problemes de planificació fins al reconeixement de veu.

Algorismes basats en programació dinàmica

La programació dinàmica és bastant efectiva i serveix molt bé per a una àmplia gamma de problemes. Molts algoritmes es poden veure com a aplicacions d'algoritmes voraços, com:

- Sèrie de nombres de Fibonacci.

- Torres de Hanoi.

- Tots els parells de rutes més curtes per Floyd-Warshall.

- Problema de la motxilla.

- Programació de projectes.

- El camí més curt per Dijkstra.

- Control de vol i control de robòtica.

- Problemes d'optimització matemàtica.

- Temps compartit: programar el treball per maximitzar l'ús de la CPU.

Sèrie de nombres de Fibonacci

Els nombres de Fibonacci són els números que es troben en la seqüència següent: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, etc.

En la terminologia matemàtica, la successió Fn dels nombres de Fibonacci està definida per la fórmula de recurrència: F (n) = F (n -1) + F (n -2), on F (0) = 0 i F (1) = 1.

Enfocament de dalt a baix

En aquest exemple, s'inicialitza amb -1 una matriu de recerca amb tots els valors inicials. Sempre que es necessiti la solució a un subproblema, primer es buscarà en aquesta matriu de cerca.

Si allà hi ha el valor calculat, llavors es retornarà aquest valor. En cas contrari, s'ha de calcular el resultat per emmagatzemar-lo en la matriu de recerca i així poder-lo reutilitzar més endavant.

enfocament ascendent

En aquest cas, per a la mateixa sèrie de Fibonacci, es calcula primer f (0), després f (1), f (2), f (3), i així successivament. Així, s'estaran construint les solucions dels subproblemes de baix a dalt.

referències

1. Vineet Choudhary (2020). Introduction to Dynamic Programming. Developer Insider.Tomado de: developerinsider.co.
2. Alex Allain (2020). Dynamic Programming in C ++. C Programming. Pres de: cprogramming.com.
3. After Academy (2020). Idea of ​​Dynamic Programming. Pres de: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dynamic Programming and Recursion - Difference, Advantages with Example. CSE Stack. Pres de: csestack.org.
5. Code Xef (2020). Tutorial For Dynamic Programming. Pres de: codechef.com.
6. Programiz (2020). Dynamic Programming. Pres de: programiz.com.