Programación dinámica: Introducción
Recordemos el problema de la mochila: Se tienen n objetos
fraccionables y una mochila. El objeto i tiene peso pi y una
fracción xi (0=xi=1) del objeto i produce un beneficio
bixi. El objetivo es llenar la mochila, de capacidad C, de manera
que se maximice el beneficio. Una variante: la “mochila
0-1” xi sólo toma valores 0 ó 1, indicando
que el objeto se deja fuera o se mete en la mochila. Los pesos,
pi, y la capacidad son números naturales. Los beneficios,
bi, son reales no negativos.
Ejemplo: n=3 C=15 (b1,b2,b3)=(38,40,24) (p1,p2,p3)=(9,6,5)
Recordar la estrategia voraz: Tomar siempre el objeto que
proporcione mayor beneficio por unidad de peso. Se obtiene la
solución: (x1,x2,x3)=(0,1,1), con beneficio 64 Sin
embargo, la solución óptima es: (x1,x2,x3)=(1,1,0),
con beneficio 78 Por tanto, la estrategia voraz no calcula la
solución óptima del problema de la mochila 0-1.
Programación dinámica: Introducción
Técnica de programación dinámica Se emplea
típicamente para resolver problemas de
optimización. Permite resolver problemas mediante una
secuencia de decisiones. Como el esquema voraz A diferencia del
esquema voraz, se producen varias secuencias de decisiones y
sólamente al final se sabe cuál es la mejor de
ellas. Está basada en el principio de optimalidad de
Bellman: “Cualquier subsecuencia de decisiones de una
secuencia óptima de decisiones que resuelve un problema
también debe ser óptima respecto al subproblema que
resuelve.” Programación dinámica:
Introducción R. Bellman: Dynamic Programming, Princeton
University Press, 1957.
Supongamos que un problema se resuelve tras tomar un secuencia
d1, d2, …, dn de decisiones. Si hay d opciones posibles
para cada una de las decisiones, una técnica de fuerza
bruta exploraría un total de dn secuencias posibles de
decisiones (explosión combinatoria). La técnica de
programación dinámica evita explorar todas las
secuencias posibles por medio de la resolución de
subproblemas de tamaño creciente y almacenamiento en una
tabla de las soluciones óptimas de esos subproblemas para
facilitar la solución de los problemas más grandes.
Programación dinámica: Introducción
Sea mochila(k,l,P) el problema: El problema de la mochila 0-1 es
mochila(1,n,C). El problema de la mochila 0-1
Ecuación de recurrencia hacia adelante:
Si
es el beneficio (o ganancia total) de una
solución óptima de mochila(j,n,c), entonces
dependiendo de que el objeto j-ésimo entre o no en la
solución (nótese que sólo puede entrar si
c-pj=0). Además, El problema de la mochila 0-1 Ambas
ecuaciones permiten
calcular ,
que es el valor de una solución óptima de
mochila(1,n,C). (Nótese que la ecuación de
recurrencia es hacia adelante pero el cálculo se realiza
hacia atrás.) v g j ( c ) v g j ( c ) ? max v g j ? 1 ( c
) , v g j ? 1 ( c ? p j ) ? b j ? ? (Gp:) (Gp:) (Gp:) (Gp:) v
(Gp:) g (Gp:) n (Gp:) ? (Gp:) 1 (Gp:) ( (Gp:) c (Gp:) ) (Gp:) ?
(Gp:) 0 (Gp:) , (Gp:) (Gp:) para cualquier capacidad (Gp:)
c
Ecuación de recurrencia hacia atrás:
Si es
el beneficio (o ganancia total) de una solución
óptima de mochila(1,j,c), entonces dependiendo de que el
objeto j-ésimo entre o no en la solución
(nótese que sólo puede entrar si c-pj=0).
Además, El problema de la mochila 0-1 Ambas ecuaciones
permiten
calcular ,
que es el valor de una solución óptima de
mochila(1,n,C). (Ahora la recurrencia es hacia atrás pero
el cálculo se realiza hacia adelante.) (Gp:) (Gp:) (Gp:)
(Gp:) w (Gp:) g (Gp:) j (Gp:) ( (Gp:) c (Gp:) ) (Gp:) (Gp:) (Gp:)
(Gp:) w (Gp:) g (Gp:) j (Gp:) ( (Gp:) c (Gp:) ) (Gp:) ? (Gp:) max
(Gp:) w (Gp:) g (Gp:) j (Gp:) ? (Gp:) 1 (Gp:) ( (Gp:) c (Gp:) )
(Gp:) , (Gp:) (Gp:) w (Gp:) g (Gp:) j (Gp:) ? (Gp:) 1 (Gp:) (
(Gp:) c (Gp:) ? (Gp:) p (Gp:) j (Gp:) ) (Gp:) ? (Gp:) b (Gp:) j
(Gp:) ? (Gp:) ? (Gp:) (Gp:) (Gp:) (Gp:) w (Gp:) g (Gp:) 0 (Gp:) (
(Gp:) c (Gp:) ) (Gp:) ? (Gp:) 0 (Gp:) , (Gp:) (Gp:) para
cualquier capacidad (Gp:) c
Tanto la recurrencia hacia adelante como hacia atrás
permiten escribir un algoritmo recursivo de forma inmediata. El
problema de la mochila 0-1 función
mochila1(p,b:vector[1..n] de nat; C:nat) devuelve nat principio
devuelve g(n,C) fin función g(j,c:nat) devuelve nat
principio si j=0 entonces devuelve 0 sino si c < p[j] entonces
devuelve g(j-1,c) sino si g(j-1,c)=g(j-1,c-p[j])+b[j] entonces
devuelve g(j-1,c) sino devuelve g(j-1,c-p[j])+b[j] fsi fsi fsi
fin
Problema: ineficiencia Un problema de tamaño n se reduce a
dos subproblemas de tamaño (n-1). Cada uno de los dos
subproblemas se reduce a otros dos… Por tanto, se obtiene
un algoritmo exponencial. Sin embargo, el número total de
sub-problemas a resolver no es tan grande: La
función tiene
dos parámetros: el primero puede tomar n valores distintos
y el segundo, C valores. ¡Luego sólo hay nC
problemas diferentes! Por tanto, la solución recursiva
está generando y resolviendo el mismo problema muchas
veces. El problema de la mochila 0-1 (Gp:) (Gp:) (Gp:) (Gp:) w
(Gp:) g (Gp:) j (Gp:) ( (Gp:) c (Gp:) )
Para evitar la repetición de cálculos, las
soluciones de los subproblemas se deben almacenan en una tabla.
Matriz n?C cuyo elemento (j,c) almacena Para el ejemplo anterior:
n=3 C=15 (b1,b2,b3)=(38,40,24) (p1,p2,p3)=(9,6,5) El problema de
la mochila 0-1 (Gp:) (Gp:) (Gp:) (Gp:) w (Gp:) g (Gp:) j (Gp:) (
(Gp:) c (Gp:) ) (Gp:) (Gp:) (Gp:) (Gp:) w (Gp:) g (Gp:) j (Gp:) (
(Gp:) c (Gp:) ) (Gp:) ? (Gp:) max (Gp:) w (Gp:) g (Gp:) j (Gp:) ?
(Gp:) 1 (Gp:) ( (Gp:) c (Gp:) ) (Gp:) , (Gp:) (Gp:) w (Gp:) g
(Gp:) j (Gp:) ? (Gp:) 1 (Gp:) ( (Gp:) c (Gp:) ? (Gp:) p (Gp:) j
(Gp:) ) (Gp:) ? (Gp:) b (Gp:) j (Gp:) ? (Gp:) ?
El problema de la mochila 0-1 algoritmo mochila(ent
p,b:vect[1..n]de nat; ent Cap:nat; sal g:vect[0..n,0..Cap]de nat)
variables c,j:nat principio para c:=0 hasta Cap hacer g[0,c]:=0
fpara; para j:=1 hasta n hacer g[j,0]:=0 fpara; para j:=1 hasta n
hacer para c:=1 hasta Cap hacer si c < p[j] entonces
g[j,c]:=g[j-1,c] sino si g[j-1,c]=g[j-1,c-p[j]]+b[j] entonces
g[j,c]:=g[j-1,c] sino g[j,c]:=g[j-1,c-p[j]]+b[j] fsi fsi fpara
fpara fin
Cálculos posibles a partir de la tabla g: beneficio total:
g[n,Cap] los objetos metidos en la mochila: El problema de la
mochila 0-1 algoritmo objetos(ent p,b:vect[1..n]de nat; ent
Cap:nat; ent g:vect[0..n,0..Cap]de nat) principio test(n,Cap) fin
algoritmo test(ent j,c:nat) principio si j>0 entonces si c
g[j-1,c] entonces test(j-1,c-p[j]);
escribir('meter ',j) sino test(j-1,c) fsi fsi fsi fin
Consideraciones finales Cada componente de la tabla g se calcula
en tiempo constante, luego el coste de construcción de la
tabla es O(nC). El algoritmo test se ejecuta una vez por cada
valor de j, desde n descendiendo hasta 0, luego su coste es O(n).
Si C es muy grande, entonces esta solución no es buena. Si
los pesos pi o la capacidad C son reales, esta solución no
sirve. El problema de la mochila 0-1
Camino de coste mínimo en un grafo multietapa Grafo
multietapa: Un grafo multietapa G=(V,A) es un grafo dirigido en
el que se puede hacer una partición del conjunto V de
vértices en k (k=2) conjuntos distintos Vi, 1=i=k, tal que
todo arco del grafo (u,v) es tal que u?Vi y v?Vi+1 para
algún i, 1=i < k. Los conjuntos V1 y Vk tienen un solo
vértice que se llama vértice origen, o, y
vértice destino, d, respectivamente. Consideraremos grafos
etiquetados.Denotamos por c(u,v) el coste del arco (u,v). (Gp:)
10 (Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) 4 (Gp:) 5 (Gp:) 6 (Gp:) 7 (Gp:)
8 (Gp:) 9 (Gp:) 5 (Gp:) 7 (Gp:) 2 (Gp:) 3 (Gp:) 1 (Gp:) 4 (Gp:) 5
(Gp:) 9 (Gp:) 8 (Gp:) 11 (Gp:) 6 (Gp:) 4 (Gp:) 5 (Gp:) 9 (Gp:) 12
(Gp:) V1 (Gp:) V2 (Gp:) V3 (Gp:) V4 (Gp:) V5 (Gp:) o (Gp:)
d
El problema: Encontrar un camino de coste mínimo que vaya
de o a d. Todo camino de o a d tiene exactamente un
vértice en cada Vi, por eso se dice que cada Vi define una
etapa del grafo. (Gp:) 10 (Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) 4 (Gp:) 5
(Gp:) 6 (Gp:) 7 (Gp:) 8 (Gp:) 9 (Gp:) 5 (Gp:) 7 (Gp:) 2 (Gp:) 3
(Gp:) 1 (Gp:) 4 (Gp:) 5 (Gp:) 9 (Gp:) 8 (Gp:) 11 (Gp:) 6 (Gp:) 4
(Gp:) 5 (Gp:) 9 (Gp:) 12 (Gp:) V1 (Gp:) V2 (Gp:) V3 (Gp:) V4
(Gp:) V5 (Gp:) o (Gp:) d Camino de coste mínimo en un
grafo multietapa
Ejemplo de aplicación: Se tienen n unidades de un recurso
que deben asignarse a r proyectos. Si se asignan j, 0=j=n,
unidades al proyecto i se obtiene un beneficio Ni,j. El problema
es asignar el recurso a los r proyectos maximizando el beneficio
total. Camino de coste mínimo en un grafo multietapa
Formulación como grafo multietapa: Número de
etapas: r+1 La etapa i, 1=i=r, representa el proyecto i. Hay n+1
vértices vi,j, 0=j=n, en cada etapa i, 2=i=r. Las etapas 1
y r+1 tienen un vértice, o=v1,0 y d=vr+1,n,
respectivamente. El vértice vi,j, 2=i=r, representa el
estado en el que se asignan un total de j unidades del recurso a
los proyectos 1, 2, …, i-1. Los arcos son de la forma
(vi,j,vi+1,l) para todo j=l y 1=i < r. El arco (vi,j,vi+1,l),
j=l, tiene asignado un coste Ni,l-j que corresponde a asignar l-j
unidades del recurso al proyecto i, 1=i < r. Además hay
arcos de la forma (vr,j,vr+1,n), que tienen asignado un coste
Camino de coste mínimo en un grafo multietapa
Grafo resultante para r=3 y n=4. La asignación
óptima está definida por un camino de coste
máximo de o a d. Para convertirlo en un problema de camino
de coste mínimo basta cambiar los signos de las etiquetas.
Camino de coste mínimo en un grafo multietapa
Solución de programación dinámica: Cada
camino de o a d es el resultado de una secuencia de k-2
decisiones. Decisión i-ésima: determinar, a partir
de un vértice vi de Vi, un arco que tenga a vi como origen
y algún nodo de Vi+1 como destino. Principio de
optimalidad: El camino de coste mínimo debe contener
subcaminos de coste mínimo entre otros nodos. Dem.: En
otro caso, podrían sustituirse dichos subcaminos por otros
mejores, resultando un camino total de coste menor. Camino de
coste mínimo en un grafo multietapa (Gp:) 10 (Gp:) 1 (Gp:)
2 (Gp:) 3 (Gp:) 4 (Gp:) 5 (Gp:) 6 (Gp:) 7 (Gp:) 8 (Gp:) 9 (Gp:) 5
(Gp:) 7 (Gp:) 2 (Gp:) 3 (Gp:) 1 (Gp:) 4 (Gp:) 5 (Gp:) 9 (Gp:) 8
(Gp:) 11 (Gp:) 6 (Gp:) 4 (Gp:) 5 (Gp:) 9 (Gp:) 12 (Gp:) V1 (Gp:)
V2 (Gp:) V3 (Gp:) V4 (Gp:) V5 (Gp:) o (Gp:) d
Ecuación de recurrencia hacia adelante: Sea s(i,j) un
camino de coste mínimo C*(i,j) desde el vértice j
del conjunto Vi hasta el vértice destino d. Entonces:
Camino de coste mínimo en un grafo multietapa (Gp:) 10
(Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) 4 (Gp:) 5 (Gp:) 6 (Gp:) 7 (Gp:) 8
(Gp:) 9 (Gp:) 5 (Gp:) 7 (Gp:) 2 (Gp:) 3 (Gp:) 1 (Gp:) 4 (Gp:) 5
(Gp:) 9 (Gp:) 8 (Gp:) 11 (Gp:) 6 (Gp:) 4 (Gp:) 5 (Gp:) 9 (Gp:) 12
(Gp:) V1 (Gp:) V2 (Gp:) V3 (Gp:) V4 (Gp:) V5 (Gp:) o (Gp:)
d
Camino de coste mínimo en un grafo multietapa (Gp:) 10
(Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) 4 (Gp:) 5 (Gp:) 6 (Gp:) 7 (Gp:) 8
(Gp:) 9 (Gp:) 5 (Gp:) 7 (Gp:) 2 (Gp:) 3 (Gp:) 1 (Gp:) 4 (Gp:) 5
(Gp:) 9 (Gp:) 8 (Gp:) 11 (Gp:) 6 (Gp:) 4 (Gp:) 5 (Gp:) 9 (Gp:) 12
(Gp:) V1 (Gp:) V2 (Gp:) V3 (Gp:) V4 (Gp:) V5 (Gp:) o (Gp:)
d
Falta almacenar las decisiones hechas en cada etapa que minimizan
el coste: Sea D(i,j) el valor de l que minimiza Entonces el
camino de coste mínimo es: v1=1; v2=D(1,1);
v3=D(2,D(1,1)); etc. Camino de coste mínimo en un grafo
multietapa (Gp:) c (Gp:) ( (Gp:) j (Gp:) , (Gp:) l (Gp:) ) (Gp:)
? (Gp:) C (Gp:) ? (Gp:) ( (Gp:) i (Gp:) ? (Gp:) 1 (Gp:) , (Gp:) l
(Gp:) ). (Gp:) 10 (Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) 4 (Gp:) 5 (Gp:) 6
(Gp:) 7 (Gp:) 8 (Gp:) 9 (Gp:) 5 (Gp:) 7 (Gp:) 2 (Gp:) 3 (Gp:) 1
(Gp:) 4 (Gp:) 5 (Gp:) 9 (Gp:) 8 (Gp:) 11 (Gp:) 6 (Gp:) 4 (Gp:) 5
(Gp:) 9 (Gp:) 12 (Gp:) V1 (Gp:) V2 (Gp:) V3 (Gp:) V4 (Gp:) V5
(Gp:) o (Gp:) d
Camino de coste mínimo en un grafo multietapa algoritmo
multietapa(ent G=(V,A,c):grafo; ent k,n:nat; sal P:vect[1..k]de
1..n) {Los vértices están numerados de forma que
los índices de los vértices de una etapa son
mayores que los índices de los de la etapa anterior. El
primer índice de C* y D, que sólo identificaba la
etapa, se ha suprimido.} variables C:vect[1..n]de real;
D:vect[1..n]de 1..n; j,r:1..n principio C[n]:=0.0;
{Cálculo de C* y D} para j:=n-1 descendiendo hasta 1 hacer
r:=vértice t.q. (j,r)?A 3 c(j,r)+C[r] es mínimo;
C[j]:=c(j,r)+C[r]; D[j]:=r fpara; P[1]:=1; P[k]:=n;
{Construcción del camino} para j:=2 hasta k-1 hacer
P[j]:=D[P[j-1]] fpara fin
Coste del algoritmo: Si G está representado mediante
listas de adyacencia, entonces el cálculo de r en el
interior del primer bucle lleva un tiempo proporcional al grado
del vértice j. Por tanto, si a es el número de
arcos del grafo, el coste total del algoritmo es ?(n+a). (El
segundo bucle lleva un tiempo ?(k).) Camino de coste
mínimo en un grafo multietapa
Análogamente, se desarrolla la recurrencia hacia
atrás. Ecuación de recurrencia hacia atrás:
Sea s(i,j) un camino de coste mínimo C*(i,j) desde el
vértice origen o hasta el vértice j del conjunto
Vi. Entonces: Camino de coste mínimo en un grafo
multietapa (Gp:) 10 (Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) 4 (Gp:) 5 (Gp:)
6 (Gp:) 7 (Gp:) 8 (Gp:) 9 (Gp:) 5 (Gp:) 7 (Gp:) 2 (Gp:) 3 (Gp:) 1
(Gp:) 4 (Gp:) 5 (Gp:) 9 (Gp:) 8 (Gp:) 11 (Gp:) 6 (Gp:) 4 (Gp:) 5
(Gp:) 9 (Gp:) 12 (Gp:) V1 (Gp:) V2 (Gp:) V3 (Gp:) V4 (Gp:) V5
(Gp:) o (Gp:) d
Camino de coste mínimo en un grafo multietapa algoritmo
multietapaB(ent G=(V,A,c):grafo; ent k,n:nat; sal P:vect[1..k]de
1..n) {Los vértices están numerados de forma que
los índices de los vértices de una etapa son
mayores que los índices de los de la etapa anterior. El
primer índice de C* y D, que sólo identificaba la
etapa, se ha suprimido.} variables C:vect[1..n]de real;
D:vect[1..n]de 1..n; j,r:1..n principio C[1]:=0.0;
{Cálculo de C* y D} para j:=2 hasta n hacer
r:=vértice t.q. (r,j)?A 3 c(r,j)+C[r] es mínimo;
C[j]:=c(r,j)+C[r]; D[j]:=r fpara; P[1]:=1; P[k]:=n;
{Construcción del camino} para j:=k-1 descendiendo hasta 2
hacer P[j]:=D[P[j+1]] fpara fin Nota: La eficiencia es la misma
si G está representado mediante listas de adyacencia
inversa.
Multiplicación de una secuencia de matrices Se desea
calcular el producto matricial: Como es asociativo, existen
varias formas… (Recordar que el algortimo resultante de la
definición del producto de dos matrices p?q y q?r necesita
pqr multiplicaciones de escalares.) Ejemplo: se quiere calcular
el producto ABCD, de las matrices A(13?5), B(5?89), C(89?3) y
D(3?34). ¡El caso más eficiente es casi 19 veces
más rápido que el más lento! (Gp:) (Gp:)
(Gp:) n (Gp:) º (Gp:) multip. (Gp:) ( (Gp:) ( (Gp:) AB (Gp:)
) (Gp:) C (Gp:) ) (Gp:) D (Gp:) ) (Gp:) 10582 (Gp:) ( (Gp:) AB
(Gp:) ) (Gp:) ( (Gp:) CD (Gp:) ) (Gp:) 54201 (Gp:) ( (Gp:) A
(Gp:) ( (Gp:) BC (Gp:) ) (Gp:) ) (Gp:) D (Gp:) 2856 (Gp:) A (Gp:)
( (Gp:) ( (Gp:) BC (Gp:) ) (Gp:) D (Gp:) ) (Gp:) 4055 (Gp:) A
(Gp:) ( (Gp:) B (Gp:) ( (Gp:) CD (Gp:) ) (Gp:) ) (Gp:)
26418
¿Cómo hallar el mejor método? 1. Insertar
los paréntesis de todas las formas posibles
(significativamente diferentes). 2. Calcular para cada una el
número de multiplicaciones escalares requeridas.
¿Cuántas formas posibles T(n) de insertar
paréntesis existen en un producto de n matrices? Si
cortamos entre la i y la (i+1)-ésima: Entonces tenemos
T(i)T(n-i) formas distintas. Como i puede tomar valores entre 1 y
n-1: Números de Catalan Multiplicación de una
secuencia de matrices
Los números de Catalan crecen exponencialmente. De hecho
puede demostrarse que: Por ejemplo: Luego el método
directo no sirve. Multiplicación de una secuencia de
matrices
Aplicación del principio de optimalidad: Si el mejor modo
de realizar el producto exige dividir inicialmente entre las
matrices i e (i+1)-ésima, los productos deberán ser
realizados de forma óptima para que el total
también sea óptimo. Método: Construir la
matriz [mij], 1=i=j=n, donde mij da el óptimo (i.e., el
número de multiplicaciones escalares requeridas) para la
partedel producto total. La solución final vendrá
dada por m1n. Multiplicación de una secuencia de matrices
S. Godbole: “On efficient computation of matrix chain
products”, IEEE Transactions on Computers, 22(9), pp.
864-866, 1973.
Construcción de [mij], 1=i=j=n: Guardar las dimensiones de
las Mi, 1=i=n, en un vector d, de 0..n componentes, de forma que
Mi tiene dimensiones di-1?di. La diagonal s de [mij] contiene los
mij tales que j-i=s: El tercer caso representa que para
calcular se
intentan todas las posibilidadesy se escoge la mejor. De forma
más compacta: Multiplicación de una secuencia de
matrices
Para el ejemplo anterior: A(13?5), B(5?89), C(89?3) y D(3?34) Se
tiene d=(13,5,89,3,34). Para s=1: m12=5785, m23=1335, m34=9078.
Para s=2: Para s=3: La matriz es: Multiplicación de una
secuencia de matrices
Solución recursiva inmediata: Aplicación de la
ecuación recurrente. Problema: complejidad exponencial.
Almacenamiento de las soluciones de los subproblemas en una
tabla: Número de subproblemas: ?(n2).
Multiplicación de una secuencia de matrices
Multiplicación de una secuencia de matrices algoritmo
parentOpt(ent d:vect[0..n]de nat; sal m:vect[1..n,1..n]de nat;
sal km:vect[1..n,1..n]de 1..n) {m es la matriz [mij] definida
antes; km[i,j] guarda el índice k para el que se alcanza
el mínimo al calcular m[i,j].} variables i,r,j,k,q:nat;
principio para i:=1 hasta n hacer m[i,i]:=0 fpara; para r:=2
hasta n hacer para i:=1 hasta n-r+1 hacer j:=i+r-1; m[i,j]:=8;
para k:=i hasta j-1 hacer q:=m[i,k]+m[k+1,j]+d[i-1]*d[k]*d[j]; si
q < m[i,j] entonces m[i,j]:=q; km[i,j]:=k fsi fpara fpara
fpara fin
Coste en tiempo: ?(n3) Coste en memoria: ?(n2)
Multiplicación de una secuencia de matrices
¡Falta hacer el producto! El elemento km[i,j] guarda el
valor de ktal que la división óptima de
parte el producto entre Mk y Mk+1. Por
tanto: Multiplicación de una secuencia de matrices
función multSec(M:vect[1..n]de matriz;
km:vect[1..n,1..n]de 1..n; i,j:1..n) devuelve matriz variables
X,Y:matriz principio si j>i entonces
X:=multSec(M,km,i,km[i,j]); Y:=multSec(M,km,km[i,j]+1,j];
devuelve mult(X,Y) sino devuelve M[i] fsi fin
Caminos mínimos entre todos los pares de nodos de un grafo
Problema: Cálculo de los caminos de coste mínimo
entre todos los pares de vértices de un grafo dirigido sin
ciclos de peso negativo. Principio de optimalidad: Si i1, i2,
…, ik, ik+1, …, in es un camino de coste
mínimo de i1 a in, entonces: i1, i2, …, ik es un
camino de coste mínimo de i1 a ik, y ik, ik+1, …,
in es un camino de coste mínimo de ik a in.
Aplicación del principio: Si k es el vértice
intermedio de mayor índice en el camino óptimo de i
a j, entonces el subcamino de i a k es un camino óptimo de
i a k que, además, sólo pasa por vértices de
índice menor que k. Lo análogo ocurre con el
subcamino de k a j. R.W. Floyd: “Algorithm 97: Shortest
path”, Communications of the ACM, 5(6), p. 345, 1962.
Sea C(i,j) el coste de la arista (i,j) o infinito si esa arista
no existe. Sea C(i,i)=0. Sea Dk(i,j) la longitud (o distancia)
del camino de coste mínimo de i a j que no pasa por
ningún vértice de índice mayor que k. Sea
D(i,j) la longitud del camino de coste mínimo de i a j.
Entonces: Ahora, un camino óptimo de i a j que no pase por
ningún vértice de índice mayor que k bien
pasa por el vértice k ó no. Si pasa por k entonces:
Si no pasa por k entonces ningún vértice intermedio
tiene índice superior a k-1: Caminos mínimos entre
todos los pares de nodos de un grafo
En resumen: Se tiene la siguiente ecuación recurrente que
define el método de programación dinámica.
Caminos mínimos entre todos los pares de nodos de un
grafo
ESTA PRESENTACIÓN CONTIENE MAS DIAPOSITIVAS DISPONIBLES EN
LA VERSIÓN DE DESCARGA