PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSP

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


Á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



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



¿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.


Á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



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.



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 =


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


Σ 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



nk

L R

Cij = mij + Ci,k-1 + Ck+1,j

[ ni, ni+1, ..., nk-1, nk, nk+1, ..., nj-1, nj ]

L R




Cij = mij + min ( Ci,k-1 + Ck+1,j )i < k < j

Cii = pi

La Matriz se llena por diagonales.


Σ (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?


Con m = j - i


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


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Á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.



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 =



1 2

4 3

1513 910

8208

10

5

9

12

6

Ejemplo:

g( 2 , Ø ) = 5

g( 3 , Ø ) = 6

g( 4 , Ø ) = 8



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



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



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



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



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



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



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



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



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 →

→

→

→



Σ 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


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)


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.)


REFERENCIAS

Guilles Brassard y Paul Bratley.

“Algorithmics: Theory and Practice”

Prentice Hall. 1988.

ISBN-13: 9780130232434


¿PREGUNTAS?


¡MUCHAS GRACIAS!

Documents

PROGRAMACIÓN DINÁMICA PARA ÁRBOLES DE BÚSQUEDA ÓPTIMOS Y TSP