Subproblemas superpuestos

En informática , se dice que un problema tiene subproblemas superpuestos si se puede dividir en subproblemas que se reutilizan varias veces o si un algoritmo recursivo para el problema resuelve el mismo subproblema repetidamente en lugar de generar siempre nuevos subproblemas. ^{[ 1 ] [ 2 ] [ 3 ]}

Por ejemplo, el problema de calcular la sucesión de Fibonacci presenta subproblemas superpuestos. El problema de calcular el n -ésimo número de Fibonacci, F ( n ), se puede descomponer en los subproblemas de calcular F ( n - 1) y F ( n - 2), y luego sumar ambos. El subproblema de calcular F ( n - 1) se puede descomponer a su vez en un subproblema que implica calcular F ( n - 2). Por lo tanto, el cálculo de F ( n - 2) se reutiliza, y la sucesión de Fibonacci presenta así subproblemas superpuestos.           

Un enfoque recursivo ingenuo para este tipo de problema generalmente falla debido a su complejidad exponencial . Si el problema también comparte una propiedad de subestructura óptima , la programación dinámica es una buena manera de resolverlo.

En las siguientes dos implementaciones para calcular la secuencia de Fibonacci , fibonaccise utiliza recursión regular y fibonacci_memse utiliza memorización . fibonacci_memes mucho más eficiente ya que el valor para cada particular nse calcula solo una vez.

Cuando se ejecuta, la fibonaccifunción calcula el valor de algunos de los números de la secuencia muchas veces, mientras que fibonacci_memreutiliza el valor nque se calculó previamente:

La diferencia de rendimiento puede parecer mínima con un nvalor de 5; sin embargo, a medida que naumenta, la complejidad computacional de la función original fibonaccicrece exponencialmente. En cambio, la fibonacci_memversión muestra un incremento de complejidad más lineal.

• Programación dinámica