Introducción
Dentro de los temas dedicados a los esquemas algorítmicos, la metodología Programación Dinámica tiene un papel esencial, sobre todo por las posibilidades que ofrece a la hora de mejorar el orden de complejidad de los algoritmos resultantes.
A veces ocurre que a lo largo del proceso recursivo un mismo subproblema es resuelto varias veces, reduciendo la eficiencia. En ocasiones, hasta hacer inviable el algoritmo resultante.
En cambio, la Programación Dinámica nos permite evitar esa posibilidad.
Ejemplo 1: RAYUELA
Dados unos cuadros alineados y numerados desde el 0, el juego consiste en ir saltando hasta el cuadro que ocupa la posición n, siendo n>0, permitiéndose para ello dos posibles movimientos:
Solución recursiva
Esta solución se mostró en el tema II “Diseño de Algoritmos Recursivos”.-
{ n > 0 }
Funcion Rayuela( n : entero ) retorna ( f : entero )
si n=1 ó n=2 entonces retorna n
si no retorna Rayuela(n-1) + Rayuela(n-2)
fsi
ffuncion
Árbol de llamadas ( n = 8 )
Técnica descendente
Programación dinámica
Para la construcción del algoritmo final se precisa:
Elegir una estructura de almacenamiento adecuada
Rellenar dicha estructura en sentido creciente
Elección de la Estructura de almacenamiento
Estructura de Almacenamiento: un vector V de dimensión n
RAYUELA(1) → V[1]
…
RAYUELA(n) → V[n]
Rellenado de la estructura
1ª parte: Problemas triviales
V[1]=1
V[2]=2
2ª parte: Resto de los Problemas (los no triviales) en orden creciente
V[3]=V[2]+V[1]
V[4]=V[3]+V[2]
…
V[i]=V[i-1]+V[i-2]
…
3ª parte: Mostrar Solución
retorna V[n]
{ n > 0 }
Función RAYUELA_Programacion_Dinamica ( n : entero ) retorna ( f : entero )
var V[1..n] : vector de enteros, i : entero fvar
V[1]=1 # 1ª parte: Problemas triviales
V[2]=2
para i=3 hasta n hacer # 2ª parte: Resto de los Problemas (los no triviales) en orden creciente
V[i]=V[i-1]+V[i-2]
fpara
retorna V[n] # 3ª parte: Mostrar Solución
ffuncion
Mejora del algoritmo
{ n > 0 }
Función RAYUELA_Programacion_Dinamica_mejorado ( n : entero ) retorna ( f : entero )
var a, b : entero fvar
a=1 # 1ª parte: Problemas triviales
b=2
para i = 3 hasta n hacer # 2ª parte: Resto de los Problemas (no triviales) en orden creciente
b = a + b
a = b - a
fpara
si n = 1 entonces retorna a
sino retorna b fsi # 3ª parte: Mostrar Solución
ffuncion
Ejemplo 2: COMPETICIÓN INTERNACIONAL
Dos equipos A y B juegan partidas sucesivas entre sí, en las que no cabe el empate y en las que el resultado de cada una es independiente de los resultados ocurridos en las demás.
La competición continúa hasta que uno de los equipos consigue n victorias. Esto implica que el número máximo de partidas que pueden llegar a disputarse es 2n-1.
Partimos del supuesto de que las probabilidades de que A y B ganen una partida son conocidas y suman 1, al no existir la posibilidad de empate. Sea p la probabilidad de A gane una partida y por tanto, 1-p, la probabilidad de que gane B.
Nuestro objetivo es:
diseñar un algoritmo que nos permita calcular la probabilidad de que A gane la competición.
Inicialmente, razonaremos de forma recursiva. Para ello planteamos una situación intermedia.
Llamaremos Competicion(i, j) a la probabilidad de que el equipo A gane la competición cuando nos encontramos en un momento en el que:
al equipo A le faltan i victorias para ganar la competición y al equipo B le faltan j
Por tanto, 0 <= i, j <= n y el problema inicial es: Competición(n, n)
Supongamos que se juega una nueva partida. El problema Competición( i, j ) se transformará en uno de los subproblemas siguientes:
Competición( i - 1, j ) si esa partida la gana A (lo que sucede con probabilidad p) ó
Competición( i, j - 1 ) si la gana B (que sucede con probabilidad 1-p)
En resumen,
Competicion(i, j) = p * Competicion(i -1, j) + (1-p) * Competicion(i, j -1)
De acuerdo con el preorden establecido entre los subproblemas, los casos triviales corresponden a los problemas de la forma:
Competicion(0, j) y Competicion(i,0), cuyas soluciones respectivas son 1.00 y 0.00
{ 0 <= i, j <= n }
Función Competicion ( i, j : entero; p : real ) retorna ( s : real )
si i = 0 entonces retorna 1.00
sino si j = 0 entonces retorna 0.00
sino retorna p * Competicion( i-1, j, p ) + (1-p) * Competicion( i, j-1, p)
fsi
fsi
ffuncionLa llamada inicial a la función sería: Competicion(n, n, p)
Árbol de llamadas ( n = 4 )
Estructura de Almacenamiento: una matriz M de dimensión (n+1) filas x (n+1) columnas
de tal modo que Competicion (i, j, p) → M[ i ][ j ]
Datos del problema: n = 4 y p = 0.45
Problemas triviales: i = 0 ó j = 0
Resto de los problemas en orden creciente -> rellenado por filas o por columnas o por diagonales
Por filas:
M[3][2] = 0.45 * M[2][2] + ( 1-0.45 ) * M[3][1] = 0.24
Solución: M[4][4]
Función Competición_Programacion_Dinamica ( n : entero; p : real ) retorna ( s : real )
var M[0..n][0..n]: matriz de reales; i, j : entero fvar
para i = 1 hasta n hacer # 1ª parte: Problemas triviales
M[ i ][ 0 ] = 0.00
M[ 0 ][ i ] = 1.00
fpara
para i = 1 hasta n hacer # 2ª parte: Resto de los Problemas (los no triviales) en orden creciente
para j = 1 hasta n hacer
M[ i ][ j ] = p * M[ i - 1 ][ j ] + ( 1-p ) * M[ i ][ j - 1 ]
fpara
fpara
retorna M[n][n] # 3ª parte: Mostrar Solución
ffuncion
Mejora del algoritmo
Observemos que al rellenar la fila i-ésima sólo se precisa de la información almacenada en la misma fila i y en la fila i-1 de la matriz.
Por lo que podremos hacer uso únicamente de un vector de (n+1) elemento. ¿Cómo?
V[1]=0.45*V[1]+0.55*V[0]=0.45*1.00+0.55*0.00=0.45
V[2]= 0.45*V[2]+0.55*V[1]=0.45*1.00+0.55*0.45=0.70
En este punto, el contenido del vector V es equivalente a la fila 1 de la matriz
Función Competición_Programacion_Dinamica ( n : entero; p : real ) retorna ( s : real )
var V[0..n]: vector de reales; i, j : entero fvar
para i = 1 hasta n hacer # 1ª parte: Problemas triviales
V[ i ] = 1.00
fpara
V[ 0 ] = 0.00
para i = 1 hasta n hacer # 2ª parte: Resto de los Problemas (los no triviales) en orden creciente
para j = 1 hasta n hacer
V[ j ] = p * V[ j ] + ( 1-p ) * V[ j - 1 ]
fpara
fpara
retorna V[n] # 3ª parte: Mostrar Solución
ffuncion
Last updated