Vés al contingut

Programació dinàmica

De la Viquipèdia, l'enciclopèdia lliure

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:

  1. Dividir el problema en subproblemes més petits.
  2. Resoldre aquests problemes de manera òptima fent servir aquest procés de tres passos recursivament.
  3. 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:

  1. FIB (5)
  2. FIB (4)+fib (3)
  3. (FIB (3)+fib (2))+(fib (2)+fib (1))
  4. ((Fib (2)+fib (1))+(fib (1)+fib (0)))+((fib (1)+fib (0))+fib (1))
  5. (((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.

Enllaços externs

[modifica]