1. No category

Análisis de algoritmos
Tema 10: Algoritmos ávidos
Solicitado: Ejercicios 07: Ejercicios sobre Dijkstra, Prim y Kruskal
M. en C. Edgardo Adrián Franco Martínez
http://www.eafranco.com
[email protected]
@edfrancom
edgardoadrianfrancom
1
• Introducción
• Algoritmos ávidos
• Forma general de un algoritmo ávido
• Planteamiento de un algoritmo ávido
• Ejemplo
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Contenido
• Mínimo número de monedas
• Ejercicios 07: Ejercicios sobre Dijkstra, Prim y
Kruskal
2
• Los algoritmos ávidos o voraces (Greedy Algorithms)
son algoritmos que toman decisiones de corto
alcance, basadas en información inmediatamente
disponible, sin importar consecuencias futuras.
• Suelen ser bastante simples y se emplean sobre
todo para resolver problemas de optimización, como
por ejemplo, encontrar la secuencia óptima para
procesar un conjunto de tareas por un computador,
hallar el camino mínimo de un grafo, etc.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Introducción
3
• Normalmente son utilizados para resolver
problemas en los que la velocidad de respuesta
debe ser muy alta o en la que el árbol de decisiones
de búsqueda es muy grande, no siendo posible
analizar la totalidad de posibilidades.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
• Los algoritmos voraces también se caracterizan por
la rapidez en que encuentran una solución (cuando
la encuentran), la cual casi siempre no es la mejor.
4
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
• La estrategia general de este tipo de algoritmos se
basa en la construcción de una solución, la cual
comienza sin elementos y cada vez que debe tomar
algún tipo de decisión, lo hace con la información
que tiene a primera mano, la cual de alguna manera
le permita adicionar elementos y así avanzar hacia la
solución total. Cada elemento o paso de la solución
se adiciona al conjunto solución y así hasta llegar a
la solución final o a un punto en el cual no puede
seguir avanzando, lo cual indica que no encontró
una solución al problema.
5
• Un conjunto o lista de candidatos (tareas a procesar,
vértices del grafo, etc.)
• Un conjunto de decisiones ya tomadas (candidatos ya
escogidos).
• Una función que determina si un conjunto de
candidatos es una solución al problema (aunque no
tiene por qué ser la óptima).
• Para resolver el problema de optimización hay que
encontrar un conjunto de candidatos que optimiza
la función objetivo. Los algoritmos voraces proceden
por pasos.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
• Habitualmente, los elementos que intervienen son:
6
• Un algoritmo voraz (también conocido como ávido,
devorador o goloso) es aquel que, para resolver un
determinado problema, sigue una heurística
consistente en elegir la opción óptima en cada paso
local con la esperanza de llegar a una solución
general óptima. Este esquema algorítmico es el que
menos dificultades plantea a la hora de diseñar y
comprobar su funcionamiento. Normalmente se
aplica a los problemas de optimización.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Algoritmos ávidos
7
• Cada conjunto 𝑆 que satisfaga las restricciones se le
suele denominar prometedor, y si este además logra que
la función objetivo se minimice o maximice (según
corresponda) diremos que 𝑆 es una solución óptima.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
• Dado un conjunto finito de entradas C, un algoritmo
voraz devuelve un conjunto S (seleccionados) tal que
S ⊆ C y que además cumple con las restricciones del
problema inicial.
8
• El conjunto 𝑪 de candidatos, entradas del problema.
• Función solución, esta comprueba, en cada paso, si el
subconjunto actual de candidatos elegidos forma una
solución (no importa si es óptima o no lo es).
• Función de selección, informa de cuál es el elemento más
prometedor para completar la solución. Éste no puede haber
sido escogido con anterioridad. Cada elemento es
considerado una sola vez. Luego, puede ser rechazado o
aceptado y pertenecerá a 𝐶 \ 𝑆.
• Función de factibilidad, informa si a partir de un conjunto se
puede llegar a una solución. Lo aplicaremos al conjunto de
seleccionados unido con el elemento más prometedor.
• Función objetivo, es aquella que queremos maximizar o
minimizar, el núcleo del problema.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Elementos de los que consta la técnica
9
Función Ávido(C:conjunto):conjunto //C conjunto de candidatos
S <= vacio //S conjunto en el que se construye la solución
mientras ¬solución(S) y C <> vacío hacer
x <= el elemento de C que maximiza seleccionar(x)
C <= C \ {x}
si prometedor(S U {x}) entonces S <= S U {x}
si solución(S)
entonces devolver S
si no devolver no hay solución
Fin Ávido
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Forma general de un algoritmo ávido
10
• Para identificar si un problema es susceptible de ser
resuelto por un algoritmo ávido se definen una serie
de elementos que han de estar presentes en el
problema:
• Un conjunto de candidatos, que corresponden a las n
entradas del problema.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Forma general de un algoritmo ávido
• Una función de selección que en cada momento determine
el candidato idóneo para formar la solución de entre los
que aún no han sido seleccionados ni rechazados.
11
• Una función objetivo que determine el valor de la solución
hallada. Es la función que queremos maximizar o
minimizar.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
• Una función que compruebe si un cierto subconjunto de
candidatos es prometedor. Entendemos por prometedor
que sea posible seguir añadiendo candidatos y encontrar
una solución.
• Una función que compruebe si un subconjunto de estas
entradas es solución al problema, sea óptima o no.
12
• Para resolver el problema, un algoritmo ávido tratará de encontrar un
subconjunto de candidatos tales que, cumpliendo las restricciones del
problema, constituya la solución óptima.
• Para ello trabajará por etapas, tomando en cada una de ellas la
decisión que le parece la mejor, sin considerar las consecuencias
futuras, y por tanto escogerá de entre todos los candidatos el que
produce un óptimo local para esa etapa, suponiendo que será a su vez
óptimo global para el problema.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Planteamiento de un algoritmo ávido
• Antes de añadir un candidato a la solución que está construyendo
comprobará si es prometedora al añadirlo. En caso afirmativo lo
incluirá en ella y en caso contrario descartará este candidato para
siempre y no volverá a considerarlo.
• Cada vez que se incluye un candidato comprobará si el conjunto
obtenido es solución.
13
• Se pide crear un algoritmo que permita a una máquina
expendedora devolver el cambio mediante el menor número
de monedas posible.
1. Considerando que el número de monedas es ilimitado.
2. Considerando que el número de monedas es limitado,
es decir, se tiene un número concreto de monedas de
cada tipo.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Ejemplo: Mínimo número de monedas
14
• Solución: conjunto de monedas cuya suma es la cantidad a
pagar.
• Prometedor: la suma de las monedas escogidas en un
momento dado no supera la cantidad a pagar.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
• Candidato: conjunto finito de monedas de, por ejemplo, 1,
5, 10 y 25 unidades, con un número de monedas ilimitado
o limitado.
• Función de selección: la moneda de mayor valor en el
conjunto de candidatos aún no considerados.
• Función objetivo: número de monedas utilizadas en la
solución.
15
• Si hay que devolver la cantidad 110, se tomaría primero una moneda de
50, quedando una cantidad restante de 60. Como 50 es aún menor que
60, se tomaría otra moneda de 50. Ahora la cantidad restante es 10, por
tanto ya tenemos que devolver una moneda de 5, ya que 50 y 25 son
mayores que 10, y por tanto se desechan. La cantidad a devolver ahora es
5. Se tomaría otra moneda de 5, terminando así el problema de forma
correcta.
• Solución: Devolver dos monedas de 50 y dos de 5.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
• La estrategia a seguir consiste en escoger sucesivamente las
monedas de valor mayor que no superen la cantidad de
cambio a devolver. El buen funcionamiento del algoritmo
depende de los tipos de monedas presentes en la entrada.
Así, por ejemplo, si no hay monedas de valor menor que diez,
no se podrá devolver un cambio menor que diez. Además, la
limitación del número de monedas también influye en la
optimalidad del algoritmo, el cual devuelve buenas
soluciones bajo determinados conjuntos de datos, pero no
siempre.
Denominación de Monedas 50 25 5 1
16
fun cambio (monedas_valor[1..n] de nat, importe: nat) dev
cambio[1..n] de nat
m := 1;
mientras (importe > 0) and (m <= n) hacer
si (monedas_valor[m] <= importe) entonces
monedas[m] := monedas[m] – 1;
cambio[m] := cambio[m] + 1;
importe := importe – monedas_valor[m];
si no
m := m + 1;
fsi
fmientras
si importe > 0 entonces devolver “Error”; fsi
ffun
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Algoritmo ávido: Monedas ilimitadas
17
Denominación de Monedas 50 25 5 1
Monedas disponibles
3
4
1 6
• Si hay que devolver la cantidad 110 siguiendo el método del algoritmo
voraz, se tomaría primero una moneda de 50, quedando una cantidad
restante de 60. Como 50 es aún menor que 60, se tomaría otra moneda de
50. Ahora la cantidad restante es 10, por tanto ya tenemos que devolver
una moneda de 5, ya que 50 y 25 son mayores que 10, y por tanto se
desechan. La cantidad a devolver ahora es 5. Se tomaría otra moneda de
5, pero puesto que ya no nos queda ninguna, deberán devolverse 5 de
valor 1, terminando así el problema de forma correcta.
• Solución: Devolver dos monedas de 50, una de 5 y cinco de 1.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
• Si consideramos además un numero de monedas de cada
denominación no ilimitado deberemos ahora de considerar
que sea posible tomar monedas de cada denominación para
formar la solución
18
fun cambio (monedas_valor[1..n] de nat, monedas[1..n] de nat,
importe: nat) dev cambio[1..n] de nat
m := 1;
mientras (importe > 0) and (m <= n) hacer
si (monedas_valor[m] <= importe) and (monedas[m] > 0)
entonces
monedas[m] := monedas[m] – 1;
cambio[m] := cambio[m] + 1;
importe := importe – monedas_valor[m];
si no
m := m + 1;
fsi
fmientras
si importe > 0 entonces devolver “Error”; fsi
ffun
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Algoritmo ávido: Monedas limitadas
19
• Árboles generadores minimales
• Problema
• Dado un grafo conexo G = (V, A) no dirigido y ponderado con pesos
positivos, calcular un subgrafo conexo T ⊆ G que conecte todos los
vértices del grafo G y que la suma de los pesos de las aristas seleccionadas
sea mínima.
• Solución
• Este subgrafo es necesariamente un árbol: árbol generador minimal o
árbol de recubrimiento mínimo (“minimum spanning tree” [MST]).
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Ejemplo: Algoritmos Greedy sobre grafos
20
• Diseño de redes: redes telefónicas, eléctricas, hidráulicas, de ordenadores,
de carreteras…
• Construcción de redes de mínimo coste
• Refuerzo de líneas criticas
• Identificación de cuellos de botella
• Enrutamiento (evitar ciclos)
• Soluciones aproximadas para problemas NP.
• Algoritmos de agrupamiento (análisis de clúster)
• Algoritmos Greedy para resolver el problema:
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
• Aplicaciones
• Algoritmo de Kruskal:
• Comenzando con T=∅, considerar las aristas en orden creciente de coste y
añadir las aristas a T salvo que hacerlo suponga la creación de un ciclo.
• Algoritmo de Prim:
• Comenzando con un nodo raíz arbitrario s, hacer crecer el árbol T desde s
hacia afuera. En cada paso, se añade al árbol T el nodo que tenga una
arista de menor coste que lo conecte a otros nodos de T.
• Algoritmo de borrado inverso:
• Comenzando con T=A, considerar las aristas en orden decreciente de coste
y eliminar las aristas de T salvo que eso desconectase T.
21
• Caminos mínimos
• Problema
• Dado un grafo G ponderado con pesos positivos, calcular el camino de
menor peso existente entre un vértice s y otro vértice t.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Ejemplo: Caminos mínimos
22
• El algoritmo de Djikstra es un algoritmo muy único. Inicialmente, se
utiliza un enfoque voraz para conseguir distancias iniciales a los nodos
vecinos. Luego, en el siguiente paso, se comprueba si el valor
calculado es el óptimo global a ese nodo o no. Si no, se comprueba
todos los otros caminos y calcula la distancia óptima a ese
nodo. Luego, basándose en los valores ya calculados de los nodos
anteriores, se calcula el camino más corto para el nodo final. Por lo
tanto, esto es una especie de un enfoque de programación dinámica.
• Así, Djikstra utiliza ambos enfoques y, por tanto, no puede ser
completamente clasificada como "Greedy" o "DP". Es una mezcla de
ambos y por lo tanto, es único. Siempre ha sido un tema debatido. Tal
es la belleza del algoritmo.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
• Algoritmo de Dijkstra (1959)
• Dado un grafo G=(V,A) y un vértice s, encontrar el camino de costo
mínimo para llegar desde s al resto de los vértices en el grafo.
• IDEA: Mantener el conjunto de nodos ya explorados para los cuales ya
hemos determinado el camino más corto desde s…
23
• Para los siguientes 5 grafos detallar la solución de la ruta más corta
del nodo (1) a todos los nodos (Dijkstra) y el árbol recubridor
mínimo mediante Prim y Kruskal.
• Describir de manera detallada los algoritmos y sus pasos.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Ejercicios 07: Ejercicios sobre Dijkstra, Prim y
Kruskal
Ejercicio 01
24
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Ejercicio 02
Ejercicio 03
25
Ejercicio 05
*Se entregará antes del día Miércoles 01 de Julio de 2015
(23:59:59 hora limite).
*Portada y encabezados de pagina.
Análisis de algoritmos
10 Algoritmos ávidos
Prof. Edgardo Adrián Franco Martínez
Ejercicio 04
26