Algoritmia – Teoría

Tema 7 – Programación dinámica

David Llorens

30 de noviembre de 2023

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 1 / 92

Tema 7
Programación dinámica

1. Introducción

2. El problema del cambio generalizado

3. Implementación de ecuaciones recursivas

4. Obtención de ecuaciones recursivas

5. Ejemplos

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 2 / 92

Tema 7
Programación dinámica

1. Introducción
1.1 Subestructura óptima
1.2 Subproblemas superpuestos
1.3 Aplicación de la programación dinámica

2. El problema del cambio generalizado

3. Implementación de ecuaciones recursivas

4. Obtención de ecuaciones recursivas

5. Ejemplos

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 3 / 92

Tema 7 – Programación dinámica
1. Introducción

Programación dinámica (PD) es una estrategia algorítmica para la

evaluación eficiente de cierta familia de funciones recursivas.

La recursividad divide el problema en subproblemas más simples. A

diferencia de “divide y vencerás”, los subproblemas son de talla similar
al original (una decisión menos).
Funciona en aquellos problemas que presentan:
Subestructura óptima
Subproblemas superpuestos

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 4 / 92

1. Introducción
1.1. Subestructura óptima

Podemos utilizar las soluciones óptimas de los subproblemas para

encontrar la solución óptima del problema original.
Ejemplo de problema con subestructura óptima: Averiguar la nota
más alta en la selectividad de un país.
Podemos preguntar a cada provincia la mejor nota que se ha obtenido.
La nota de selectividad mas alta será la más alta entre ellas.

Ejemplo de problema sin subestructura óptima: Averiguar la mayor

diferencia entre las notas de selectividad de un país.
Aunque sepamos la mayor diferencia de notas en cada provincia, no
podemos calcular la mayor diferencia en notas del país.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 5 / 92

1. Introducción
1.2. Subproblemas superpuestos

Tenemos subproblemas superpuestos cuando se usa un mismo

subproblema para resolver varios problemas de mayor tamaño.
Ejemplo:
El quinto miembro de la sucesión de Fibonacci es:
F5 = F4 + F3 = (F3 + F2 ) + (F2 + F1 ) = ((F2 + F1 ) + F2 ) + (F2 + F1 )

Por lo tanto, para calcular F5 , F2 se calculará tres veces.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 6 / 92

1. Introducción
1.2. Subproblemas superpuestos - Memoización

Programación dinámica utiliza una técnica denominada memoización

(memoizing ) para tratar eficientemente los subproblemas
superpuestos.

La memoización consiste en guardarse los resultados de las llamadas

recursivas para evitar que se tengan que volver a calcular.

Los resultados se guardan en un diccionario en el que las claves son

las tuplas formadas por los valores de los parámetros de cada llamada
recursiva.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 7 / 92

1.2. Subproblemas superpuestos
Ejemplo: n-ésimo número de Fibonacci

Podemos definir los números de Fibonacci con la siguiente ecuación

recursiva:

0, si n = 0;


F (n) = 1, si n = 1;
F (n − 1) + F (n − 2), si n > 1.



Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 8 / 92

1.2. Subproblemas superpuestos
Fibonacci: Implementación sin memoización

def fib(n: int) -> int:

global fib_calls # Contador de llamadas
fib_calls += 1 # Incrementamos el contador en cada llamada
if n == 0: return 0
if n == 1: return 1
return fib(n-2) + fib(n-1)

fib_calls = 0 # Inicializamos el contador de llamadas

print(f'fib(30): {fib(30)}') # Calculamos fib(30)
print(f'Llamadas: {fib_calls}') # Hemos hecho 2692537 llamadas a fib

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 9 / 92

1.2. Subproblemas superpuestos
Fibonacci: Implementación con memoización

def fib_mem(n: int) -> int:

def fib(n: int):
global fib_calls # Contador de llamadas
fib_calls += 1 # Incrementamos el contador en cada llamada
if n == 0: return 0
if n == 1: return 1
if n not in mem:
mem[n] = fib(n - 2) + fib(n - 1)
return mem[n]
mem: dict[int, int] = {} # Clave: tipo de n,Valor: tipo de fib(n)
return fib(n)

fib_calls = 0 # Inicializamos el contador de llamadas

print(f'fib_mem(30): {fib_mem(30)}') # Calculamos fib(30)
print(f'Llamadas: {fib_calls}') # Hemos hecho 59 llamadas a fib

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 10 / 92

1. Introducción
1.3. Aplicación de la programación dinámica

Si un problema tiene subestructura óptima y subproblemas

superpuestos, podemos resolverlo mediante programación dinámica:
1. Obtener una ecuación recursiva a partir del enunciado del problema.
Suele ser la parte más difícil.
2. Implementar la ecuación recursiva como una función recursiva.
Veremos varias alternativas.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 11 / 92

Tema 7
Programación dinámica

1. Introducción

2. El problema del cambio generalizado

2.1 Formalización
2.2 La ecuación recursiva

3. Implementación de ecuaciones recursivas

4. Obtención de ecuaciones recursivas

5. Ejemplos

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 12 / 92

Tema 7 – Programación dinámica
2. El problema del cambio generalizado

El problema del cambio lo hemos visto varias veces en la asignatura.

La versión generalizada consiste en añadir un peso diferente a cada

tipo de moneda, con el objetivo de encontrar el cambio de peso
mínimo.
Datos de entrada:
Una cantidad a devolver: Q
Un vector de valores de moneda: v = (v0 , v1 , . . . , vN −1 )
Un vector de pesos de moneda: w = (w0 , w1 , . . . , wN −1 )
El problema: Obtener el cambio de menor peso.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 13 / 92

2. El problema del cambio generalizado
2.1. Formalización

El conjunto de soluciones (todos los cambios válidos):

( )
N −1
X = (x0 , x1 , . . . , xN −1 ) ∈ N N
∑ xi vi = Q
i =0

La función objetivo (dado un cambio, devuelve su peso):

N −1
f (x0 , x1 , . . . , xN −1 ) = ∑ xi wi
i =0

La solución óptima, xb, es el cambio de menor peso:

N −1
xb = arg mín f (x ) =
x ∈X
arg mín ∑ xi wi
(x0 ,x1 ,...,xN −1 )∈X i =0

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 14 / 92

2. El problema del cambio generalizado
2.2. La ecuación recursiva

Sea xb ∈ X la solución óptima (el cambio de menor peso).

