PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE
BÚSQUEDA ÓPTIMOS Y TSP
Universidad Simón Bolívar (Sede de Sartenejas)
Programa de Maestría en Ciencias de la Computación
CI-7621 (Teoría de Algoritmos)
Expositor: Ricardo Monascal
Profesor: Oscar Meza
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
Contenido
→ Árboles de Búsqueda
→ Árboles de Búsqueda Óptimos
→ Programación Dinámica (Árboles de Búsqueda Óptimos)
→ TSP (Travelling Salesman Problem)
→ Programación Dinámica (Travelling Salesman Problem)
→ Conclusiones
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
ÁRBOLES DE BÚSQUEDA
Un árbol de búsqueda es un árbol binario que cumple la siguiente condición:
Para cada nodo x:
Todos los nodos de su hijo izquierdo deben ser menores o iguales que la clave de x.
Todos los nodos de su hijo derecho deben ser mayores que la clave de x.
5
3
1 4
6
8
7
5
3
1 4
6
8
7
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
ÁRBOLES DE BÚSQUEDA
4
3
1 5
7
86
5
3
1 4
7
86
5
3
1 4
7
864
3
1 5
7
86
5
3
1 4
6
8
7
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
ÁRBOLES DE BÚSQUEDA
¿Cuántas comparaciones hacen falta (en promedio) para conseguir un elemento en un árbol de búsqueda?
5
3
1 4
7
86
Clave 5: 1 comparación
Claves 3 y 7: 2 comparaciones
Claves 1, 4, 6 y 8: 3 comparaciones
En general:
Para un nodo de profundidad di, la cantidad de comparaciones necesarias
para encontrar dicho nodo es di + 1.
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
ÁRBOLES DE BÚSQUEDA ÓPTIMOS
Considerando que cada clave tiene la misma probabilidad de ser buscada en el árbol. ¿Qué configuración proporciona el mínimo número promedio de comparaciones necesarias?
¿Cuántas comparaciones hacen falta (en promedio) para conseguir un elemento en el siguiente árbol de búsqueda?
5
3
1 4
7
86
(1 + 2 + 2 + 3 + 3 + 3 + 3) / 8
=
17 / 8
=
2.125
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
ÁRBOLES DE BÚSQUEDA ÓPTIMOS
Considerando ahora que cada clave tiene probabilidad pi de ser buscada en el árbol.
¿Qué configuración proporciona el mínimo número promedio de comparaciones necesarias?
A este problema se le conoce como: Hallar el árbol de búsqueda óptimo para un conjunto determinado de claves.
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
ÁRBOLES DE BÚSQUEDA ÓPTIMOS
Supondremos la condición de que todas las claves, en efecto se encuentran en el árbol:
Siendo así, la cantidad promedio de comparaciones necesarias, para una configuración dada, viene dada por:
Σ pi = 1i = 1
n
Σ pi (di + 1)i = 1
n
C =
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
nk
L R
[ ni, ni+1, ..., nk-1, nk, nk+1, ..., nj-1, nj ]
L R
PROGRAMACIÓN DINÁMICAÁRBOLES DE BÚSQUEDA ÓPTIMOS
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
Σ pk
k = i
j
mij =
Ejemplo:
i 1 2 3 4 5pi 0.30 0.05 0.08 0.45 0.12
0.30 0.35 0.43 0.88 1.00
0.05 0.13 0.58 0.70
m = 0.08 0.53 0.65
0.45 0.57
0.12
PROGRAMACIÓN DINÁMICAÁRBOLES DE BÚSQUEDA ÓPTIMOS
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
nk
L R
Cij = mij + Ci,k-1 + Ck+1,j
[ ni, ni+1, ..., nk-1, nk, nk+1, ..., nj-1, nj ]
L R
PROGRAMACIÓN DINÁMICAÁRBOLES DE BÚSQUEDA ÓPTIMOS
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICAÁRBOLES DE BÚSQUEDA ÓPTIMOS
Cij = mij + min ( Ci,k-1 + Ck+1,j )i < k < j
Cii = pi
La Matriz se llena por diagonales.
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
Σ (n - m) (m + 1) = n3
m = 1
n-1
T(n) = Θ( ) Θ( )
¿Qué ocurriría si se admitiera la búsqueda de claves que no se encuentren en el árbol?
PROGRAMACIÓN DINÁMICAÁRBOLES DE BÚSQUEDA ÓPTIMOS
Con m = j - i
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
TSPTRAVELLING SALESMAN PROBLEM
Dado un grafo G = (V, E) y una función de costo C : E → R+
Se desea conseguir un circuito (un camino que empieza y termina en el mismo nodo), de costo mínimo, tal que dicho circuito pase por cada nodo exactamente una vez.
1 2
4 3
1513 910
8208
10
5
9
12
6
Circuito óptimo:
C = 1 → 2 → 4 → 3 → 1
Costo (C) = 10 + 10 + 9 + 6 = 35
1 2
4 3
1513 910
8208
10
5
9
12
6
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
TSPTRAVELLING SALESMAN PROBLEM
1 2 4 3 110 10 9 6
También es óptimo
Sea g (i , S) el costo de un camino óptimo que empiece en el nodo i y termine en el nodo 1, pasando exactamente una vez por cada nodo en S.
g( 1 , V / { 1 } ) = min ( C1j + g ( j , V \ { 1, j } ) )2 < j < n
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICATRAVELLING SALESMAN PROBLEM
g( i , S ) = min ( Cij + g ( j , S \ { j } ) ) j S
g( i , Ø ) = Ci1
El algoritmo entonces puede averiguar los valores para g, cuando S = Ø.
Luego, puede usar esa información para averiguar los valores de g, cuando |S| = 1, luego cuando |S| = 2.
Y así en adelante hasta que S = V.
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICATRAVELLING SALESMAN PROBLEM
1 2
4 3
1513 910
8208
10
5
9
12
6
Ejemplo:
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
C =
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICATRAVELLING SALESMAN PROBLEM
1 2
4 3
1513 910
8208
10
5
9
12
6
Ejemplo:
g( 2 , Ø ) = 5
g( 3 , Ø ) = 6
g( 4 , Ø ) = 8
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICATRAVELLING SALESMAN PROBLEM
1 2
4 3
1513 910
8208
10
5
9
12
6
Ejemplo:
g( 2 , { 3 } ) = C23 + g( 3 , Ø ) = 15
g( 2 , { 4 } ) = C24 + g( 4 , Ø ) = 18
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICATRAVELLING SALESMAN PROBLEM
1 2
4 3
1513 910
8208
10
5
9
12
6
Ejemplo:
g( 3 , { 2 } ) = C32 + g( 2 , Ø ) = 18
g( 3 , { 4 } ) = C34 + g( 4 , Ø ) = 20
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICATRAVELLING SALESMAN PROBLEM
1 2
4 3
1513 910
8208
10
5
9
12
6
Ejemplo:
g( 4 , { 2 } ) = C42 + g( 2 , Ø ) = 13
g( 4 , { 3 } ) = C43 + g( 3 , Ø ) = 15
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICATRAVELLING SALESMAN PROBLEM
1 2
4 3
1513 910
8208
10
5
9
12
6
Ejemplo:
g( 2 , { 3 , 4 } )
=
C23 + g( 3 , { 4 } )
C24 + g( 4 , { 3 } )
=
25
min
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICATRAVELLING SALESMAN PROBLEM
1 2
4 3
1513 910
8208
10
5
9
12
6
Ejemplo:
g( 3 , { 2 , 4 } )
=
C32 + g( 2 , { 4 } )
C34 + g( 4 , { 2 } )
=
25
min
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICATRAVELLING SALESMAN PROBLEM
1 2
4 3
1513 910
8208
10
5
9
12
6
Ejemplo:
g( 4 , { 2 , 3 } )
=
C42 + g( 2 , { 3 } )
C43 + g( 3 , { 2 } )
=
23
min
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICATRAVELLING SALESMAN PROBLEM
Ejemplo:
g( 1 , { 2 , 3 , 4 } )
=
C12 + g( 2 , { 3 , 4 } )
C13 + g( 3 , { 2 , 4 } )
C14 + g( 4 , { 2 , 3 } )
=
35
min
1 2
4 3
1513 910
8208
10
5
9
12
6
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICATRAVELLING SALESMAN PROBLEM
Nótese que hasta ahora se ha asumido que g (i , S) se calcula una sola vez, y luego es reutilizado cada vez que haga falta.
Sin embargo, S es un conjunto, por lo tanto hay que escoger alguna estructura de datos conveniente para representarlo.
Una posible representación podría ser una codificación binaria de los elementos en S, con respecto a V.
Por ejemplo:
V = { 1 , 2 , 3 , 4 }
S = { 2 , 4 }
{ 2 , 4 } 0 1 0 1S = = 5
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICATRAVELLING SALESMAN PROBLEM
Para reconstruir el circuito de costo mínimo, se puede tener otro espacio de memoria J ( i , S ), tal que contenga el j
escogido cuando de calculaba g ( i , S ).
1 2
4 3
1513 910
8208
10
5
9
12
6
J ( 1 , { 2 , 3 , 4 } ) = 2
J ( 2 , { 3 , 4 } ) = 4
J ( 4 , { 3 } ) = 3
1
1 →
→
→
→
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
PROGRAMACIÓN DINÁMICATRAVELLING SALESMAN PROBLEM
Σ 2 (n - 1) + (n - 1) k = n2 2n
k = 1
n-2
T(n) = Θ( ) Θ( )n – 2 k
n
Tiempo:
Método directo
Θ( n! )
Tiempo:
Prog. Dinámica
Θ( n2 2n )
Espacio:
Prog. Dinámica
Θ( n 2n )
5 120 800 160
10 3,628,800 102,400 10,240
15 1,31x1012 7,372,800 491,520
20 2,43x1018 419,430,400 20,971,520
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
CONCLUSIONES
Nuevamente la técnica de programación dinámica nos proporciona una forma viable de tratar
problemas que parecen difíciles.
En el caso de lo árboles de búsqueda óptimos, nos proporcionó un algoritmo polinomial para su
resolución.
(Como nota aparte, puede verse la similitud de éste problema con el de la multiplicación encadenada de matrices)
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
CONCLUSIONES
En el caso de TSP, se obtuvo un algoritmo que, a pesar de seguir siendo de orden exponencial,
mejora por mucho el tiempo del método directo.
(Cuando existen 20 nodos en el grafo, la programación dinámica se tomará un poco menos de 7 minutos, mientras que el método directo
excederá los 77.000 años.)
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
REFERENCIAS
Guilles Brassard y Paul Bratley.
“Algorithmics: Theory and Practice”
Prentice Hall. 1988.
ISBN-13: 9780130232434
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
¿PREGUNTAS?
PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSPCI-7621 (Teoría de Algoritmos) Expositor: Ricardo Monascal
¡MUCHAS GRACIAS!