Algoritmos I (CAO302) Tema 04.
Técnicas Avanzadas de Programación
TÉCNICAS AVANZADAS DE PROGRAMACIÓN
Guía Práctica
Contenido Sinóptico
Algoritmos Greedy. Backtracking. Programación dinámica.
Algoritmos Greedy
1. Problema de retornar el cambio: Se dispone de un conjunto finito M = {m1, m2, …, mn} de tipos de
monedas, donde cada mi es un número natural que indica el valor de las monedas de tipo i, y se
cumple m1 < m2 < … < mn. Suponiendo que la cantidad de monedas de cada tipo es ilimitada, se
quiere retornar de forma exacta una cantidad C > 0 utilizando el menor número posible de monedas.
2. Realice una corrida en frio del algoritmo anterior para las siguientes instancias del problema:
a) C = 8 y M = {1, 5, 10}
b) C = 8 y M = {1, 4, 6}
c) C = 8 y M = {5, 10}
Indique que sucede en cada caso.
3. El algoritmo de Kruskal permite encontrar el árbol expandido de costo mínimo en un grafo pesado.
Realice este algoritmo bajo el esquema de algoritmos greedy.
4. El algoritmo de Dijkstra permite encontrar los caminos de costo mínimo entre un vértice inicial v y
todos los demás vértices del grafo. Realice este algoritmo bajo el esquema de algoritmos greedy.
Backtracking
5. Resuelva el problema de retornar el cambio con esta técnica. Indique el esquema a utilizar.
6. Problema de las n-reinas: Considere un tablero de ajedrez de n × n. Desarrolle un algoritmo que
permita colocar n reinas sobre el mismo sin que se ataquen. Tómese en cuenta que la reina se
mueve de manera horizontal, vertical y diagonal:
Universidad de Carabobo Facultad de Ciencias y Tecnología Departamento de Computación
Pag. 1
Algoritmos I (CAO302) Tema 04. Técnicas Avanzadas de Programación
7. Dado un grafo dirigido, encontrar:
a) Todos los caminos.
b) Un camino cualquiera.
c) El camino mínimo.
Entre dos vértices dados (vértice inicial y vértice final) de manera tal que los vértices contenidos
en cada camino sean visitados una sola vez.
8. Dado un laberinto, la casilla de entrada y la casilla de salida, encuentre:
a) Todos los caminos.
b) Un camino cualquiera.
c) El camino mínimo (el de menos movimientos).
Para salir del mismo.
9. Problema del caballo: Considere un tablero de ajedrez de n × n. Desarrolle un algoritmo que dada
la posición inicial de un caballo en un tablero de ajedrez, realice el recorrido por todas las casillas
del mismo una sola vez. Considere que el caballo solamente se mueve en forma de L:
Indique el esquema a utilizar.
10. Dado el tablero correspondiente a una configuración inicial de sudoku, encuentre su solución final.
11. Dado un grafo, realice un algoritmo que permita hallar un circuito hamiltoniano dentro del mismo.
Universidad de Carabobo Facultad de Ciencias y Tecnología Departamento de Computación
Pag. 2
Algoritmos I (CAO302) Tema 04. Técnicas Avanzadas de Programación
Programación Dinámica
12. Resuelva el problema de retornar el cambio con esta técnica.
13. Problema de la mochila: Dada una mochila que puede cargar un peso máximo p, y n artículos con
valor y peso distinto, de los cuales hay disponibilidad infinita, determine cuantos artículos de cada
tipo debe introducir en la mochila de manera tal que maximice el valor de la misma.
14. Realice una corrida en frio del algoritmo anterior para una mochila de capacidad máxima p = 5 y la
siguiente lista de artículos:
Artículo Peso (kg) Valor (u.m.)
A 2 65
B 3 80
C 1 30
15. Problema de la mochila 0-1: Considere el problema de la mochila, pero tomando en cuenta que la
cantidad de artículos de cada tipo es 1.
16. El algoritmo de Floyd-Warshall se utiliza para conseguir los caminos de costo mínimo entre cada par
de vértices de un grafo pesado, para ello, construye una matriz en la cual se encuentra el costo del
camino mínimo entre cada par de vértices. Esto se logra verificando si un camino simple de un
vértice v a un vértice w puede ser mejorado al pasar por el vértice k. Realice este algoritmo bajo el
enfoque de la programación dinámica.
Universidad de Carabobo Facultad de Ciencias y Tecnología Departamento de Computación
Pag. 3
