Programació dinàmica
From Wikipedia, the free encyclopedia
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:
- subproblemes superposats
- subestructures òptimes
- Memoització
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.