Sea s[
core = f (xb), la puntuación de la solución óptima (su peso).

La ecuación recursiva sólo calcula s[

core. Al implementarla como
función nos encargaremos de que también devuelva xb.

Ecuación recursiva para el problema del cambio generalizado:


0,
 si n = 0 ∧ q = 0;
+∞,

si n = 0 ∧ q > 0;

S (q, n) =

 mı́n k S (q − d · vn−1 , n − 1) + d · wn−1 , si n > 0.
0≤d ≤ j q

vn − 1

donde q es la cantidad a devolver y n el número de decisiones

tomadas.
Dada la ecuación anterior: s[
core = S (Q, N )
Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 15 / 92
Tema 7
Programación dinámica

1. Introducción

2. El problema del cambio generalizado

3. Implementación de ecuaciones recursivas

3.1 Implementación recursiva directa
3.2 Implementación recursiva con memoización
3.3 Implementación recursiva con recuperación de camino
3.4 Implementación iterativa
3.5 Implementación iterativa con reducción del coste espacial

4. Obtención de ecuaciones recursivas

5. Ejemplos

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 16 / 92

Tema 7 – Programación dinámica
3. Implementación de ecuaciones recursivas

Implementaciones recursivas:
Recursiva directa: la traducción directa de la ecuación recursiva.
Devuelve la puntuación de la mejor solución. Suele tener un coste
exponencial (por la repetición de cálculos), por lo que no se utiliza.
Recursiva con memoización: devuelve la puntuación de la mejor
solución (sin repetir cálculos).
Recursiva con memoización y recuperación de camino: devuelve la
mejor solución y su puntuación.

Implementaciones iterativas:
Iterativa con recuperación de camino: devuelve la mejor solución y su
puntuación.
Iterativa con reducción del coste espacial: devuelve sólo la puntuación
de la mejor solución.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 17 / 92

3.1. Implementación recursiva directa
El problema del cambio (sin memoización)
Score = Union[int, float] # El Score es un peso,pero puede ser infinity

def coin_change_no_mem(v: list[int], w: list[int], Q: int) -> Score:

def S(q: int, n: int) -> Score:
# Casos base
if q == 0 and n == 0: return 0 # Caso base 'bueno'
if q > 0 and n == 0: return infinity # Caso base 'malo'
# Recursividad
best_score = infinity
for d in range(q // v[n - 1] + 1):
q_prev, n_prev = q - d * v[n - 1], n - 1
current_score = S(q_prev, n_prev) + d * w[n - 1]
if current_score < best_score: # Minimización
best_score = current_score
return best_score

return S(Q, len(v))

values, weights, quantity = [1, 2, 4], [2, 3, 9], 7

print(coin_change_no_mem(values, weights, quantity)) # output: 11
Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 18 / 92
3.1. Implementación recursiva directa
Grafo de dependencias que se genera para calcular S (7, 3)

Instancia: Q = 7, v = (1, 2, 4) y w = (2, 3, 9).

Observación importante: S (3, 1) y S (1, 1) se calculan dos veces.

S(7,0) S(7,1) S(7,2) S(7,3)

S(6,0)

S(5,0) S(5,1)

S(4,0)

S(3,0) S(3,1) S(3,2)

S(2,0)

S(1,0) S(1,1)

S(0,0)

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 19 / 92

3.1. Implementación recursiva directa
El problema del cambio (sin memoización) - Costes

Coste espacial. Número máximo de tramas de activación × Tamaño

trama: O (N ) · O (1) = O (N )

Coste temporal. Exponencial debido a la repetición de subproblemas.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 20 / 92

3.2. Implementación recursiva con memoización
El problema del cambio (con memoización)

Score = Union[int, float] # El Score es un peso,pero puede ser infinity

SParams = tuple[int, int] # Los tipos de los parámetros de la función S: (q,n)

def coin_change_mem(v: list[int], w: list[int], Q: int) -> Score:

def S(q: int, n: int) -> Score:
# Casos base
if q == 0 and n == 0: return 0 # Caso base 'bueno'
if q > 0 and n == 0: return infinity # Caso base 'malo'

# Recursividad con memoización

if (q, n) not in mem:
mem[q, n] = infinity
for d in range(q // v[n - 1] + 1):
q_prev, n_prev = q - d * v[n - 1], n - 1
current_score = S(q_prev, n_prev) + d * w[n - 1]
if current_score < mem[q, n]: # Minimización
mem[q, n] = current_score
return mem[q, n]

mem: dict[SParams, Score] = {}

return S(Q, len(v))

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 21 / 92

3.2. Implementación recursiva con memoización
El diccionario mem

El diccionario mem memoiza las llamadas a S(q, n) por lo que su

clave es una tupla con los parámetros de la llamada (q, n) y su valor
es la puntuación devuelta por la llamada (un entero).

Veamos los tipos involucrados en el diccionario mem:

SParams = tuple[int, int] # tupla con los tipos de los parám. de S
Score = Union[int, float] # El peso es un int,pero puede ser inf.
mem: dict[SParams, Score] = {}

mem[q, n] contiene el peso de la mejor solución que devuelve la

cantidad q tras tomar n decisiones (sobre las n primeras monedas del
sistema monetario).

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 22 / 92

3.2. Implementación recursiva con memoización
Grafo de dependencias que se genera para calcular S (7, 3)

Instancia: Q = 7, v = (1, 2, 4) y w = (2, 3, 9).

Memoización: S (3, 1) y S (1, 1) se llaman dos veces pero se calculan una.

S(7,0) S(7,1) S(7,2) S(7,3)

S(6,0)

S(5,0) S(5,1)

S(4,0)

S(3,0) S(3,1) S(3,2)

S(2,0)

S(1,0) S(1,1)

S(0,0)

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 23 / 92

3.2. Implementación recursiva con memoización
El problema del cambio (con memoización) - Coste espacial

El coste espacial es la suma de:

El tamaño del código y de las variables independientes de la talla: O (1)
El tamaño del diccionario mem: O (Q N ), donde N = len(v ). Suele ser
el mayor de los tres costes.
El tamaño de la pila de llamadas a función. Número máximo de tramas
de activación × Tamaño de trama: O (N ) · O (1) = O (N ).

Por la tanto, el coste espacial es O (Q N ). Como veremos después,

este coste es pseudopolinómico.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 24 / 92

3.2. Implementación recursiva con memoización
El problema del cambio (con memoización) - Coste temporal

El coste temporal de las implementaciones con memoización suele ser

el coste de rellenar la estructura mem:
Como hemos visto, la estructura mem tiene Q N elementos.
¿Cuánto cuesta calcular un elemento de mem? En la implementación
vemos un bucle que hace, como mucho, Q iteraciones, todas de coste
constante, por lo que el coste de calcular un elemento de mem es O (Q ).

Multiplicando ambos costes obtenemos el coste temporal: O (Q 2 N ).

Como el anterior, este coste es pseudopolinómico. Veamos qué
significa esto.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 25 / 92

3.2. Implementación recursiva con memoización
El problema del cambio (con memoización) - Costes pseudopolinómicos

El coste espacial O (Q N ) y el temporal O (Q 2 N ) parecen polinómicos,

pero no lo son, N es la talla de un vector pero Q es sólo un número
que indica una cantidad.

¿Cuál es la talla de un número? Si utilizamos la representación en

binario, la talla de un número de b bits es 2b . Por ejemplo, el número
32 en binario es ‘100000’, por lo que su talla es 26 . Cada bit que
añadamos, duplicará la talla.

Resumiendo, si Q tiene b bits, tenemos que |Q | = 2b .

Por lo tanto, los costes originales se pueden reescribir como:
Espacial: O (Q N ) = O (2b N )
Temporal: O (Q 2 N ) = O ((2b )2 N ) = O ((22 )b N ) = O (4b N ).

Ambos costes son exponenciales con el número de bits de Q.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 26 / 92
3. Implementación de ecuaciones recursivas
3.3. Implementación recursiva con recuperación de camino

Los algoritmos anteriores devuelven la puntuación (el peso) de la

solución óptima, pero no qué monedas la forman.

Para obtener las monedas necesitamos guardar qué arco gana la

minimización para poder recuperar el camino. Realmente lo que nos
interesa es el nodo origen del arco y la decisión que representa dicho
arco.

¿Dónde guardamos el nodo origen “ganador” y su decisión? Durante

la recursividad, vamos a guardarlos en el diccionario de la
memoización, mem, acompañando a las puntuaciones.

Tras finalizar la recursividad, utilizaremos esta información para

efectuar la recuperación del camino.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 27 / 92

3.3. Implementación recursiva con recuperación de camino
El problema del cambio (con recup. de camino)
def coin_change(v: list[int], w: list[int], Q: int)-> tuple[Score, list[Decision]]:
def S(q: int, n: int) -> Score: # Decision = int
if q == 0 and n == 0: return 0 # Caso base 'bueno'
if q > 0 and n == 0: return infinity # Caso base 'malo'
if (q, n) not in mem: # Recursividad con memoización
mem[q, n] = infinity, (-1, -1), -1
for d in range(q // v[n - 1] + 1):
q_prev, n_prev = q - d * v[n - 1], n - 1
current_score = S(q_prev, n_prev) + d * w[n - 1]
if current_score < mem[q, n][0]: # Minimización
mem[q, n] = current_score, (q_prev, n_prev), d
return mem[q, n][0]

mem: dict[SParams, tuple[Score, SParams, Decision]] = {}

score = S(Q, len(v)) # La puntuación de la solución óptima (su peso)
decisions: list[Decision] = [] #
if score != infinity: #
q, n = Q, len(v) #
while (q, n) != (0, 0): # Recupera las decisiones (si hay solución)
_, (q, n), d = mem[q, n] #
[Link](d) #
[Link]() #
return score, decisions
Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 28 / 92
3.3. Implementación recursiva con recuperación de camino
El nuevo diccionario mem

Veamos los tipos involucrados en el nuevo diccionario mem:

SParams = tuple[int, int] # tupla con los tipos de los parám. de S
Score = Union[int, float] # El peso es un int,pero puede ser inf.
Decision = int # Número de monedas utilizadas de un tipo
mem: dict[SParams, tuple[Score, SParams, Decision]] = {}

mem[q, n] contiene una tupla de tres elementos:

score: el peso de la mejor solución que devuelve la cantidad q
utilizando las n primeras monedas del sistema monetario.
(q ′ , n′ ): La tupla con los parámetros del problema previo.
La decisión elegida para pasar del estado (q ′ , n′ ) al estado (q, n).

Podemos recuperar las decisiones que forman la solución óptima

partiendo de mem[Q,N].

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 29 / 92

3.3. Implementación recursiva con recuperación de camino
Grafo de dependencias que se genera para calcular S (7, 3)

Instancia: Q = 7, v = (1, 2, 4) y w = (2, 3, 9). Es el mismo grafo en

las tres versiones recursivas:

S(7,0) S(7,1) S(7,2) S(7,3)

S(6,0)

S(5,0) S(5,1)

S(4,0)

S(3,0) S(3,1) S(3,2)

S(2,0)

S(1,0) S(1,1)

S(0,0)

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 30 / 92

3.3. Implementación recursiva con recuperación de camino
Visualización del contenido de mem tras calcular S (7, 3)

Instancia: Q = 7, v = (1, 2, 4) y w = (2, 3, 9).

[7,0] [7,1] [7,2] [7,3]

inf 14 11 11
- 7 3 0

[6,0]
inf
-

[5,0] [5,1]
inf 10
- 5

[4,0]
inf
-

Q
[3,0] [3,1] [3,2]
inf 6 5
- 3 1

[2,0]
inf
-

[1,0] [1,1]
inf 2
- 1

[0,0]
0
-

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 31 / 92

3.3. Implementación recursiva con recuperación de camino
El problema del cambio (con recup. de camino) - Costes

La recuperación del camino no afecta a los costes, que se mantienen:

Coste temporal: O (Q 2 N ).
Coste espacial: O (Q N ).

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 32 / 92

3.4. Implementación iterativa
El problema del cambio (iterativa con recup. de camino)

def cc_iter(v: list[int], w: list[int], Q: int) -> tuple[Score, list[Decision]]:

mem: dict[SParams, tuple[Score, SParams, Decision]] = {}
mem[0, 0] = 0, (-1, -1), -1 #
for q in range(1, Q + 1): # Rellena mem[.,0]
mem[q, 0] = infinity, (-1, -1), -1 #
for n in range(1, len(v) + 1):
for q in range(0, Q + 1): #
mem[q, n] = infinity, (-1, -1), -1 #
for d in range(q // v[n - 1] + 1): #
q_p, n_p = q - d * v[n - 1], n - 1 # Rellena mem[.,n]
c_score = mem[q_p, n_p][0] + d * w[n - 1] #
if c_score < mem[q, n][0]: #
mem[q, n] = c_score, (q_p, n_p), d #
score = mem[Q, len(v)][0] # La puntuación de la solución óptima (su peso)
decisions: list[Decision] = [] #
if score != infinity: #
q, n = Q, len(v) #
while (q, n) != (0, 0): # Recupera las decisiones (si hay solución)
_, (q, n), d = mem[q, n] #
[Link](d) #
[Link]() #
return score, decisions

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 33 / 92

3.4. Implementación iterativa
Grafo de dependencias que se genera para calcular S (7, 3)

Instancia: Q = 7, v = (1, 2, 4) y w = (2, 3, 9).

S(7,0) S(7,1) S(7,2) S(7,3)

S(6,0) S(6,1) S(6,2) S(6,3)

S(5,0) S(5,1) S(5,2) S(5,3)

S(4,0) S(4,1) S(4,2) S(4,3)

S(3,0) S(3,1) S(3,2) S(3,3)

S(2,0) S(2,1) S(2,2) S(2,3)

S(1,0) S(1,1) S(1,2) S(1,3)

S(0,0) S(0,1) S(0,2) S(0,3)

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 34 / 92

3.4. Implementación iterativa
Visualización del contenido de mem tras calcular S (7, 3)

Instancia: Q = 7, v = (1, 2, 4) y w = (2, 3, 9).

[7,0] [7,1] [7,2] [7,3]
inf 14 11 11
- 7 3 0

[6,0] [6,1] [6,2] [6,3]

inf 12 9 9
- 6 3 0

[5,0] [5,1] [5,2] [5,3]

inf 10 8 8
- 5 2 0

[4,0] [4,1] [4,2] [4,3]

inf 8 6 6
- 4 2 0

Q
[3,0] [3,1] [3,2] [3,3]
inf 6 5 5
- 3 1 0

[2,0] [2,1] [2,2] [2,3]

inf 4 3 3
- 2 1 0

[1,0] [1,1] [1,2] [1,3]

inf 2 2 2
- 1 0 0

[0,0] [0,1] [0,2] [0,3]

0 0 0 0
- 0 0 0

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 35 / 92

3.4. Implementación iterativa
El problema del cambio (iterativa con recup. de camino) - Costes

La versión iterativa con recuperación de camino no modifica los

costes:
Coste temporal: O (Q 2 N ).
Coste espacial: O (Q N ).

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 36 / 92

3.4. Implementación iterativa
Versiones con recuperación de camino: recursiva vs iterativa

S(7,0) S(7,1) S(7,2) S(7,3) S(7,0) S(7,1) S(7,2) S(7,3)

S(6,0) S(6,0) S(6,1) S(6,2) S(6,3)

S(5,0) S(5,1) S(5,0) S(5,1) S(5,2) S(5,3)

S(4,0) S(4,0) S(4,1) S(4,2) S(4,3)

Q Q

S(3,0) S(3,1) S(3,2) S(3,0) S(3,1) S(3,2) S(3,3)

S(2,0) S(2,0) S(2,1) S(2,2) S(2,3)

S(1,0) S(1,1) S(1,0) S(1,1) S(1,2) S(1,3)

S(0,0) S(0,0) S(0,1) S(0,2) S(0,3)

N N

Versión recursiva Versión iterativa

Ventajas de la versión recursiva:

Más sencilla de implementar (es prácticamente la ecuación recursiva).
No recorre todo el espacio de estados.

Ventajas de la versión iterativa:

Suele ser más rápida: pese a recorrer todos los estados, no tiene el
sobrecoste de la recursividad.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 37 / 92

3.5. Implementación iterativa con reducción del coste espacial
El problema del cambio (iterativa sin recup. de camino)

Si sólo nos interesa la puntuación de la solución óptima, podemos modificar

la versión iterativa para reducir el coste espacial.

Idea: Reemplazar el diccionario mem por dos vectores, current y previous,

que mantienen la columna actual y la previa del grafo de dependencias.

def coin_change_iter_score(v: list[int], w: list[int], Q: int) -> Score:

previous: list[Score] = [0] * (Q + 1)
current: list[Score] = [0] + [infinity] * Q
for n in range(1, len(v) + 1):
previous, current = current, current
for q in range(0, Q + 1):
current[q] = infinity
for d in range(q // v[n - 1] + 1):
current_score = previous[q - d * v[n - 1]] + d * w[n - 1]
if current_score < current[q]:
current[q] = current_score
return current[Q]

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 38 / 92

3.5. Implementación iterativa con reducción del coste espacial
El problema del cambio (iterativa sin recup. de camino) - Costes

Coste temporal: O (Q 2 N ). No ha cambiado.

Coste espacial: O (Q ). Se ha reducido, era O (Q N ).

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 39 / 92

Tema 7
Programación dinámica

1. Introducción

2. El problema del cambio generalizado

3. Implementación de ecuaciones recursivas

4. Obtención de ecuaciones recursivas

4.1 El problema del cambio generalizado
4.2 El problema del cambio generalizado (X alternativo)
4.3 La plantilla de programación dinámica

5. Ejemplos

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 40 / 92

Tema 7 – Programación dinámica
4. Obtención de ecuaciones recursivas

Formalizaremos el problema para obtener:

El conjunto de soluciones: X
La función objetivo (que permite puntuar cada solución): f

Que utilizamos para calcular:

La solución óptima: xb = arg opt f (x )
x ∈X

La puntuación de la solución óptima: s[

core = opt f (x )
x ∈X
donde opt es mı́n o máx según si el problema es de minimización o de
maximización.

Utilizaremos la ecuación de la puntuación de la solución óptima

para obtener la ecuación recursiva.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 41 / 92

4. Obtención de ecuaciones recursivas
4.1. El problema del cambio generalizado (I)

Recordemos el conjunto de soluciones:

( )
N −1
X = (x0 , x1 , . . . , xN −1 ) ∈ N N
∑ xi vi = Q
i =0

En PD nos resulta útil poder expresar las conjuntos de soluciones de

los problemas “previos” (con menos decisiones).

Con este objetivo utilizaremos el conjunto X parametrizado:

( )
n −1
Xq,n = (x0 , x1 , . . . , xn−1 ) ∈ Nn ∑ xi vi = q
i =0

El conjunto de soluciones del problema original será ahora XQ,N .

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 42 / 92

4. Obtención de ecuaciones recursivas
4.1. El problema del cambio generalizado (y II)

Recordemos la función objetivo:

N −1
f ((x0 , x1 , . . . , xN −1 )) = ∑ xi wi
i =0

La solución óptima, xb, es la que minimiza la función objetivo (la

solución de menor peso):
N −1
xb = arg mín f (x ) =
x ∈XQ,N
arg mín ∑ xi wi
(x0 ,x1 ,...,xN −1 )∈XQ,N i =0

La puntuación de la solución óptima (su peso), s[

core:
N −1
core = mı́n f (x ) =
s[
x ∈XQ,N
mı́n ∑
(x0 ,...,xN −1 )∈XQ,N i =0
xi wi

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 43 / 92

4.1. El problema del cambio generalizado
Pasos para la obtención de la ecuación recursiva (I)

1. Partimos de la puntuación de la solución óptima, s[

core:

N −1
core =
s[ mı́n
(x0 ,...,xN −1 )∈XQ,N i =0
∑ xi wi

2. Minimizamos por separado el último elemento del sumatorio, xN −1 :

 
N −1
mı́nj mı́n ∑
 
core =
s[ 
k xi wi 
0≤xN −1 ≤ Q (x0 ,...,xN −2 )∈ i =0 
vN −1 XQ −xN −1 vN −1 ,N −1

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 44 / 92

4.1. El problema del cambio generalizado
Pasos para la obtención de la ecuación recursiva (II)

3. Sacamos el último término del sumatorio de la minimización interior:

  
N −2
mı́nj mı́n ∑
  
core =
s[ 
k   + xN −1 wN −1 
xi wi  
0≤xN −1 ≤ Q (x0 ,...,xN −2 )∈ i =0
vN − 1 XQ −xN −1 vN −1 ,N −1

La recursividad ya puede apreciarse en la minimización interior,

comparándola con la minimización del paso 1.
La nueva minimización tiene una decisión menos que la del paso 1.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 45 / 92

4.1. El problema del cambio generalizado
Pasos para la obtención de la ecuación recursiva (III)

4. Definimos una función capaz de representar ambas minimizaciones:

n −1
S (q, n) = mı́n ∑ xi w i
(x0 ,x1 ,...,xn−1 )∈Xq,n i =0

5. Reescribimos las ecuaciones de los pasos 1 y 3 con esta nueva función:

core = S (Q, N )
s[
mı́nj S (Q − xN −1 vN −1 , N − 1) + xN −1 wN −1


core =
s[ k
Q
0≤xN −1 ≤ vN −1

Por lo tanto:

mı́nj S ( Q − xN − 1 vN − 1 , N − 1 ) + xN − 1 w N − 1


S (Q, N ) = k
Q
0≤xN −1 ≤ vN − 1

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 46 / 92

4.1. El problema del cambio generalizado
Pasos para la obtención de la ecuación recursiva (y IV)

6. La función S será nuestra ecuación recursiva, que generalizamos para

cualquier valor de q y n:

S (q, n) = mı́nj k (S (q − xn−1 vn−1 , n − 1) + xn−1 wn−1 )

q
0≤xn−1 ≤ vn−1

7. Para simplificar, renombramos xn−1 como d (de decisión):

S (q, n) = mı́n
j k (S (q − d · vn−1 , n − 1) + d · wn−1 )
q
0≤d ≤ vn − 1

8. Por último, añadimos los casos base de la recursión:



 0, si n = 0 ∧ q = 0;
+∞,

si n = 0 ∧ q > 0;

S (q, n) =

 mı́n k S (q − d · vn−1 , n − 1) + d · wn−1 , si n > 0.
0≤d ≤ j q

vn − 1

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 47 / 92

4. Obtención de ecuaciones recursivas
4.1. El problema del cambio generalizado - Obtener los casos base

El caso base lo tendremos cuando n llegue a 0 y no podamos continuar las

llamadas recursivas.

Tras llegar al caso base, deberemos comprobar el valor del resto de

parámetros de S, en nuestro caso, la cantidad q:

Si q = 0 estaremos en S (0, 0), que debe obtener el peso de la mejor

solución que no devuelve nada y no usa ninguna moneda, es decir, 0.
Si q > 0 estaremos en S (q, 0), que debe obtener el peso de la mejor
solución que devuelve q sin usar ninguna moneda. Este problema no
tiene solución y debemos devolver el elemento neutro de nuestro
operador mı́n, es decir, +∞.

Por lo tanto, tenemos dos casos base: n = 0 ∧ q = 0 y n = 0 ∧ q > 0.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 48 / 92

4. Obtención de ecuaciones recursivas
4.1. El problema del cambio generalizado - Costes

Las versiones recursiva e iterativa (ambas con recup. de camino)

tienen los mismos costes:
Espacial: O (Q N ). Coincide con el coste espacial del diccionario mem.
Temporal: O (Q 2 N ). Coincide con el coste de rellenar el diccionario
mem, pues calcular cada valor tiene un coste O (Q ).

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 49 / 92

4. Obtención de ecuaciones recursivas
4.2. El problema del cambio generalizado (X alternativo)

Ahora nuestras soluciones son una lista, de longitud variable, de

índices de moneda:

( )
k
XQ = (x0 , x1 , . . . , xk ) ∈ {0, 1, . . . , N − 1} ∗
∑ vx i =Q
i =0

La nueva función objetivo:

k
f (x0 , x1 , . . . , xk ) = ∑ wx


i
i =0

La solución óptima es la solución de menor peso:

k
xb = arg mín f (x ) =
x ∈XQ
arg mín ∑ wx i
(x0 ,x1 ,...,xk )∈XQ i =0

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 50 / 92

4.2. El problema del cambio generalizado (X alternativo)
Pasos para la obtención de la ecuación recursiva (I)

1. Como antes, partimos de la puntuación de la solución óptima, s[

core:

k
core =
s[ mı́n ∑ wxi
(x0 ,x1 ,...,xk )∈XQ i =0

2. Minimizamos por separado el último elemento del sumatorio, xk :

!
k
core =
s[ mı́n
0≤xk <|v |:
mı́n ∑ wxi
(x0 ,...,xk −1 )∈XQ −vx i =0
k
Q −vxk ≥0

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 51 / 92

4.2. El problema del cambio generalizado (X alternativo)
Pasos para la obtención de la ecuación recursiva (II)

3. Sacamos el último término del sumatorio

! !
k −1
core =
s[ mı́n
0≤xk <|v |:
mı́n ∑ wxi
(x0 ,...,xk −1 )∈XQ −vx i =0
+ wxk
k
Q −vxk ≥0

La recursividad ya puede apreciarse en la minimización interior,

comparándola con la minimización del paso 1.
La nueva minimización tiene una decisión menos que la del paso 1.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 52 / 92

4.2. El problema del cambio generalizado (X alternativo)
Pasos para la obtención de la ecuación recursiva (III)

4. Definimos una función capaz de representar ambas minimizaciones:

k′
S (q ) = mı́n ∑ wxi
(x0 ,x1 ,...,xk ′ )∈Xq i =0

5. Reescribimos las ecuaciones de los pasos 1 y 3 con esta nueva función:

core = S (Q )
s[
mı́n


core =
s[ S (Q − vxk ) + wxk
0≤xk <|v |:
Q −vxk ≥0

Por lo tanto:
mı́n


S (Q ) = S (Q − vxk ) + wxk
0≤xk <|v |:
Q −vxk ≥0

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 53 / 92

4.2. El problema del cambio generalizado (X alternativo)
Pasos para la obtención de la ecuación recursiva (y IV)

6. La función S será nuestra función recursiva, que generalizamos para

cualquier valor q:

S (q ) = mı́n


S (q − vxk ) + wxk
0≤xk <|v |:
q −vxk ≥0

7. Renombramos xk como d (de decisión):

mı́n


S (q ) = S ( q − vd ) + w d
0≤d <|v |:
q −vd ≥0

8. Por último, añadimos los casos base:


0,
 si q = 0;
+∞,

si q > 0 ∧ mı́n(v ) > q;
S (q ) =


 mı́n S (q − vd ) + wd , si q > 0 ∧ mı́n(v ) ≤ q.
0≤d <|v |:

q −vd ≥0

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 54 / 92

4. Obtención de ecuaciones recursivas
4.2. El problema del cambio generalizado (X alternativo) - Costes

Las versiones recursiva e iterativa (ambas con recup. de camino)

tienen los mismos costes:
Espacial: O (Q ). Coincide con el coste espacial del diccionario mem, que
ahora contiene Q elementos.
Temporal: O (Q N ). Coincide con el coste de rellenar el diccionario mem:
contiene Q elementos y calcular cada uno de ellos tiene un coste O (N ).

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 55 / 92

4. Obtención de ecuaciones recursivas
4.3. La plantilla de programación dinámica

S (□) = opt S (□′ ) ⊕ p (d )

d ∈⃝

opt: mı́n para minimización y máx para maximización.

□: Parámetros del problema actual.

□′ : Parámetros del problema previo, cuando la última decisión del

problema actual es d.

⃝: Conjunto de decisiones válidas.

p (d ): Puntuación de d, término de f correspondiente a d.

⊕: Combina la puntuación de d con la puntuación de □′ . Es el

“operador principal” de f .
Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 56 / 92
4.3. La plantilla de programación dinámica
Aplicación al problema del cambio generalizado (I)

Formalización: ( )
N −1
XQ,N = (x0 , x1 , . . . , xN −1 ) ∈ N N
∑ xi vi = Q
i =0

N −1
f (x0 , x1 , . . . , xN −1 ) = ∑ xi wi
i =0

S (□) = opt S (□′ ) ⊕ p (d )

d ∈⃝

opt = mı́n ⃝ = {0, 1, . . . , ⌊q/vn−1 ⌋}

□ = q, n p ( d ) = d · wn − 1
□ ′ = q − d · vn − 1 , n − 1 ⊕=+

Ecuación recursiva:
S (q, n) = mı́n
j k (S (q − d · vn−1 , n − 1) + d · wn−1 )
q
0≤d ≤ vn − 1

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 57 / 92

4.3. La plantilla de programación dinámica
Aplicación al problema del cambio generalizado (y II)

Para terminar, añadimos los casos base de la recursión:



 0, si n = 0 ∧ q = 0;
+∞,

si n = 0 ∧ q > 0;

S (q, n) =

 mı́n k S (q − d · vn−1 , n − 1) + d · wn−1 , si n > 0.
0≤d ≤ j q

vn − 1

donde:
En el caso base posible usamos el neutro de ⊕ (en este caso 0).
En el caso base imposible usamos el neutro de opt (en este caso +∞).

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 58 / 92

4.3. La plantilla de programación dinámica
Ejercicio

Dada la formulación alternativa para el problema del cambio

generalizado presentada en el apartado 4.2 y resumida aquí:
( )
k
XQ = (x0 , x1 , . . . , xk ) ∈ {0, 1, . . . , N − 1}∗ ∑ vx i =Q
i =0
k
f (x0 , x1 , . . . , xk ) = ∑ wx


i
i =0
core = mı́n f (x )
s[
x ∈XQ

utiliza la plantilla de PD para obtener la ecuación recursiva.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 59 / 92

Tema 7
Programación dinámica

1. Introducción

2. El problema del cambio generalizado

3. Implementación de ecuaciones recursivas

4. Obtención de ecuaciones recursivas

5. Ejemplos
5.1 El problema de la mochila
5.2 Asignación óptima de recursos
5.3 Problema del cambio con limitación en el nº de monedas
5.4 Camino más corto en un digrafo ponderado acíclico
5.5 Segmentación de un texto en palabras
5.6 Distancia de edición entre cadenas

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 60 / 92

5. Ejemplos
5.1. El problema de la mochila

El conjunto de soluciones (contiene todas las soluciones):

( )
N −1
XC ,N = (x0 , x1 , . . . , xN −1 ) ∈ {0, 1} N
∑ xi wi ≤ C
i =0

La función objetivo (puntúa soluciones):

N −1
f (x0 , x1 , . . . , xN −1 ) = ∑ xi vi
i =0

La puntuación de la mejor solución:

N −1
core = máx f (x ) =
s[
x ∈XC ,N
máx ∑
(x0 ,x1 ,...,xN −1 )∈XC ,N i =0
xi vi

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 61 / 92

5.1. El problema de la mochila
Aplicación de la plantilla de PD (I)

Formalización: ( )
N −1
XC ,N = (x0 , x1 , . . . , xN −1 ) ∈ {0, 1} N
∑ xi w i ≤ C
i =0

N −1
f (x0 , x1 , . . . , xN −1 ) = ∑ xi vi
i =0

S (□) = opt S (□′ ) ⊕ p (d )

d ∈⃝

opt = máx ⃝ = {0, 1}

□ = c, n p ( d ) = d · vn − 1
□′ = c − d · wn−1 , n − 1 ⊕=+

Ecuación recursiva:
S (c, n) = máx (S (c − d · wn−1 , n − 1) + d · vn−1 )
d ∈{0,1}

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 62 / 92

5.1. El problema de la mochila
Aplicación de la plantilla de PD (y II)

Simplificamos el máx:

S (c, n) = máx (S (c − d · wn−1 , n − 1) + d · vn−1 )

d ∈{0,1}

= máx S (c, n − 1), S (c − wn−1 , n − 1) + vn−1

Y añadimos los casos base de la recursión:


0,
 si n = 0;
S (c, n) = S (c, n − 1), si n > 0 ∧ wn−1 > c;


máx S (c, n − 1), S (c − wn−1 , n − 1) + vn−1 , si n > 0 ∧ wn−1 ≤ c.


Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 63 / 92

5.1. El problema de la mochila
Costes

La versión recursiva con recuperación de camino y la iterativa tienen

los mismos costes:
Espacial: O (C N ). Coincide con el coste espacial del diccionario mem.
Temporal: O (C N ). Coincide con el coste de rellenar el diccionario mem,
pues calcular cada valor tiene un coste O (1).

La versión iterativa con reducción del coste espacial lo reduce a O (C ).

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 64 / 92

5. Ejemplos
5.2. Asignación óptima de recursos

Disponemos de U unidades de un recurso y deseamos asignar cierta

cantidad del mismo a cada una de N actividades distintas.

El número de unidades del recurso que podemos asignar a una

actividad i debe ser inferior o igual a mi .

Se nos proporciona una función, v , que nos indica el beneficio que

obtenemos al asignar u unidades del recurso a la actividad i-ésima:
v (u, i ).

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 65 / 92

5.2. Asignación óptima de recursos
Formalización

Conjunto de soluciones (todas las asignaciones válidas):

( )
N −1
XU,N = (x0 , x1 , . . . , xN −1 ) ∈ NN
∑ xi ≤ U ∧ 0 ≤ xi ≤ mi , ∀0 ≤ i < N
i =0

Función objetivo (el beneficio de una asignación concreta):

N −1
f (x0 , x1 , . . . , xN −1 ) = ∑ v (xi , i )
i =0

La puntuación (beneficio) de la mejor asignación de recursos:

N −1
core =
s[ máx ∑
(x0 ,x1 ,...,xN −1 )∈XU,N i =0
v (xi , i )

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 66 / 92

5.2. Asignación óptima de recursos
Aplicación de la plantilla de PD (I)

Formalización:
( )
N −1
XU,N = (x0 , x1 , . . . , xN −1 ) ∈ NN
∑ xi ≤ U ∧ 0 ≤ xi ≤ mi , ∀0 ≤ i < N
i =0

N −1
f (x0 , x1 , . . . , xN −1 ) = ∑ v (xi , i )
i =0

S (□) = opt S (□′ ) ⊕ p (d )

d ∈⃝

opt = máx ⃝ = {0, 1, . . . , mı́n(mn−1 , u )}

□ = u, n p (d ) = v (d, n − 1)
□′ = u − d, n − 1 ⊕=+

Ecuación recursiva:
S (u, n) = máx (S (u − d, n − 1) + v (d, n − 1))
0≤d ≤mı́n(mn−1 ,u )

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 67 / 92

5.2. Asignación óptima de recursos
Aplicación de la plantilla de PD (y II))

Para terminar, añadimos el caso base de la recursión:


0, si n = 0;
S (u, n) = máx (S (u − d, n − 1) + v (d, n − 1)) , si n > 0.

0≤d ≤mı́n(mn−1 ,u )

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 68 / 92

5.2. Asignación óptima de recursos
Costes

La versión recursiva con recuperación de camino y la iterativa tienen

los mismos costes:
Espacial: O (U N ). Coincide con el coste espacial del diccionario mem.
Temporal: O (U 2 N ). Coincide con el coste de rellenar el diccionario
mem, pues calcular cada valor tiene un coste O (U )

La versión iterativa con reducción del coste espacial lo reduce a O (U ).

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 69 / 92

5. Ejemplos
5.3. Problema del cambio con limitación en el nº de monedas

Quitamos el peso de las monedas y añadimos una cantidad máxima

para cada moneda, mi .
El conjunto de soluciones:
( )
N −1
XQ,N = (x0 , x1 , . . . , xN −1 ) ∈ NN
∑ xi vi = Q ∧ 0 ≤ xi ≤ mi , ∀0 ≤ i < N
i =0

Función objetivo (cuenta el nº de monedas):

N −1
f (x0 , x1 , . . . , xN −1 ) = ∑ xi
i =0

La puntuación (nº de monedas) de la mejor solución:

N −1
core = mı́n f (x ) =
s[
x ∈XQ,N
mı́n ∑
(x0 ,x1 ,...,xN −1 )∈XQ,N i =0
xi

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 70 / 92

5.3. Problema del cambio con limitación en el nº de monedas
Aplicación de la plantilla de PD (I)

Formalización:
( )
N −1
XQ,N = (x0 , x1 , . . . , xN −1 ) ∈ NN ∑ xi vi = Q ∧ 0 ≤ xi ≤ mi , ∀0 ≤ i < N
i =0

N −1
f (x0 , x1 , . . . , xN −1 ) = ∑ xi
i =0

S (□) = opt S (□′ ) ⊕ p (d )

d ∈⃝

opt = mı́n ⃝ = {0, 1, . . . , mı́n (⌊q/vn−1 ⌋ , mn−1 )}

□ = q, n p (d ) = d
□′ = q − d · vn−1 , n − 1 ⊕=+

Ecuación recursiva:
S (q, n) = mı́n
j k  (S (q − d · vn−1 , n − 1) + d )
q
0≤d ≤mı́n vn − 1 ,mn−1

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 71 / 92

5.3. Problema del cambio con limitación en el nº de monedas
Aplicación de la plantilla de PD (y II)

Para terminar, añadimos los casos base de la recursión:



 0, si n = 0 ∧ q = 0;
+∞,

si n = 0 ∧ q > 0;

S (q, n) =

 mı́n  (S (q − d · vn−1 , n − 1) + d ) , si n > 0.
0≤d ≤mı́nj q
 k
,mn−1
vn−1

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 72 / 92

5.3. Problema del cambio con limitación en el nº de monedas
Costes

Tiene los mismos costes que la versión sin limitación del nº de

monedas.
La versión recursiva con recuperación de camino y la iterativa tienen
los mismos costes:
Espacial: O (Q N ). Coincide con el coste espacial del diccionario mem.
Temporal: O (Q 2 N ). Coincide con el coste de rellenar el diccionario
mem, pues calcular cada valor tiene un coste O (Q ).

La versión iterativa con reducción del coste espacial lo reduce a O (Q ).

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 73 / 92

5. Ejemplos
5.4. Camino más corto en un digrafo ponderado acíclico

Dado un digrafo acíclico, G = (V , E ), una función de ponderación de

aristas, w , y un vértice inicial, I, queremos encontrar el camino más corto
hasta el vértice final, T .

El conjunto de soluciones (caminos válidos):

 
XT = (x0 , x1 , . . . , xk ) ∈ V + x0 = I ∧ xk = T ∧ (xi , xi +1 ) ∈ E , ∀0 ≤ i < k

La función objetivo (la suma de los pesos de las aristas del camino):

k −1
f ( x0 , x1 , . . . , xk ) = ∑ w ( xi , xi + 1 )
i =0

La puntuación (peso del camino) de la mejor solución:

k −1
core = mı́n f (x ) =
s[
x ∈XT
mı́n ∑ w (xi , xi +1 )
(x0 ,x1 ,...,xk )∈XT i =0

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 74 / 92

5.4. Camino más corto en un digrafo ponderado acíclico
Aplicación de la plantilla de PD (I)

Formalización:
 
XT = (x0 , x1 , . . . , xk ) ∈ V + x0 = I ∧ xk = T ∧ (xi , xi +1 ) ∈ E , ∀0 ≤ i < k

k −1
f (x0 , x1 , . . . , xk ) = ∑ w (xi , xi +1 )
i =0

S (□) = opt S (□′ ) ⊕ p (d )

d ∈⃝

opt = mı́n ⃝ = preds (t ) = {v ∈ V | (v , t ) ∈ E }

□=t p (d ) = w (d, t )
□′ = d ⊕=+

Ecuación recursiva:
S (t ) = mı́n (S (d ) + w (d, t ))
d ∈preds (t )

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 75 / 92

5.4. Camino más corto en un digrafo ponderado acíclico
Aplicación de la plantilla de PD (y II))

Para terminar, añadimos los casos base de la recursión:


0,
 si t = I;
S (t ) = +∞,

si t ̸= I y |preds (t )| = 0;
 mı́n (S (d ) + w (d, t )) , si t ̸= I y |preds (t )| > 0.


d ∈preds (t )

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 76 / 92

5.4. Camino más corto en un digrafo ponderado acíclico
Costes

La versión recursiva con recuperación de camino y la iterativa tienen

los mismos costes:
Espacial: O (|V |). Coincide con el coste espacial del diccionario mem.
Temporal: O (|V |2 ). Coincide con el coste de rellenar el diccionario
mem, pues calcular cada valor tiene un coste O (|V |).

Además, para este problema, la versión iterativa con reducción del

coste espacial, no reduce el coste espacial.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 77 / 92

5. Ejemplos
5.5. Segmentación de un texto en palabras

Tenemos una cadena t, de longitud N, formada por la concatenación,

sin espacios en blanco, de una o más palabras. Queremos averiguar la
secuencia de palabras más probable que componen la cadena.

Disponemos de una función, p (w ), que nos devuelve la probabilidad

de aparición de una palabra w en un texto.

Consideraremos que probabilidad de una secuencia de palabras es el

producto de la probabilidad de cada una de ellas.

Indicaremos la segmentación con índices (como el operador de corte

de Python):

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 78 / 92

5.5. Segmentación de un texto en palabras
Formalización

Conjunto de soluciones (todas las segmentaciones válidas):

 

 x0 = 0 ∧ 

XN = (x0 , x1 , . . . , xk ) ∈ {0, 1, . . . , N }+ xk = N ∧
 
∀0 ≤ i < k : xi < xi +1
 

Función objetivo (la probabilidad de una segmentación concreta):

k −1
f (x0 , x1 , . . . , xk ) = ∏ p (txi :xi +1 )
i =0

La puntuación (probabilidad) de la mejor segmentación:

k −1
core = máx f (x ) =
s[
x ∈XN
máx ∏ p (tx :x + )
(x0 ,x1 ,...,xk )∈XN i =0
i i 1

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 79 / 92

5.5. Segmentación de un texto en palabras
Aplicación de la plantilla de PD (I)

Formalización:
 

 x0 = 0 ∧ 

XN = (x0 , x1 , . . . , xk ) ∈ {0, 1, . . . , N }+ xk = N ∧
 
∀0 ≤ i < k : xi < xi +1
 

k −1
f (x0 , x1 , . . . , xk ) = ∏ p (txi :xi +1 )
i =0

S (□) = opt S (□′ ) ⊕ p (d )

d ∈⃝

opt = máx ⃝ = {0, 1, . . . , n − 1}

□=n p (d ) = p (td :n )
□′ = d ⊕=·

Ecuación recursiva:
máx


S (n ) = S (d ) · p (td :n )
0≤d ≤n −1
Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 80 / 92
5.5. Segmentación de un texto en palabras
Aplicación de la plantilla de PD (y II)

Para terminar, añadimos el caso base de la recursión:


1, si n = 0;
S (n ) =
 máx S (d ) · p (td :n ) , si n > 0.


0≤d ≤n −1

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 81 / 92

5.5. Segmentación de un texto en palabras
Costes

La versión recursiva con recuperación de camino y la iterativa tienen

los mismos costes:
Espacial: O (N ). Coincide con el coste espacial del diccionario mem.
Temporal: O (N 2 ). Coincide con el coste de rellenar el diccionario mem,
pues calcular cada valor tiene un coste O (N ).

Para este problema, la versión iterativa con reducción del coste

espacial, mantiene el coste espacial.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 82 / 92

5. Ejemplos
5.6. Distancia de edición entre cadenas

Levenstein definió una medida de disimilitud entre cadenas basada en

transformaciones de edición.
Una transformación de edición en una secuencia de operaciones de
edición. Hay tres operaciones de edición:
λ → c. Inserción de un carácter.
c → λ. Borrado de un carácter.
c → d. Sustitución de un carácter por otro.

Veamos una transformación óptima de ‘ejemplo’ en ‘campos’ en cinco

operaciones de edición:
e →c j →a e →λ l →λ λ →s
ejemplo ===⇒ cjemplo ==⇒ caemplo ===⇒ camplo ==⇒ campo ===⇒ campos

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 83 / 92

5.6. Distancia de edición entre cadenas
Formalización

Dadas dos cadenas, s y t, deseamos obtener D (s, t ), la ‘distancia’

que nos indica lo similares o distintas que son las dos cadenas.

Definimos el conjunto de soluciones, Xs,t como el conjunto de todas

las transformaciones de edición que transforman la cadena s en la
cadena t.

La función objetivo simplemente calcula la longitud de la

transformación de edición (el número de operaciones de edición).

Queremos averiguar la longitud de la transformación de edición más

corta.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 84 / 92

5.6. Distancia de edición entre cadenas
La idea principal

Para simplificar la notación, en vez de escribir D (s, t ) escribiremos

D (M, N ), donde M y N son las tallas de las cadenas s y t,
respectivamente.

Así podemos representar distancias entre prefijos de s y t.

La idea principal es calcular D (M, N ) a partir de sus prefijos:

D (M − 1, N ) + 1,
 borrado;
D (M, N ) = mı́n D (M, N − 1) + 1, inserción;

D (M − 1, N − 1) + δ(sm−1 , tn−1 ), sustitución;


donde (
0, si x = y ;
δ (x , y ) =
1, en otro caso.

Nos falta añadir los casos base y ya tendremos la ecuación recursiva.

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 85 / 92

5.6. Distancia de edición entre cadenas
La idea principal: una visión alternativa

Una visión alternativa para calcular la distancia es considerar que

vamos quitando caracteres, desde el final, a ambas cadenas, con estas
penalizaciones:
Si quitamos el último carácter de sólo una cadena: 1.
Si quitamos el último carácter de ambas cadenas: 0 si el carácter era el
mismo y 1 si era distinto.

Veamos un ejemplo, la distancia de costa a casa:


D (cost, casa) + 1,
 quitamos la ‘a’ de ‘costa’;
D (costa, casa) = mı́n D (costa, cas) + 1, quitamos la ‘a’ de ‘casa’;

D (cost, cas) + 0, quitamos ambas (y son iguales).


Y continuamos recursivamente hasta que ambas cadenas estén vacías.

Este visión alternativa genera la misma ecuación recursiva que la

anterior.
Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 86 / 92
5.6. Distancia de edición entre cadenas
La ecuación recursiva

La ecuación recursiva, con sus casos base, queda:


0,
 si m = 0 y n = 0;




 D (m − 1, n) + 1, si m > 0 y n = 0;

D (m, n − 1) + 1, si m = 0 y n > 0;
D (m, n) = 


 D (m − 1, n) + 1,

mı́n D (m, n − 1) + 1, , si m > 0 y n > 0;




 
D (m − 1, n − 1) + δ(sm−1 , tn−1 ),
 

La distancia buscada será el valor de D (M, N ).

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 87 / 92

5.6. Distancia de edición entre cadenas
Operaciones de edición para convertir ‘costa’ en ‘casa’

casa|costa casa|osta casa|sta casa|ta casa|a casa|

cas|costa cas|osta cas|sta cas|ta cas|a cas|

ca|costa ca|osta ca|sta ca|ta ca|a ca|

c|costa c|osta c|sta c|ta c|a c|

|costa |osta |sta |ta |a |

c o s t a

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 88 / 92

5.6. Distancia de edición entre cadenas
Grafo de dependencias para D (‘costa’, ‘casa’) = D (5, 4)

D(0,4) D(1,4) D(2,4) D(3,4) D(4,4) D(5,4)

D(0,3) D(1,3) D(2,3) D(3,3) D(4,3) D(5,3)

D(0,2) D(1,2) D(2,2) D(3,2) D(4,2) D(5,2)

D(0,1) D(1,1) D(2,1) D(3,1) D(4,1) D(5,1)

D(0,0) D(1,0) D(2,0) D(3,0) D(4,0) D(5,0)

c o s t a

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 89 / 92

5.6. Distancia de edición entre cadenas
Backpointers y scores almacenados en el diccionario mem

D(0,4) D(1,4) D(2,4) D(3,4) D(4,4) D(5,4)

4 3 3 2 2 2

D(0,3) D(1,3) D(2,3) D(3,3) D(4,3) D(5,3)

3 2 2 1 2 3

D(0,2) D(1,2) D(2,2) D(3,2) D(4,2) D(5,2)

2 1 1 2 3 3

D(0,1) D(1,1) D(2,1) D(3,1) D(4,1) D(5,1)

1 0 1 2 3 4

D(0,0) D(1,0) D(2,0) D(3,0) D(4,0) D(5,0)

0 1 2 3 4 5

c o s t a

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 90 / 92

5.6. Distancia de edición entre cadenas
Costes

La versión recursiva con recuperación de camino y la iterativa tienen

los mismos costes:
Espacial: O (M N ). Coincide con el coste espacial del diccionario mem.
Temporal: O (M N ). Coincide con el coste de rellenar el diccionario
mem, pues calcular cada valor tiene un coste O (1).

La versión iterativa con reducción del coste espacial lo reduce a

O (min(M, N )).

Algoritmia EI1022/MT1022 – © Universitat Jaume I de Castelló 2023 91 / 92

La asignatura termina aquí...

¡y ha sido un placer contárosla!