Problemas de optimización
Una aplicación característica de Programación Dinámica es la resolución de problemas de optimización.
Estos problemas pueden tener muchas soluciones factibles (que cumplen unas restricciones), pero se trata de encontrar LA SOLUCIÓN ÓPTIMA.
Cada solución tiene un valor asociado, y lo que se desea encontrar es la solución con el valor óptimo (máximo o mínimo)
Por lo que tendremos:
FUNCIÓN OBJETIVO
RESTRICCIONES
Otra característica de este tipo de problemas es que la solución se puede expresar como una SECUENCIA DE DECISIONES, esto es,
<X1, X2, …, Xn>
Además, para garantizar que la aplicación de Programación Dinámica a un problema de optimización produce una solución óptima, dicho problema debe satisfacer ciertas condiciones que se expresan bajo el denominado “PRINCIPIO DE OPTIMALIDAD DE BELLMAN”:
”En una secuencia óptima de decisiones, toda subsecuencia debe ser también óptima”
Ejemplo.-
Supongamos que el camino más corto entre Gijón y Santander pasa por Llanes, entonces la parte del camino que va desde Gijón a Llanes también debe ser el camino más corto posible, al igual que la parte del camino que va de Llanes a Santander.
Demostración.-
Sea la solución óptima al problema de la ruta más corta entre Gijón y Santander:
Cuya distancia total es X, esto es, X = Y + Z
Supongamos ahora que Y NO es la distancia del camino más corto que va de Gijón a Llanes, sino que hay otro camino de Gijón a Llanes con una distancia menor
En conclusión, Y’ < Y
Lo que implica que X’ = Y’ + Z
Mejoraría X = Y + Z
Ya que X’ = Y’ + Z
es menor que X = Y + Z
lo cual contradice la hipótesis de partida, pues ésta era la solución óptima de dicho problema. Se cumple pues, el principio de optimalidad.
Aún cuando este principio pueda parecer evidente, no es aplicable a todos los problemas.
Resolución a los problemas de optimización
Pasos a seguir.-
Solución como secuencia de decisiones
Función objetivo y restricciones
Demostración principio de optimalidad
Definición recursiva
Árbol de llamadas
Repetición Subproblemas
Orden de los subproblemas
Estructura de Almacenamiento
Proceso de rellenado
Búsqueda de la solución óptima
Algoritmo
Ejemplo 1: El problema de la mochila
Tenemos n objetos, siendo n≥0, y cada objeto i tiene un peso (Pi) y un beneficio (Bi), donde Pi y Bi son mayores 0.
Además, tenemos una mochila con una capacidad C y se cumple que
¿Qué objetos debemos introducir en la mochila de tal forma que maximicemos el beneficio que transporta y no superemos la capacidad C de la mochila?
Solución como secuencia de decisiones
< X1, X2, …, Xn >
donde Xi es la decisión con respecto al objeto i:
Xi = 1 indica que el objeto i se introduce en la mochila
y
Xi = 0 indica que el objeto i no se introduce en la mochila.
Función objetivo y restricciones
Principio de optimalidad
”En una secuencia óptima de decisiones, toda subsecuencia debe ser también óptima”
Demostración.-
Sea < X1, X2, …, Xn > la solución óptima para el problema (1, n, C), esto es, para el problema con n objetos (del 1 al n) y una mochila de capacidad C.
Su valor (beneficio) asociado es
sujeto a
Vamos a prescindir de la última decisión, es decir, Xn
La subsecuencia que queda, esto es, < X1,X2, …, Xn-1 > , es la solución óptima para el problema asociado, es decir, para el problema (1, n-1, C - XnPn)
Su valor (beneficio) asociado es
sujeto a
Supongamos que < X1,X2, …, Xn-1 > NO es la solución óptima del problema (1, n-1, C-XnPn) sino que hay otra
solución, siendo ésta, < Y1, Y2,…, Yn-1 > que mejora el resultado para el problema (1, n-1, C - XnPn)
Su valor (beneficio) asociado es
sujeto a
Dado que < Y1, Y2,…, Yn-1 > mejora el resultado de < X1, X2,…, Xn-1 > , eso implica lo siguiente:
pero entonces sumando XnBn a ambos lados de la desigualdad anterior, se cumpliría que:
lo cual significa que la tupla < Y1, Y2,…, Yn-1, Xn > mejoraría el resultado de < X1, X2, …, Xn-1, Xn > para el problema (1, n, C), lo cual contradice la hipótesis de partida, pues ésta era la solución óptima de dicho problema.
Se cumple, pues, el principio de optimalidad.
Definición recursiva
BACKWARD (HACIA ATRÁS).- Dado que el parámetro 1 va a permanecer invariable a lo largo de todo el proceso recursivo, podemos prescindir del mismo en la representación del problema con el fin de simplificar la notación, esto es,
Mochila(1, j, c) pasa a ser Mochila( j, c)
Llamada inicial: Mochila(n,C)
Otra forma de expresarla
Árbol de llamadas
Sean n=3, C=15 , B[1..3] = {24, 40, 38} y P[1..3] = {5, 6, 9}
Repetición de subproblemas
Desde la perspectiva recursiva el problema está resuelto.
Pero debemos tener en cuenta que la complejidad resultante es de orden exponencial, pues la ecuación recurrente tiene la forma
T(n)=2T(n-1)+c1,
lo cual da lugar a un orden O()
Esta complejidad es debida a la reiteración en la solución de subproblemas.
Estructuras de almacenamiento
Se necesitan dos matrices:
con n+1 filas (para representar el objeto en curso de decisión) y
con C+1 columnas (para representar todos los posibles estados c de la mochila)
Bmax[0..n][0..C] -> en la que se almacena el Beneficio máximo
Dec[0..n][0..C] -> en la que se guarda la decisión que proporciona el beneficio máximo
Proceso de rellenado
1º.- Problemas triviales
Ejemplo: n=3, C=15 , B[1..3] = {24, 40, 38} y P[1..3] = {5, 6, 9}
2º.- Resto de los problemas en orden creciente
Bmax [1][5] = max { Bmax [0][5]+0, Bmax [0][0]+24 }= max {0+0, 0+24} = max {0, 24} = 24
Dec[1][5]=1
Bmax [2][15] = max { Bmax [1][15]+0, Bmax [1][9]+40 }= max {24+0, 24+40} = max {24, 64} = 64
Dec[2][15]=1
Bmax [3][15] = max { Bmax [2][15]+0, Bmax [2][6]+38 }= max {64+0, 40+38} = max {64, 78} = 78
Dec[3][15]=1
Dec[3][15]=1
3º.- Mostrar solución
Consiste en dos partes.-
a) Valor que maximiza la función objetivo
b) Secuencia óptima de decisiones
Solución óptima vista en el árbol de llamadas
Algoritmo
Función Mochila(P[1..n], B[1..n]:vector de enteros; n, C:entero) retorna (p:entero, f[1..n]:vector de enteros)
# Necesita: el número de objetos, los pesos y valores de los n objetos y la capacidad de la mochila
# Produce: El valor de la solución óptima y un vector con la decisión tomada para cada objeto
var
# almacenará el beneficio máximo para cada subproblema
Bmax[0..n][0..C] : matriz de enteros
# registrará la decisión óptima para cada subproblema
Dec[0..n][0..C] : matriz de enteros
# almacenará la secuencia de decisiones óptima
X[1..n] : vector de enteros
# otras variables
j, c : entero
fvar
# 1ª parte: inicializar la estructura de almacenamiento con los resultados de los problemas triviales
para c = 0 hasta C hacer
Bmax [0][c] = 0
Dec [0][c] = 0
fpara
# 2ª parte: rellenar el resto de estructura de almacenamiento con resultados de problemas no triviales, sentido creciente
para j = 1 hasta n hacer
para c = 0 hasta C hacer
si ( c < P[ j ] ) entonces
Bmax [ j ][ c ] = Bmax [ j-1 ][ c ]
Dec [ j ][ c ] = 0
si no
si ( Bmax [ j-1 ][ c ] Bmax [ j-1 ][ c-P[ j ] ] + B[ j ] ) entonces
Bmax [ j ][ c ] = Bmax [ j-1 ][ c ]
Dec [ j ][ c ] = 0
si no
Bmax [ j ][ c ] = Bmax[ j-1 ][ c - P[ j ] ] + B[ j ]
Dec [ j ][ c ] = 1
fsi
fsi
fpara
fpara
# 3ª parte: Mostrar Solución
j = n
c = C
mientras ( j > 0 ) hacer
X[ j ] = Dec [ j ][ c ]
c = c - X[ j ] * P[ j ]
j = j - 1
fmientras
retorna ( Bmax[ n ][ C ], X )
ffunción
Otro enfoque
Tras haber resuelto el problema de la mochila manejando subproblemas de la forma ( 1, j, c ), consistente en resolver óptimamente el subproblema formado por los objetos del 1 al j y con una mochila de capacidad c (BACKWARD o HACIA ATRÁS).-
< X1, …, Xj-1, Xj >
Vamos a mostrar a continuación cómo se resolvería el problema de la mochila manejando los subproblemas del tipo ( j, n, c), consistente en resolver óptimamente el subproblema formado por los objetos del j al n y con una mochila de capacidad c (FORWARD o HACIA ADELANTE).-
< Xj, Xj+1, … Xn >
Principio de optimalidad
”En una secuencia óptima de decisiones, toda subsecuencia debe ser también óptima”
Demostración.-
Sea < X1, X2, …, Xn > la solución óptima para el problema (1, n, C), esto es, para el problema con n objetos (del 1 al n) y una mochila de capacidad C.
Su valor (beneficio) asociado es
sujeto a
Vamos a prescindir de la primera decisión decisión, es decir, X1
La subsecuencia que queda, esto es, < X2,X3, …, Xn > , es la solución óptima para el problema asociado, es decir, para el problema (2, n, C – X1P1)
Su valor (beneficio) asociado es
sujeto a
Supongamos que < X2,X3, …, Xn > NO es la solución óptima del problema (2, n, C-X1P1) sino que hay otra
solución, siendo ésta, < Y2, Y3,…, Yn > que mejora el resultado para el problema (2, n, C – X1P1)
Su valor (beneficio) asociado es
sujeto a
Dado que < Y2, Y3,…, Yn > mejora el resultado de < X2, X3,…, Xn > , eso implica lo siguiente:
pero entonces sumando X1B1 a ambos lados de la desigualdad anterior, se cumpliría que:
lo cual significa que la tupla < X1, Y2, Y3,…, Yn > mejoraría el resultado de < X1, X2, …, Xn > para el problema (1, n, C) lo cual contradice la hipótesis de partida, pues ésta era la solución óptima de dicho problema.
Se cumple, pues, el principio de optimalidad.
Definición recursiva
FORWARD (HACIA ADELANTE).- Dado que el parámetro n va a permanecer invariable a lo largo de todo el proceso recursivo, podemos prescindir del mismo en la representación del problema con el fin de simplificar la notación, esto es,
Mochila( j, n, c ) pasa a ser Mochila( j, c )
Llamada inicial: Mochila(1,C)
Estructuras de almacenamiento
Se necesitan dos matrices:
con n+1 filas (para representar el objeto en curso de decisión) y
con C+1 columnas (para representar todos los posibles estados c de la mochila)
Bmax[1..n+1][0..C] -> en la que se almacena el Beneficio máximo
Dec[1..n+1][0..C] -> en la que se guarda la decisión que proporciona el beneficio máximo
Algoritmo
Función Mochila(P[1..n], B[1..n]:vector de enteros; n, C:entero) retorna (p:entero, f[1..n]:vector de enteros)
# Necesita: el número de objetos, los pesos y valores de los n objetos y la capacidad de la mochila
# Produce: El valor de la solución óptima y un vector con la decisión tomada para cada objeto
var
# almacenará el beneficio máximo para cada subproblema
Bmax[1..n+1][0..C]: matriz de enteros
# registrará la decisión óptima para cada subproblema
Dec[1..n+1][0..C] : matriz de enteros
# almacenará la secuencia de decisiones óptima
X[1..n]: vector de enteros
# otras variables
j, c : entero
fvar
# 1ª parte: inicializar la estructura de almacenamiento con los resultados de los problemas triviales
para c = 0 hasta C hacer
Bmax [n+1][c] = 0
Dec [n+1][c] = 0
fpara
# 2ª parte: rellenar el resto de estructura de almacenamiento con resultados de problemas no triviales, sentido creciente
para j = n hasta 1 hacer
para c = 0 hasta C hacer
si ( c < P[ j ] ) entonces
Bmax [ j ][ c ] = Bmax [ j+1 ][ c ]
Dec [ j ][ c ] = 0
si no
si ( Bmax [ j+1 ][ c ] Bmax [ j+1 ][ c-P[ j ] ] + B[ j ] ) entonces
Bmax [ j ][ c ] = Bmax [ j+1 ][ c ]
Dec [ j ][ c ] = 0
si no
Bmax [ j ][ c ] = Bmax[ j+1 ][ c - P[ j ] ] + B[ j ]
Dec [ j ][ c ] = 1
fsi
fsi
fpara
fpara
# 3ª parte: Mostrar Solución
j = 1
c = C
mientras ( j < n+1 ) hacer
X[ j ] = Dec [ j ][ c ]
c = c - X[ j ] * P[ j ]
j = j + 1
fmientras
retorna ( Bmax[ 1 ][ C ], X )
ffunción
Ejemplo 2: Descomponer un número en sumandos
Dados dos enteros N y M con N >= M > 0, se pide:
descomponer el número N en M sumandos (enteros positivos) de forma que
los M sumandos sumen N y
su producto sea máximo.
Solución como secuencia de decisiones
< S1, S2 , …, SM >
donde Si es el valor correspondiente al sumando i-ésimo. Dicho valor es entero positivo.
Función objetivo y restricciones
La secuencia óptima de decisiones será aquella < S1, S2 , …, SM > tal que maximice la siguiente función
sujeta a la siguiente restricción
Principio de optimalidad
"En una secuencia óptima de decisiones, toda subsecuencia debe ser también óptima”
Demostración.-
Sea <S1, S2, …, SM > la solución óptima para el problema (1, M, N), esto es, para el problema de descomponer N en M sumandos (del 1 al M).
Su valor asociado es
sujeto a
Vamos a prescindir de la última decisión, es decir, SM
La subsecuencia que queda, esto es, <S1, S2, …, SM-1 > , es la solución óptima para el problema asociado, es decir, para el problema (1, M-1, N-SM)
Su valor asociado es
sujeto a
Supongamos que < S1, S2, …, SM-1 > NO es la solución óptima del problema (1, M-1, N-SM) sino que hay otra solución, siendo ésta, < Y1, Y2,…, YM-1 > que mejora el resultado para el problema (1, M-1, N-SM)
Su valor asociado es
sujeto a
Dado que < Y1, Y2,…, YM-1 > mejora el resultado de < S1, S2,…, SM-1 > , eso implica lo siguiente
Pero entonces, multiplicando SM a ambos lados de la desigualdad, se cumpliría que:
lo cual significa que < Y1, Y2,…, YM-1, SM > mejoraría el resultado de < S1, S2, …, SM-1, SM > para el problema
(1, M, N), lo cual contradice la hipótesis de partida, pues ésta última era la solución óptima de dicho problema.
Se cumple, pues, el principio de optimalidad.
Definición recursiva
Tal y como se ve en la demostración del principio de optimalidad, representaremos el problema a resolver por la terna
(1, M, N)
esto es, el problema que debe determinar el valor de los sumandos del 1 al M, los cuales tienen que sumar N y su producto ha de ser máximo.
Existen dos posibilidades:
Manejar subproblemas del tipo ( j, M, n), consistente en resolver óptimamente el subproblema formado por los sumandos del j al M y con un valor a obtener como suma de n.
< Sj, Sj+1, …, SM >
Manejar subproblemas de la forma ( 1, j, n) consistente en resolver óptimamente el subproblema formado por los sumandos del 1 al j y con un valor a obtener como suma de n.
< S1, …, Sj-1, Sj >
Vamos a optar por considerar los problemas del segundo tipo, es decir,
(1, j, n)
dado que en esa línea fue la demostración del principio de optimalidad.
Al igual que ocurría en el problema de la mochila, el parámetro 1 va a permanecer invariable a lo largo de todo el proceso recursivo, por lo que podemos prescindir del mismo en la representación del problema con el fin de simplificar la notación.
Llamaremos Sumandos( j, n) a la solución óptima de este subproblema.
Por tanto, Sumandos( j, n) representa el producto máximo de los j sumandos (del 1 al j) que sumados dan n. La llamada inicial a la función corresponde a j=M y n=N.
Árbol de llamadas
Ejemplo: M=4 y N=7
En él se han desarrollado sólo algunos subproblemas, pero aún así, se puede ver la repetición en el cálculo de subproblemas. En color morado se indican los subproblemas triviales.
Estructuras de almacenamiento
Se necesitan dos matrices:
con M filas (para representar el sumando en curso) y
con N columnas (para representar todos los posibles estados n del número a conseguir)
Pmax[1..M][1..N] -> almacena el producto máximo
Dec[1..M][1..N] -> guarda la decisión que proporciona el producto máximo
Proceso de rellenado
1º.- Problemas triviales
2º.- Resto de subproblemas en sentido creciente
Pmax [4][7] = max { Pmax [3][6]*1, Pmax [3][5]*2, Pmax [3][4]*3, Pmax [3][3]*4 }=
= max {8*1, 4*2, 2*3, 1*4} = 8
Dec[4][7]=1 ó Dec[4][7]=2
3º.-Mostrar solución
a) Valor que maximiza la función objetivo.
Pmax[M][N]
b) Secuencia óptima de decisiones.
Se realiza un recorrido por la estructura que almacena las decisiones (Dec). Este recorrido está guiado por la definición recursiva.
< S1, S2 , S3 , S4 > = < 1, 2, 2, 2 >
Solución óptima en el árbol de llamadas
Algoritmo
Función Sumandos (N, M:entero) retorna (p:entero, S[1..M]:vector de enteros)
# Necesita: número a descomponer (N) y número de sumandos (M) en los que hay que descomponer N
# Produce: El producto de los sumandos de la solución óptima y un vector con el valor de cada sumando
var
# almacenará el beneficio máximo de cada subproblema
Pmax[1..M][1..N]: matriz de enteros
# almacenará la decisión óptima para cada subproblema
Dec[1..M][1..N]: matriz de enteros
# almacenará la secuencia de decisiones óptima
S[1..M]: vector de enteros
# otras variables
j, Sj, n, p:entero
fvar
# 1ª parte: inicializar la estructura de almacenamiento con los resultados de los problemas triviales
para n=1 hasta N hacer
Pmax[1][n] = n
Dec[1][n] = n
fpara
# 2ª parte: rellenar el resto de estructura de almacenamiento con resultados de problemas no triviales, sentido creciente
para j = 2 hasta M hacer
para n = j hasta N hacer
Pmax[ j ][ n ]=1
para Sj = 1 hasta n – j + 1 hacer
p = Pmax[ j -1 ][ n – Sj ] * Sj
si p >= Pmax[ j ][ n ] entonces
Pmax[ j ][ n ] = p
Dec[ j ][ n ] = Sj
fsi
fpara
fpara
fpara
# 3ª parte: Mostrar Solución
j = M
n = N
mientras (j > 0) hacer
S[ j ] = Dec[ j ][ n ]
n = n - S[ j ]
j = j - 1
fmientras
retorna (Pmax[M][N], S)
ffunción
Ejemplo 3: Embarcaderos
En un río hay n embarcaderos (numerados del 1 al n) y en cada uno de ellos se puede alquilar un bote que permite ir a cualquier embarcadero río abajo. Por tanto, existe una matriz C con las tarifas, donde en C[ i ][ j ] se recoge el coste del viaje entre el punto de embarque i y el j, para cualquier embarcadero de partida i y cualquier embarcadero de llegada j más abajo en el río.
Puede que un viaje de i a j sea más caro que una sucesión de viajes más cortos, por ello se trata de determinar cuál es el coste mínimo para ir desde el embarcadero 1 al embarcadero n y cuál es el trayecto que proporciona ese coste.
Se asume que el coste de ir de un embarcadero a él mismo es cero, o sea,
C[ i ][ i ] = 0 i 1..n
La única limitación que existe en este problema es que desde un embarcadero no se puede volver a ninguno de los anteriores.
¿Embarcaderos(1,6)?
Solución como secuencia de decisiones
<x1, x2, …, xs> con 1 <= s <= n-1
en cada una de las decisiones optamos por uno de los embarcaderos situados más adelante en el río con respecto al embarcadero actual.
x1 representa el embarcadero al que viajamos tras el embarcadero 1, por tanto
x1 { j / 1 < j ≤ n } = { 2, 3,…, n }
<x1, x2, …,xs>
x2 por su parte, representa el embarcadero al que viajamos desde x1, así
x2 { j / x1 < j ≤ n } = { x1+1, x1+2, …, n }
y así sucesivamente hasta alcanzar el embarcadero de destino (xs=n), o lo que es lo mismo, hasta que el conjunto de alternativas sea vacío.
Función objetivo y restricciones
Se trata de minimizar por tanto el coste
C[1][x1]+C[x1][x2]+…+C[xs-1][xs]
o lo que es lo mismo
C[1][x1]+C[x1][x2]+…+C[xs-1][n]
sujeto a
1 < x1 < x2 < … < xs
Principio de optimalidad
Sea <x1, x2, …, xs> la solución óptima para el problema de los embarcaderos del 1 al n. Dicho problema lo vamos a representar como (1, n). Y su valor asociado es:
C[1][x1]+C[x1][x2]+…+C[xs-1][n]
Dicha secuencia cumple que 1 < x1 < x2 < … < xs
Si prescindimos de la primera decisión, x1, la subsecuencia que nos queda es <x2, …, xs> la cual es la solución óptima al problema de los embarcaderos del x1 al n.
Dicho problema lo representaremos como (x1, n)
Supongamos que existe otra secuencia de decisiones que proporciona un coste menor para el problema (x1, n), siendo ésta:
<y1, …, ym> sujeta a x1 < y1 < y2 < … < ym-1 < ym
donde ym=n.
Entonces ocurrirá que
C[x1][y1]+ … + C[ym-1][n] < C[x1][x2]+ … + C[xs-1][n]
Pero sumando a ambos lados el coste C[1][x1] nos encontraríamos con que
C[1][x1] + C[x1][y1]+ … + C[ym-1][n] < C[1][x1] + C[x1][x2]+ … + C[xs-1][n]
lo cual es contradictorio, porque entonces la secuencia <x1,y1, …, ym> resolvería el problema (1, n) con un coste inferior a la secuencia <x1, x2, …, xs>, pues ésta última era la solución óptima de dicho problema.
Definición recursiva
Representaremos el problema a través de dos parámetros (1, n), que corresponde al coste mínimo para ir del embarcadero 1 al embarcadero n.
De forma genérica, vamos a manejar los subproblemas ( j, n) consistentes en resolver óptimamente el problema de los embarcaderos desde el embarcadero j al embarcadero n.
Dado que el parámetro n va a permanecer invariable a lo largo de toda la secuencia de decisiones, podemos prescindir del mismo en la representación del problema con el fin de simplificar la notación.
Plantearemos la siguiente ecuación recursiva
donde Embarcaderos( j ) devolverá el coste mínimo para ir desde el embarcadero j al embarcadero n.
Llamada inicial a la función: Embarcaderos(1)
Árbol de llamadas y repetición de subproblemas
Estructuras de almacenamiento
Utilizaremos estructuras unidimensionales, pues hay un único parámetro en la ecuación recursiva. Los vectores tendrán n posiciones, tantas como embarcaderos desde los que se puede viajar a n.
Costemin[1..n] -> almacena el coste mínimo
Dec[1..n] -> guarda la decisión que proporciona el coste mínimo
Orden de los subproblemas
1º TRIVIALES ( j = n ), en nuestro caso j = 6.
2º el subproblema Embarcaderos(5) ya que requiere el subproblema Embarcaderos(6) y éste ya está resuelto.
3º el subproblema Embarcaderos(4) ya que requiere de Embarcaderos(5) y de Embarcaderos(6) y éstos ya están resueltos.
…
Finalmente resolveremos Embarcaderos(1) ya que necesita de todos los anteriores: Embarcaderos(2), Embarcaderos(3), … Embarcaderos(6) y éstos ya están resueltos.
En términos generales, los subproblemas se resuelven en el siguiente orden:
Embarcaderos(n),
Embarcaderos(n-1),
…,
Embarcaderos(1).
Proceso de rellenado (en Costemin y Dec)
Ejemplo: n=6 y la matriz C de costes es la siguiente:
Primero rellenamos el caso base ( Embarcaderos(6) = 0 ) que corresponde a:
Seguidamente rellenamos el resto de la estructura desde la posición n-1 a la 1.
Luego, calculamos
Costemin[5] = min5 < k ≤ 6 { C[5][k] + Costemin[k]} =min {C[5][6]+Costemin[6] } = min { 7+0 } = 7
Dec[5] = 6
Y por último,
Costemin[1] = min { C[1][2]+Costemin[2], C[1][3]+Costemin[3],
C[1][4]+Costemin[4],C[1][5]+Costemin[5]+, C[1][6]+Costemin[6] } = min { 10+4, 6+11, 15+3, 23+7, 30+0 } = 14
Dec[1] = 2
Mostrar solución
Valor que minimiza la función objetivo.
El coste óptimo es Costemin[1]=14
Secuencia óptima de decisiones.
Se realiza un recorrido por la estructura que almacena las decisiones (Dec). Este recorrido está guiado por la definición recursiva.
Dec[1] = 2 -> x1
Dec[2] = 4 -> x2
Dec[4] = 6 -> x3
Solución óptima en el árbol de llamadas
Secuencia óptima.- <x1, x2, x3> = < 2, 4, 6 >
Algoritmo
Función Embarcaderos(C[1..n][1..n]:matriz de enteros; n:entero) retorna (p:entero, f[1..n-1]:vector de enteros)
# Necesita: el número de embarcaderos (n) y los costes de los viajes entre embarcaderos (C)
# Produce: El valor de la solución óptima y un vector con los embarcaderos en los que hay que parar
var
# almacenará el coste mínimo para cada subproblema
Costemin[1..n] : vector de enteros
# almacenará la decisión óptima para cada subproblema
Dec[1..n] : vector de enteros
# almacenará la secuencia de decisiones óptima
X[1..n-1] : vector de enteros
# otras variables
j , k : entero
fvar
# 1ª parte: inicializar la estructura de almacenamiento con los resultados de los problemas triviales
Costemin[n] = 0
Dec[n] = n
# 2ª parte: rellenar el resto de estructura de almacenamiento con resultados de problemas no triviales, sentido creciente
para j = n-1 hasta 1 hacer
Costemin[ j ] = ∞
para k = j +1 hasta n hacer
si Costemin[ j ] > C[ j ][ k ] + Costemin[ k ] entonces
Costemin[ j ] = C[ j ][ k ] + Costemin[ k ]
Dec[ j ] = k
fsi
fpara
fpara
# 3ª parte: Mostrar Solución
X[1] = Dec[1]
j = 1
mientras X[ j ] ≠ n hacer
j = j + 1
X[ j ] = Dec[X[ j - 1]]
fmientras
retorna (Costemin[1], X)
ffunción
Aplicaciones de Programación Dinámica: Ejemplos
Camino más corto que une cada par de vértices de un grafo:
Algoritmo de Floyd_Warshall (no hay pesos negativos)
Algoritmo de Bellman-Ford (hay pesos negativos)
Distancia de edición (también conocida como distancia de Levenshtein) mide la diferencia entre dos cadenas s y t como el número mínimo de operaciones de edición que hay que realizar para convertir una cadena en otra)
Correctores ortográficos,
Detección de plagios,
…
Distancia entre dos series temporales: O(n2)
Algoritmo DTW permite medir la similitud entre dos secuencias que pueden variar en el tiempo o en el espacio.
Análisis sintáctico: O(n3)
Algoritmo Cocke-Younger-Kasami (Algoritmo CKY),
Algoritmo de Early
Algoritmo de Viterbi:
decodificación de señales,
procesamiento de lenguaje natural,
bioinformática
…
Multiplicación encadenada de matrices
Problema de subsecuencia común más larga ( LCS problem ) en el que se trata de encontrar la subsecuencia más larga que es común en un conjunto de secuencias. El problema de LCS es uno de los problemas clásicos de las ciencias computacionales y es la base de programas que comparan datos como la utilidad diff.
Last updated