Analisis y diseno de algoritmo

Problemas de Algoritmia Avanzada
Curso 2004–2005 25 de noviembre de 2004

Advertencia: todos los problemas descritos en este documento admiten diversas formas de ser resueltos, por lo que no debe suponerse que, necesariamente, otras formas de resolver el problema son incorrectas. En caso de duda, cons´ltese con los profesores de u la asignatura.

´ Indice
1. Programaci´n din´mica o a 2.Ramificaci´n y poda o 3. Simulaci´n o . Soluciones de los ejercicios 2 7 8 10

1

1.

Programaci´n din´mica o a

Ejercicio 1. Una empresa constructora desea subcontratar para las distintas tareas que hay que ejecutar (cada una de las cuales puede considerarse como una etapa del trabajo) a otras empresas. El coste de cada tarea depende de qu´ decisi´n se tom´ en la etapa anterior, de forma quelas tareas se e o o pueden representar como un grafo multietapa en el que los nodos se disponen en niveles (etapas) y las aristas van siempre de los nodos de una etapa a los nodos de la siguiente, tal y como se refleja en el ejemplo de la figura 1. Cada arista (x, y) tiene adem´s un coste asociado d(x, y). Escribe un algoritmo de a programaci´n din´mica para encontrar la secuencia ´ptima dedecisiones. o a o
a 3 S k=0 5 7 c b 4 8 6 e 5 6 d 2 1 F

3

k=2

k=2

k=3

Figura 1: Un ejemplo de grafo multietapa.

Ejercicio 2. Dada una secuencia finita de n´meros enteros estrictamente u positivos S = {a1 , a2 , ..., aN }, se desea extraer una subsecuencia tan larga como sea posible que sea no decreciente. Por ejemplo, si S = {7, 2, 6, 5, 6} las subsecuencias {2, 5, 6} y {2, 6, 6} son nodecrecientes y de longitud m´xia ma. Escribe un algoritmo recursivo y otro de programaci´n din´mica iteo a rativa para resolver este problema. Dibuja el ´rbol de llamadas que genera a la funci´n recursiva para los datos del ejemplo y marca aquellos nodos que o son calculados si se usa un almac´n para evitar repeticiones. Compara este e n´mero con el n´mero de c´lculos que hace el algoritmoiterativo. u u a Ejercicio 3. Un robot con dos brazos debe soldar una serie de puntos r1 , . . . , rN en un circuito. Aunque el orden de soldadura no puede cambiarse, puede elegirse qu´ brazo realizar´ la soldadura. Se quiere encontrar la e a

2

secuencia de movimientos que minimiza la longitud total de los desplazamientos realizados si inicialmente ambos brazos se encuentran en la posici´n o r0 ylas distancias son conocidas. d 0 1 2 3 1 100 100 63 2 89 100 60 3 45 63 60 4 61 108 36 50 r2 ◦ r4 ◦ ◦r3 r0 ◦ ◦r1

Figura 2: Un caso de circuito de soldadura.

Comprueba que la soluci´n voraz no es correcta para el ejemplo de la o figura 2. Escribe una funci´n de programaci´n din´mica recursiva que permita o o a resolver el problema y analiza su coste temporal en funci´n de N . o Dibuja el´rbol de llamadas recursivas que se genera para los datos del a ejemplo y escribe el resultado en cada nodo. Compara el n´mero de c´lculos con el de un esquema recursivo puro y u a con el de un esquema iterativo. Ejercicio 4. Escribe un programa monedas(M ) que calcule el n´mero m´ u ınimo de monedas necesarias para conseguir exactamente la cantidad M . Para ello, debemos utilizar un m´ximo de cimonedas de valor vi . Si no es posible a obtener la cantidad M , el programa escribir´ ∞. a denominaci´n o disponible v1 c1 v2 c2 . . . vN . . . cN

Ejercicio 5. El personal de la universidad est´ organizado jer´rquicamente a a como un ´rbol cuya ra´ ocupa el rector. Para el vino de honor de fin de curso a ız se quiere invitar al m´ximo posible de empleados de forma que no coincida a ning´n empleadocon su superior inmediato. Escribe un algoritmo de prograu maci´n din´mica para calcular el n´mero m´ximo f (x, a) de subordinados o a u a de la persona x a los que se puede invitar si x acude al ´gape (a = 1) o si a no acude (a = 0). Para ello, conocemos el conjunto s(x) de subordinados inmediatos de x (nodos del ´rbol cuyo padre es x). a

3

Ejercicio 6. Al volver de Polinesia, un...