Download Presentación de PowerPoint

Universidad Viña del Mar
Guía de Ejercicios 3: D&AA
30/9/2002
Materia: Programación dinámica y Backtracking, con Apuntes.
1) Para el problema de la mochila, se tienen, 5 objetos con pesos w=(1,2,5,6,7) y valores
v=(1,6,18,22,28). La capacidad máxima de la mochila es de 11. Usando las recurrencias,
definidas, calcule la matriz para encontrar el peso máximo. Qué objetos son incuídos?
2) Para el problema de costo mínimo en un grafo por etapas, cambie la recurrencia definida
hacia delante por una hacia “atrás”, de manera de calcular las etapas desde el origen al destino.
Pruebe su idea con el grafo:
12
7
2
8
1
9
8
5
3
7
5
4
-
7
9
6
6
13
Largo de la ruta más corta
Nodos de la uta óptima
Desarrolle un algoritmo para calcular el largo de la ruta óptima
Desarrolle un algoritmo para calcular la ruta más corta
3) Calcule el mínimo numero de multiplicaciones que deben realizarce para las siguientes
Matrices:
105 520 2030
302
A
B
C
D
Determine la asociación par llegar al óptimo de multiplicaciones.
4) Sea la matriz:
G  D0 
0 30 5
-- 0 20
15 5 0
15 -- 5
-5
10
0
-
Calcule la matriz de menores distancias con el algoritmo Floyd
-
Lleve una matriz P para poder reconstruir los caminos. Muestre sólo los caminos que se
redujeron
-
Dada la matriz P, construya un algoritmo que indique todo los caminos óptimos desde todo los
nodos a todo los nodos.
5) Tiene las siguientes claves y probabilidades de acceso. No se consideran probabilidades de no
acceso:
1 0.25
2 0.33
3 0.07
4 0.20
5 0.15
Para un árbol binario de búsqueda óptimo, calcule el número medio mínimo de comparaciones.
Construya el árbol.
C1  {1,2,3,4}, C2  {1,2,3}, C3  {1,3}
6) Si tiene un problema de backtracking con
Calcule el espacio de solución
Calcule la disposición de las variables, para generar el mayor espacio de búsqueda, su
cantidad
Calcule la disposición de las variables, para generar el menor espacio de búsqueda, su
cantidad
7) Para el problema de las reinas, mostrar el árbol de búsqueda para la primera solución en un
tablero de 5x5.
Cual es el espacio de búsqueda para este caso?. Cuál es el espacio de soluciones.
8) En el problema de suma de subconjuntos, para una representación variable, muestre el árbol
completo indicando los nodos soluciones, si n=4 , M=30, W=(1,5,25,29)
Usando una representación fija y el algoritmo con acotadores, resuelva para n=6, M=26, W=
(4,8,10,12,16,18), indicando cada nodo solución.
9) El grafo de la prgunta 2 con m=3 colores puede colorearse de cuantas formas distintas.?
Muestre el árbol y las soluciones.