Post on 22-Sep-2018
transcript
Análisis y Diseño de AlgoritmosAlgoritmos Voraces
DR. JESÚS A. GONZÁLEZ BERNAL
CIENCIAS COMPUTACIONALES
INAOE
Introducción22
Siempre toman la mejor opción en cada momento (punto de decisión del algoritmo)Una opción óptima local
Pensando que esta opción llevará a una solución óptima global
No siempre llevan a soluciones óptimasAunque sí para muchos problemas
Elementos de una Estrategia Voráz33
Subestructura óptima
Propiedad de elección-voraz (greedy-choice)
Propiedad de Elección-voraz44
A cada paso se toma una decisión óptima localLa solución óptima global no depende de la solución de sus subproblemasEn principio se puede llegar a una solución óptima global tomando decisiones óptimas locales (aunque no siempre)
Es necesario probar esto
Diferente de programación dinámicaResuelve problemas en modo Top-Down
Probando que un Algoritmo Voraz es Óptimo55
Hay que probar que tomando una solución óptima en cada paso nos llevará a una solución global óptima
Se parte de una solución global óptimaSe muestra que se puede modificar la solución intercambiando el primer paso por una elección voraz y que esta elección reduce el problema a uno similar pero más pequeñoUtiliza inducción para mostrar que se puede hacer una elección voraz a cada paso del algoritmo
Existe subestructura óptima
Subestructura Óptima6
Un problema tiene subestructura óptima sí una solución óptima contiene soluciones óptimas a sus subproblemas
Como en programación dinámica
Problema de la Mochila Fraccional7
Un ladrón encuentra n artículos en una tiendaEl i-ésimo artículo cuesta vi pesos y pesa wi kilos
Quiere tomar lo más valioso que pueda en una carga
Puede cargar a lo más W kilos en su mochila para algún W
Puede tomar fracciones de artículos siempre y cuando no se exceda el peso límite W
Problema de la Mochila Fraccional8
¿Qué cantidad y de qué artículos debe tomar el ladrón para maximizar el valor del botín?
Algoritmo vorazTomar tanto del artículo con el valor más alto por kilo (vi/wi) como se pueda.
Si se acaba un artículo, tomar del siguiente artículo con valor (vi/wi) más alto
Continuar hasta que se llene la mochila
Problema de la Mochila FraccionalPrueba: Propiedad de Elección Voraz
9
Si tenemos una solución óptima al problema de la mochila O = {o1, o1, …, oj} con j elementos.
Supongamos que existe una solución voraz G = {g1, g1, …, gk} con k elementos ordenados de acuerdo a la elección voraz
Prueba adaptada de: http://www.cs.kzoo.edu/cs215/ por Nathan Sprague
Problema de la Mochila FraccionalPrueba: Propiedad de Elección Voraz
10
Queremos mostrar que existe una solución óptima O’ que incluye la elección voraz g1.
CASO 1: g1 no es fraccional
Si g1 esta en O, no hay nada que probar
Si g1 no esta en O, arbitrariamente quitamos wg1 en artículos de O y lo reemplazamos con g1 para producir O’
O’ es una solución y es tan buena como O
CASO 2: g1 es fraccional (K = f*wg1 donde f es la fracción de g1 elegida y K es el límite de peso)
Si O incluye f*wg1 unidades de g1, no hay nada que probar
Si O incluye menos de f de g1, quitamos f*wg1 peso de O arbitrariamente y lo reemplazamos con f*wg1 unidades de g1 para construir O’
O’ es una solución válida y al menos tan buena como O.
Prueba adaptada de: http://www.cs.kzoo.edu/cs215/ por Nathan Sprague
Problema de la Mochila FraccionalPrueba: Subestructura Óptima
11
Se demostró que hay una solución óptima O’ que contiene a g1
Después de elegir g1 el límite de peso es K’’ = K – wg1 y el conjunto de artículos se convierte en I’’ = I – {g1}
Sea P’’ el problema de la mochila con límite de peso K’’ y lista de artículos I’’. Debemos probar que O’’ = O’ – {g1} es una solución óptima de P’’
Probamos por contradicción:Asumimos que O’’ no es una solución de P’’. Sea Q una solución óptima con más valor que O’’.
Sea R = Q ∪ {g1}. El valor de O’ es igual al valor de O’’ + g1
El valor de R es mayor que el valor de O’ = O’’ + g1
Como O’ era una solución óptima, esta es una contradicción.
Prueba adaptada de: http://www.cs.kzoo.edu/cs215/ por Nathan Sprague
Problema de Selección de Actividades(Activity Selection –Scheduling– Problem)
12
Dado un conjunto de n actividades a realizarS = {1, 2, …, n}
Todas las actividades requieren el mismo recurso (p.e. el mismo salón de clases) y lo utilizan uno a la vez
Cada actividad i tiene un tiempo de inicio si y de fin fi, si ≤ fi, [si, fi)
Dos actividades i y j son compatibles si no se traslapan: si ≥ fj ó sj≥ fi
Problema: Elegir el conjunto más grande de actividades compatibles.
Asumir que la entrada esta ordenada por f1 ≤ f2 ≤ … ≤ fn (O(nlgn)).
Problema de Selección de ActividadesAlgoritmo Voraz
13
Problema de Selección de ActividadesEjemplo
14
Problema de Selección de ActividadesAnálisis
15
El índice i tiene al último elemento (con mayor fi) que cualquier otra actividad en A
Greedy-Activity-Selector toma un tiempo de Θ(n)
Es un algoritmo greedy porque:Siempre elige la actividad compatible con el tiempo de terminación más temprano, dejando tanto tiempo libre como sea posible
Problema de Selección de ActividadesAnálisis
16
¿Es óptimo?Sí
PruebaSi ordenamos por fi, la actividad 1 termina antes que las demás
Mostrar que existe una solución óptima que empieza con una selección voraz (actividad 1)
Sea A ⊆ S una solución óptimaSi la primera actividad en A es k ≠ 1 (no es voraz), entonces existe otra solución óptima B que inicia con 1
B = A – {k} ∪ {1}
Como f1 ≤ fk, la actividad 1 todavía es compatible con A
|B| = |A|, entonces B es óptima. Entonces existe una solución óptima que inicia con una elección voraz
Problema de Selección de ActividadesAnálisis
17
También probamos su subestructura óptimaDespués de hacer la primera elección voraz tenemos el problema
S ’ = { i∈ S : si ≥ f1}, solo contamos con actividades que inicien después de f1
con solución óptima A’ = A – {1}
Esta solución debe ser óptimaSi B ’ soluciona S ’ con más actividades que A’, si agregamos la actividad 1 a B ’ lo hace más grande que A
Esto es una contradicción porque A ya era una solución óptima
Por tanto, la elección voraz nos lleva a una solución óptima
Problema de Selección de ActividadesProgramación Dinámica
18
Ya probamos que tiene subestructura óptimaAnálisis del problema
Sij = {ak ∈ S : fi ≤ sk < fk ≤ sj}
Aij tal que
Definición de c[i,j] como el tamaño de Aij.Tenemos la recurrencia:
Todavía considera muchos subproblemasAún con los subproblemas repetidos
Es mejor la versión voraz, la cual también es óptima
|}}{{|max|| kjkikSijaij AaAAk
∪∪=∈
}.1],[],[{max],[ ++= << jkckicjic jki
Problema de la Mochila 0-119
Un ladrón encuentra n artículos en una tiendaEl i-ésimo artículo cuesta vi pesos y pesa wi kilos, vi y wi son enteros
Quiere tomar lo más valioso que pueda en una carga
Puede cargar a lo más W kilos en su mochila para algún W entero
NO puede tomar fracciones de artículos, es un problema binario 0-1, o lo toma o lo deja
Ambos problemas de la mochila, el fraccional y el binario tienen subestructura óptima
El problema de la mochila binario no se resuelve con un algoritmo voraz
Sí con Programación Dinámica
Problema de la Mochila 0-120
Códigos de Huffman21
Los códigos de Huffman se utilizan para compresión de datos
Algoritmo Voraz
Determina códigos óptimos de longitud variable a caracteres
Dado un archivo de 100,000 caracteres, con 6 caracteres diferentes: a, b , c, d, e, f
Códigos de longitud fija: 300,000 bits
Códigos de longitud variable: 224,000 bitsCódigos cortos a caracteres más frecuentes
Códigos largos a caracteres menos frecuentes
Códigos Prefijo22
En un código prefijo, ningún código es prefijo de otro código
Simple codificar y decodificarabc 0.101.100
Utilizamos un árbol para decodificar001011101 0.0.101.1101 aabe
Si una cadena hace un match con un código, se da como salida, no hay ambigüedad
Códigos Prefijo23
Un código óptimo para un archivo siempre se representa por un árbol binario completo
Cada nodo no-hoja tiene dos hijosEl código de longitud fija del ejemplo no es óptimo
El árbol binario no esta completo
Si C es el alfabeto de caracteresEl árbol para un código prefijo óptimo tiene exactamente |C| hojasUna por cada letra del alfabetoExactamente |C| - 1 nodos internos
Sea f(c) la frecuencia del carácter c en el archivoSea dT(c) la profundidad de la hoja de c en el árbolNúmero de bits requeridos para codificar el archivo es:B(T) es el costo del árbol T
∑∈
=Cc
T cdcfTB )()()(
Construcción del Código Huffman24
Huffman inventó un algoritmo voraz para construir códigos prefijo óptimos llamado “Huffman Code”
Construye el árbol T del código óptimo de forma bottom-up
Inicia con un conjunto de |C| hojas y hace una secuencia de |C| - 1 operaciones “merge” para crear el árbol final
Une las dos hojas con menor frecuencia (hoja o interno) hasta que todas las hojas se han considerado
Usa un “priority queue” Q para mantener los nodos ordenados por frecuencia
Construcción del Código Huffman25
Construcción del Código HuffmanEjemplo
26
Análisis del Algoritmo HuffmanCode27
Q se implementa como un heap binario
Inicialización de Q para el conjunto C de n caracteres toma O(n) (línea 2) con Build-Heap
Ciclo de líneas 3-8 se ejecutan |n| -1 vecesCada operación del Heap requiere O(lgn)
El ciclo contribuye O(nlgn)
Tiempo total: O(nlgn)
El Algoritmo de Huffman es Correcto28
Para probar que es correcto, determinar un código prefijo óptimo debe tener las propiedades de
Elección voraz
Subestructura óptima
Lema 17.229
El procedimiento Huffman tiene la propiedad de elección voraz
Prueba
Lema 17.230
Asumimos que x y y tienen las frecuencias más bajas
Si x y y tienen las frecuencias más bajas, entonces existe un código óptimo en el que x y y estén a la profundidad máxima
La elección voraz
Supongamos ahora que tenemos una solución óptima en la que b y cson caracteres hermanos en hojas de máxima profundidad en la solución T
f[b] ≤ f[c] y f[x] ≤ f[y]
f[x] y f[y] son las frecuencias más bajas y f[b] y f[c] son frecuencias arbitrarias
f[x] ≤ f[b] y f[y] ≤ f[c]
Intercambiamos posiciones en T de b y x para producir T ’
Intercambiamos posiciones en T ’ de c y y para producir T ’’
Hay una diferencia en costos
Lema 17.231
Entonces, si llevamos a x a la mayor profundidad (similar para y), obtenemos un mejor árbol en el que x y y son nodos hoja hermanos en la profundidad máxima
Implica que se puede empezar con la elección vorazJuntar los dos caracteres con la menor frecuencia
Lema 17.332
El procedimiento Huffman tiene la propiedad de subestructura óptima
Consideremos el árbol T para los caracteres C
Sean x y y dos caracteres hermanos, hojas en T y z su padre (x y yson los de menor frecuencia)
Consideremos el árbol óptimo T ’ para C ’ = C – {x,y} ∪ {z}f(z) = f(x) + f(y)
Si hubiera un mejor árbol para C ’, llamado T ’’, entonces podríamos usar T ’’ para construir un mejor árbol original añadiendo x y y bajo z
Pero el árbol original T es óptimo, entonces esta es una contradicción
Entonces T ’ es el árbol óptimo para C ’
Huffman tiene la propiedad de subestructura óptima
Teorema 17.433
El procedimiento Huffman produce un código prefijo óptimo
Inmediato de los lemas 17.2 y 17.3