Programació dinàmica

En informàtica, la programació dinàmica és un método per a reduir el temps d'eixecució d'un algoritme per mig de l'utilisació de subproblemas superposts i subestructura òptimes.

El matemàtic Richard Bellman va inventar la programació dinàmica en 1953 que s'utilisa per a optimisar problemes complexos que poden ser discretizados i secuencializados.

Introducció

Una «subestructura òptima» implica que la solució òptima d'un problema pot obtindre's a partir de les solucions òptimes de les seues subproblemas. Per eixemple, el camí més curt entre dos vèrtiços d'un grafo es pot trobar calculant primer el camí més curt a l'objectiu des de tots els vèrtiços adjacents al de partida, i despuix usant estes solucions per a elegir el millor camí de tots ells. En general, es poden resoldre problemes en subestructura òptimes seguint estos tres passos:

1. Dividir el problema en subproblemas més menuts.
2. Resoldre estos problemes de manera òptima usant este procés de tres passos recursivament.
3. Usar estes solucions òptimes per a construir una solució òptima al problema original.

Els subproblemas es resolen a la seua volta dividint-los en subproblemas més menuts fins que s'alcance el cas fàcil, a on la solució al problema és trivial.

Dir que un problema té subproblemas superposts és dir que s'usa un mateix subproblema per a resoldre diferents problemes majors. Per eixemple, en la successió de Fibonacci (F₃ = F₁ + F₂ i F₄ = F₂ + F₃) calcular cada terme supon calcular F₂. Com per a calcular F₅ fan falta tant F₃ com a F₄, una mala implementació per a calcular F₅ acabarà calculant F₂ dos o més voltes. Açò succeïx sempre que hi haja subproblemas superposts: una mala implementació pot acabar desperdiciant temps recalculando les solucions òptimes a problemes que ya han segut resolts anteriorment.

Açò es pot evitar guardant les solucions que ya hem calculat. Llavors, si necessitem resoldre el mateix problema més vesprada, podem obtindre la solució de la llista de solucions calculades i reutilisar-la. Este acostament al problema es diu memoización (no confondre en memorisació; en anglés és cridat memoization, vore en). Si estem segurs de que no tornarem a necessitar una solució en concret, la podem descartar per a aforrar espai. En alguns casos, podem calcular les solucions a problemes que de bestreta sabem que anem a necessitar.

En resum, la programació fa us de:

• Subproblemas superposts
• Subestructura òptimes
• Memoización

La programació pren normalment un dels dos següents enfocaments:

• Top-down: El problema es dividix en subproblemas, i estos es resolen recordant les solucions per si anaren necessàries novament. És una combinació de memoización i recursión.
• Bottom-up: Tots els problemes que puguen ser necessaris es resolen de bestreta i despuix s'usen per a resoldre les solucions a problemes majors. Este enfocament és llaugerament millor en consum d'espai i cridades a funcions, pero a voltes resulta poc intuïtiu trobar tots els subproblemas necessaris per a resoldre un problema donat.

Originalment, el terme de programació dinàmica es referia a la resolució de certs problemes i operacions fòra de l'àmbit de l'Ingenieria Informàtica, de la mateixa manera que feya la programació llineal. Aquell context no té relació en la programació en absolut; el nom és una coincidència. El terme també ho va usar en els anys 40 Richard Bellman, un matemàtic nortamericà, per a descriure el procés de resolució de problemes a on fa falta calcular la millor solució consecutivament.

Alguns llenguages de programació funcionals, sobretot Haskell, poden usar la memoización automàticament sobre funcions en un conjunt concret d'arguments, per a accelerar el seu procés d'evaluació. Açò només és possible en funcions que no tinguen efectes secundaris, alguna cosa que ocorre en Haskell, pero no tant en atres llenguages.

Orige i definició

La programació dinàmica és un método quantitatiu desenrollat per Richard Bellman al voltant de la década dels anys 50, en la finalitat d'optimisar processos, ya que en eixe moment eixa era la seua funció com a treballador de RAND Corporation. Bellman va decidir amprar la paraula dinàmica a esta tècnica, ya que desijava analisar les variables dels problemes sobre el temps. Sent aixina Dasgupta, Papadimitriou i Vazirani (2006), varen entendre a la programació dinàmica com a “optimisació de processos en etapa múltiples”. L'idea de Bellman sobre la teoria de programació dinàmica es basa en una estructura d'optimisació, la qual consistix en descompondre el problema en subproblemas (més manejables). Els càlculs es realisen llavors recursivamente a on la solució òptima d'un subproblema s'utilisa com a senya d'entrada al següent problema. Per la qual cosa, s'entén que el problema és solucionat en la seua totalitat, una volta s'haja solucionat l'últim subproblema. Dins d'esta teoria, Bellman desenrolla el Principi de Optimalidad, el qual és fonamental per a la resolució adequada dels càlculs recursivos. La qual cosa vol dir que les etapes futures desenrollen una política òptima independent de les decisions de les etapes predecessores. És per això, que es definix a la programació dinàmica com una tècnica matemàtica que ajuda a resoldre decisions seqüencials interrelacionadas, combinant-les per a obtindre de la solució òptima.

Referències

• G. Vásquez, S. Fiorella L. Moreno, M. A. M. Casallo, J. Carlos. (2016). “Aplicació de model de programació dinàmica per a l'assignació de recursos de l'àrea de força de vendes de l'empresa” [Online]. Available: http://hdl.handle.net/10757/621494
• R. Bellman, «On the Theory of Dynamic Programming», Proceedings of the National Academy of Sciences 38(8):716-719, 1952
• L.L. Cooper, M.W. Cooper, Introduction to dynamic programming, Pergamon Press, Elmsford NY, 1981
• C. Cotta, Programació dinàmica. Introducció i eixercicis resolts, UMA Editorial, Màlaga, 2018

• G.L. Nemhauser, Introduction to dynamic programming, Wiley & Sons, New York NY, 1967.