Programació dinàmica
Dins de l'entorn de la informàtica, la programació dinàmica és un mètode per a reduir el temps d'execució d'un algorisme mitjançant la utilització de subproblemes superposats i subestructures òptimes, com es descriu a continuació. El matemàtic Richard Bellman va inventar la programació dinàmica el 1953.
El concepte de Subestructura òptima vol dir que es poden fer servir solucions òptimes de subproblemes per a trobar la solució òptima del problema en el seu conjunt. Per exemple, el camí més curt entre dos vèrtexs d'un graf es pot trobar calculant primer el camí més curt a l'objectiu des de tots els vèrtexs adjacents al de partida, i després fent servir aquestes solucions per a triar el millor camí de tots ells. En general, es poden resoldre problemes amb subestructures òptimes seguint aquests tres passos:
- Dividir el problema en subproblemes més petits.
- Resoldre aquests problemes de manera òptima fent servir aquest procés de tres passos recursivament.
- Emprar aquestes solucions òptimes per a construir una solució òptima al problema original.
Els subproblemes es resolen al seu torn dividint-los en subproblemes més petits fins que s'assoleixi el cas fàcil, on la solució al problema és trivial.
Direm que un problema té subproblemes superposats quan fem servir un mateix subproblema per a resoldre diferents problemes majors. Per exemple, en la successió de Fibonacci (F 3 = F 1 +F 2 i F 4 = F 2 +F 3 ) calcular cada terme suposa calcular F 2 . Com que per a calcular F 5 calen tant F 3 com F 4 , aleshores una mala implementació per a calcular F 5 acabarà calculant F 2 dues o més vegades. Això passa sempre que hi hagi subproblemes superposats: una mala implementació pot acabar desaprofitant temps recalculant les solucions òptimes a subproblemes que ja han estat resolts anteriorment.
Això es pot evitar guardant les solucions que ja hem calculat. Llavors, si necessitem resoldre el mateix problema més tard, podem obtenir la solució de la llista de solucions calculades i reutilitzar-la. Aquest acostament al problema es diu memoització (en anglès "memoization"). Si estem segurs que no tornarem a necessitar una solució en concret, la podem descartar per estalviar espai. En alguns casos, podem calcular les solucions d'aquells problemes que sabem que més endavant necessitarem.
En resum, la programació dinàmica fa ús de:
La programació dinàmica pren base normalment d'un dels dos següents enfocaments:
- Top-down : El problema es divideix en subproblemes, els quals es resolen emmagatzemant les solucions per si més endavant fessin falta. És una combinació de memoització i recursió.
- Bottom-up : Tots els subproblemes que prèviament ens calgui resoldre, es resolen per endavant i després es fan servir per resoldre les solucions a problemes majors. Aquest enfocament és lleugerament millor en consum d'espai i trucades (crides) a funcions, però de vegades resulta poc intuïtiu trobar tots els subproblemes que ens calen per a resoldre un problema donat.
Originalment, el terme de programació dinàmica es referia a la resolució de certs problemes i operacions fora de l'àmbit de l'Enginyeria Informàtica, de la mateixa manera que feia la programació lineal. Aquell context no té relació amb la programació d'ordinadors en absolut, el nom és una coincidència. El terme també el va fer servir en els anys 40 Richard Bellman, un matemàtic nord-americà, per descriure el procés de resolució de problemes on cal calcular la millor solució consecutivament.
Alguns llenguatges de programació funcionals, sobretot Haskell, poden fer servir la memoització automàticament sobre funcions amb un conjunt concret d'arguments, per accelerar-ne el procés d'avaluació. Això només és possible en funcions que no tinguin efectes secundaris, una cosa que passa a Haskell però no tant en altres llenguatges.
Principi d'optimalitat
[modifica]Quan parlem d'optimitzar ens referim a buscar alguna de les millors solucions d'entre moltes alternatives possibles. Aquest procés d'optimització pot ser vist com una seqüència de decisions que ens proporcionen la solució correcta. Si, donada una subseqüència de decisions, sempre es coneix quina és la decisió que s'ha de prendre a continuació per a obtenir la seqüència òptima, el problema és elemental i es resol trivialment prenent una decisió darrere l'altra; és el que es coneix com a estratègia voraç.
Sovint, encara que no sigui possible aplicar l'estratègia voraç, es compleix el principi d'optimalitat de Bellman que dicta que «donada una seqüència òptima de decisions, tota subseqüència d'ella mateixa és, al seu torn, òptima». En aquest cas segueix essent possible anar prenent decisions elementals, tenint la confiança que la combinació de totes elles seguirà sent òptima, però que llavors caldrà explorar moltes seqüències de decisions per a trobar la correcta, i és aquí que intervé la programació dinàmica.
Plantejar un problema com una seqüència de decisions equival a dividir-lo en subproblemes més petits i per tant més fàcils de resoldre com fem a Divideix i venceràs, tècnica similar a la de la programació dinàmica. La programació dinàmica s'aplica quan la subdivisió d'un problema condueix a:
- Una enorme quantitat de subproblemes.
- Subproblemes amb solucions parcials que es solapen.
- Grups de subproblemes de complexitat molt variada.
Exemples
[modifica]Successió de Fibonacci
[modifica]Aquesta successió pot expressar mitjançant la següent recurrència:
Una implementació d'una funció que trobi el n -èsim terme de la successió de Fibonacci basada directament en la definició matemàtica de la successió tot realitzant crides recursives fa que es generi molta feina redundant, d'una complexitat que creix exponencialment:
FUNC fib (↓ n: NATURAL ): NATURAL INICI SI n = 0 LLAVORS RETORNAR 0 SINOSI n = 1 LLAVORS RETORNAR 1 SINO Retornar fib (n-1)+fib (n-2) FINSI FI
Si anomenem, per exemple, a FIB (5) , produirem un arbre de crides que contindrà funcions amb els mateixos paràmetres diverses vegades:
FIB (5)FIB (4)+fib (3)(FIB (3)+fib (2))+(fib (2)+fib (1))((Fib (2)+fib (1))+(fib (1)+fib (0)))+((fib (1)+fib (0))+fib (1))(((Fib (1)+fib (0))+fib (1))+(fib (1)+fib (0)))+((fib (1)+fib (0))+fib (1))
En particular, fib (2) s'ha calculat dues vegades des de zero. En exemples grans, es recalculen molts altres valors de FIB , o subproblemes .
Per evitar aquest inconvenient, podem resoldre el problema mitjançant programació dinàmica, i en particular, emprant l'enfocament de memoització (desar els valors que ja han estat calculats per a fer-los servir posteriorment). Així, ompliríem una taula amb els resultats dels diferents subproblemes, per a reutilitzar-los quan calgués en comptes de tornar-los a calcular. La taula resultant esdevé unidimensional amb els resultats des de 0 fins a n.
Un programa que calculés això, usant Bottom-up, tindria la següent estructura:
FUNC Fibonacci (↓ n: NATURAL ): NATURAL VARIABLES taula: ARRAY [0 .. n] D'NATURAL i: NATURAL INICI SI n ≤ 1 LLAVORS Retornar 1 SINO taula [0] ← 1 taula [1] ← 1 PER i ← 2 FINS n FER taula [i] ← taula [i-1]+taula [i-2] FINPARA Retornar taula [n] FINSI FI
La funció resultant té complexitat O ( n ), en lloc d'exponencial.
Un altre nivell de refinament que optimizaria la solució seria quedar-nos només amb els dos últims valors calculats en lloc de tota la taula, ja que són realment els que ens resulten útils per a calcular la solució als subproblemes.
El mateix problema utilitzant Top-down tindria la següent estructura:
FUNC Fibonacci (↓ n: NATURAL , ↨ taula: ARRAY [0 .. n] D NATURAL ): NATURAL VARIABLES i: NATURAL INICI SI n ≤ 1 LLAVORS Retornar 1 FINSI SI taula [n-1] = -1 LLAVORS taula [n-1] ← Fibonacci (n-1, taula) FINSI SI taula [n-2] = -1 LLAVORS taula [n-2] ← Fibonacci (n-2, taula) FINSI taula [a] ← taula [n-1]+taula [n-2] Retornar taula [n] FI
Suposem que, a la taula, hi introduïm per primera vegada correctament, i prèviament inicialitzada, en totes les posicions, un valor incorrecte, com per exemple -1, que es distingeix per no ser un dels valors que computa la funció.
Coeficients binomials
[modifica]L'algorisme recursiu que calcula els coeficients binomials esdevé de complexitat exponencial per la repetició dels càlculs que realitza. Tanmateix, és possible dissenyar un algorisme amb un temps d'execució d'ordre O (NK) basat en la idea del Triangle de Pascal, idea clarament aplicable mitjançant programació dinàmica. Per això és necessària la creació d'una taula bidimensional en la qual anem emmagatzemant els valors intermedis que s'utilitzen posteriorment.
La idea recursiva dels coeficients binomials és la següent:
= + si 0 < k <n
= = 1
La idea per a construir la taula de manera eficient i sense valors inútils és la següent:
| 0 | 1 | 2 | 3 | ... | K-1 | k | |
| 0 | 1 | ||||||
| 1 | 1 | 1 | |||||
| 2 | 1 | 2 | 1 | ||||
| 3 | 1 | 3 | 3 | 1 | |||
| ... | ... | ... | ... | ... | ... | ||
| ... | ... | ... | ... | ... | ... | ... | |
| N-1 | C (n-1, k-1) | C (n-1, k) | |||||
| N | C (n, k) |
El següent algorisme memoitzat d'estratègia Bottom-up té complexitat polinòmica i va omplint la taula d'esquerra a dreta i de dalt a baix:
FUNC CoeficientesPolinomiales (↓ n, k: NATURAL ): NATURAL Variables taula: TAULA DE NATURAL i, j: NATURAL Inici PER i ← 0 FINS n FER taula [i] [0] ← 1 FINPARA PER i ← 1 FINS n FER taula [i] [1] ← i FINPARA PER i ← 2 FINS k FER taula [i] [i] ← 1 FINPARA PER i ← 3 FINS n FER PER j ← 2 FINS i-1 FER SI j ≤ k LLAVORS taula [i] [j] ← taula [i-1] [j-1]+taula [i-1] [j] FINSI FINPARA FINPARA Retornar taula [n] [k] Fi
Per descomptat, el problema dels Coeficients binomials també es pot resoldre mitjançant un enfocament Top-down.
El viatge més barat pel riu
[modifica]En un riu hi ha n embarcadors, en cada un dels quals es pot llogar un bot per anar a un altre embarcador que estigui riu avall. Suposem que no es pot remuntar el riu. Una taula de tarifes indica els costos de viatjar entre els diferents embarcadors. Se suposa que pot passar que un viatge entre iij surti més barat fent escala a k embarcadors que anant-hi directament.
El problema consistirà a determinar el cost mínim per a un parell d'embarcadors.
Anem a trucar (fer una crida) a la taula de tarifes, T. Així, T [i, j] serà el cost d'anar de l'embarcador i al j. La matriu serà triangular superior d'ordre n, on n és el nombre d'embarcadors.
La idea recursiva és que el cost es calcula de la manera següent:
C (i, j) = T [i, k]+C (k, j)
A partir d'aquesta idea, podem elaborar una expressió recurrent per a la solució:
0 si i = j C (i, j) = Min (T (i, k)+C (k, j), T (i, j)) si i <k ≤ j
Un algorisme que resol aquest problema és el següent, on T és la matriu de tarifes, origen i destinació els embarcadors del qual es parteix i al qual s'arriba respectivament, i C la matriu en la qual emmagatzemarem els resultats dels costos. La funció MenorDeLosCandidatos torna el menor cost entre dos punts, fent servir com a base la recurrència exposada anteriorment.
FUNC Embarcadors (↓ origen, destinació, n: NATURAL , ↓ T: MATRIU DE NATURAL ): NATURAL Variables C: MATRIU DE NATURAL i, j: NATURAL Inici PER i ← 1 FINS n FER C [i] [i] ← 0 FINPARA PER i ← 1 FINS n FER PER j ← 1 FINS n FER C [i] [j] ← menorDeLosCandidatos (i, j, n, T, C) FINPARA FINPARA Retornar C [n] [n] Fi
FUNC menorDeLosCandidatos (↓ origen, destinació, n: NATURAL , ↓ T, C: MATRIU DE NATURAL ): NATURAL Variables temp: NATURAL Inici temp ← MAX_NATURAL PER i ← origen+1 FINS n FER temp ← min (temp, T [origen] [i]+C [i] [destinació] FINPARA Retornar temp Fi
Bibliografia
[modifica]- Xumari, G.L. Introduction to dynamic programming. Wilwy & Sons Inc, New York. 1967.