Diferencia entre revisiones de «Algoritmia/Programación dinámica»
Contenido eliminado Contenido añadido
de en: |
de http://es.wikipedia.org/wiki/Programación_dinámica_(computación) |
||
Línea 2:
El término dinámico proviene de que la tabla auxiliar se rellena en tiempo de ejecución. No debe confundirse la programación dinámica en el ámbito algorítmico con los lenguajes de programación dinámicos, como [[w:Scheme|Scheme]] o [[w:Lisp|Lisp]].
==Ejemplo: la sucesión de Fibonacci==
La primera implementación de una función para encontrar el '''n'''-ésimo término de la [[w:sucesión de Fibonacci|sucesión de Fibonacci]] que surge de forma natural, es la basada en la definición matemática de la misma:
'''fun''' fib(n)
'''si''' n = 0 || n = 1
'''devolver''' n
'''si no'''
'''devolver''' fib(n - 1) + fib(n - 2)
'''fsi'''
'''ffun'''
No es difícil comprobar la cantidad de cálculo redundante a que conduce este primer acercamiento al problema. Si llamamos, por ejemplo, a <code>fib (5)</code>, produciremos un árbol de llamadas que contendrá funciones con los mismos parámetros varias veces:
# <code>fib(5)</code>
# <code>fib(4) + fib(3)</code>
# <code>(fib(3) + fib(2)) + (fib(2) + fib(1))</code>
# <code>((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))</code>
# <code>(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))</code>
En particular, <code>fib(2)</code> ha sido calculado dos veces desde cero. En ejemplos mayores, muchos otros valores de <code>fib</code>, o subproblemas, son recalculados, llevando a un algoritmo de complejidad exponencial.
Si se considera ahora la utilización de un simple array para almacenar la solución a los distintos subproblemas, la función resultante será de complejidad lineal, en lugar de exponencial, pues cada <code>fib(n)</code> se calcula una única vez:
'''var''' tabla : '''array''' [0..n] de '''ent'''
'''fun''' fib(n)
'''si''' tabla[n] = -1 '''entonces''' // El array inicializado a -1
tabla[n] := fib(n - 1) + fib(n - 2)
'''fsi'''
'''devolver''' tabla[n]
'''ffun'''
Esta implementación está hecha desde arriba (''top-down'' en inglés), solicitando primero la solución del problema y calculando recursivamente las soluciones a los subproblemas. Una implementación desde abajo (''bottom-up'' en inglés) consiste en realizar el proceso inverso: calcular primero la solución a los subproblemas y a partir de las mismas, definir la solución al problema.
| |||