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(2n2^n)

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 \foralli 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 \in { j / 1 < j ≤ n } = { 2, 3,…, n }

<x1, x2, …,xs>

x2 por su parte, representa el embarcadero al que viajamos desde x1, así

x2 \in { 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