Fibonacci y programación dinámica
Pide a un ordenador el número de Fibonacci 40 de la forma más obvia y hará más de 331 millones de llamadas. Pídeselo con una tabla y le bastarán 39 sumas. La diferencia es la programación dinámica, y casi todo el mundo la conoce por primera vez con los números de Fibonacci.
El problema
Los números de Fibonacci empiezan por 0, 1, y cada número siguiente es la suma de los dos anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21, etc. Escrito como regla: F(0) = 0, F(1) = 1 y F(n) = F(n − 1) + F(n − 2). La regla es recursiva, y convertirla directamente en un programa recursivo es fácil, pero ese programa resulta ser muy lento.
Por qué la recursión se repite
Para hallar F(5), el programa pide F(4) y F(3). F(4) pide F(3) y F(2), así que F(3) se calcula dos veces, F(2) tres veces y F(1) cinco veces. Dibujadas como un árbol, las llamadas casi se duplican en cada nivel, y el total para F(n) es de 2·F(n + 1) − 1 llamadas. Los problemas más pequeños se superponen: los mismos vuelven una y otra vez. Esa es la señal de que la programación dinámica ayudará.
Dos formas de recordar
La memoización mantiene la recursión pero escribe cada respuesta en una tabla, y cada llamada mira en la tabla antes de hacer ningún cálculo. La tabulación llena la tabla de abajo arriba: primero F(0) y F(1), luego F(2) a partir de ellos, F(3) a partir de F(2) y F(1), y así hasta F(n). En ambos casos cada término se calcula una vez, así que F(n) cuesta n − 1 sumas en lugar de un número exponencial de llamadas.
Un ejemplo
Con el método ascendente para F(7): se empieza con 0 y 1. Luego 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 y 5 + 8 = 13, así que F(7) = 13 tras seis sumas. La recursión simple haría 2·F(8) − 1 = 41 llamadas para obtener la misma respuesta. Con el método descendente, las primeras llamadas bajan hasta F(1) por el borde izquierdo del árbol; a la vuelta, casi una de cada dos llamadas encuentra su respuesta ya en la tabla.
De dónde viene el nombre
Richard Bellman dio nombre a la programación dinámica a principios de los años cincuenta, mientras trabajaba en la RAND Corporation. Más tarde escribió que eligió «programación» en el antiguo sentido de planificación, y «dinámica» porque sonaba impresionante y era difícil ponerle objeciones. El método en sí, resolver un problema mediante las respuestas a versiones más pequeñas de él, funciona hoy en correctores ortográficos, planificadores de rutas y comparación de ADN.
Explóralo
Abre la aplicación y pulsa Paso. Con Ascendente, la celda naranja es la que se está llenando y las dos celdas azules son los términos que suma. Cambia a Descendente y observa cómo la pila de llamadas bajo la tabla crece hasta n y luego se reduce a medida que vuelven las respuestas; la nota bajo Sumas cuenta cuántas llamadas se respondieron directamente desde la tabla.
Preguntas frecuentes
¿Qué son los subproblemas superpuestos?
Problemas más pequeños que una solución necesita más de una vez. F(n) y F(n − 1) necesitan ambos F(n − 2), así que la recursión simple lo calcula dos veces, y el desperdicio se multiplica más abajo. La programación dinámica resuelve cada uno una sola vez y recuerda la respuesta.
¿Es la memoización más rápida que la tabulación?
Hacen las mismas sumas. La tabulación suele ser un poco más rápida porque no hace llamadas, y no puede quedarse sin espacio en la pila; la memoización es práctica cuando solo se necesitan algunas de las respuestas más pequeñas, porque solo calcula esas.
¿Se pueden calcular los números de Fibonacci aún más rápido?
Sí. Con F(2k) = F(k)·(2·F(k + 1) − F(k)) y F(2k + 1) = F(k)² + F(k + 1)², el método de duplicación rápida solo necesita unos log₂ n pasos. La fórmula de Binet con el número áureo da los mismos números, pero los errores de redondeo la hacen poco fiable para n grandes.
¿Cuánta memoria necesita la tabla?
Una tabla completa guarda n + 1 números, pero cada término nuevo solo necesita los dos anteriores, así que un bucle que guarde dos números hace el mismo trabajo con memoria constante. Guardar toda la tabla es útil cuando quieres todos los términos, o para ver cómo funciona el método.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba Fibonacci con programación dinámica