DR. JOSÉ MARTÍNEZ CARRANZA
CIENCIAS COMPUTACIONALESINAOE
Análisis y Diseño de AlgoritmosAlgoritmos Voraces
2
Introducción
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 óptimas Aunque sí para muchos problemas
2
3
Elementos de una Estrategia Voráz
Subestructura óptima Propiedad de elección-voraz (greedy-choice)
3
4
Propiedad de Elección-voraz
A cada paso se toma una decisión óptima local La solución óptima global no depende de la solución de sus
subproblemas En 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ámica Resuelve problemas en modo Top-Down
4
Subestructura Óptima
Un problema tiene subestructura óptima sí una solución óptima contiene soluciones óptimas a sus subproblemas Como en programación dinámica
5
Códigos de Huffman6
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 bits
Códigos cortos a caracteres más frecuentes Códigos largos a caracteres menos frecuentes
Códigos Prefijo7
En un código prefijo, ningún código es prefijo de otro código Simple codificar y decodificar
abc 0.101.100
Utilizamos un árbol para decodificar 001011101 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 Prefijo8
Un código óptimo para un archivo siempre se representa por un árbol binario completo Cada nodo no-hoja tiene dos hijos El código de longitud fija del ejemplo no es óptimo
El árbol binario no esta completo Si C es el alfabeto de caracteres
El árbol para un código prefijo óptimo tiene exactamente |C| hojas Una por cada letra del alfabeto Exactamente |C| - 1 nodos internos
Sea f(c) la frecuencia del carácter c en el archivo Sea dT(c) la profundidad de la hoja de c en el árbol Número de bits requeridos para codificar el archivo es: B(T) es el costo del árbol T
B(T )= ∑c∈ C
f ( c )dT (c )
Construcción del Código Huffman9
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 Huffman10
Construcción del Código HuffmanEjemplo
11
Análisis del Algoritmo HuffmanCode
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 veces Cada operación del Heap requiere O(lgn) El ciclo contribuye O(nlgn)
Tiempo total: O(nlgn)
12
El Algoritmo de Huffman es Correcto
Para probar que es correcto, determinar un código prefijo óptimo debe tener las propiedades de Elección voraz Subestructura óptima
13
Lema 17.2
El procedimiento Huffman tiene la propiedad de elección voraz
Prueba
14
Lema 17.2
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 a y bson caracteres hermanos en hojas de máxima profundidad en la solución T f[a] ≤ f[b] y f[x] ≤ f[y] f[x] y f[y] son las frecuencias más bajas y f[a] y f[b] son frecuencias
arbitrarias f[x] ≤ f[a] y f[y] ≤ f[b]
Intercambiamos posiciones en T de a y x para producir T ’ Intercambiamos posiciones en T ’ de b y y para producir T ’’ Hay una diferencia en costos
15
Lema 17.2
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 voraz Juntar los dos caracteres con la menor frecuencia
16
Lema 17.3
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 y son 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
17
Teorema 17.4
El procedimiento Huffman produce un código prefijo óptimo Inmediato de los lemas 17.2 y 17.3
18
Problema de la Mochila Fraccional19
Un ladrón encuentra n artículos en una tienda El 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 Fraccional20
¿Qué cantidad y de qué artículos debe tomar el ladrón para maximizar el valor del botín?
Algoritmo voraz Tomar 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 Selección de Actividades(Activity Selection –Scheduling– Problem)
21
Dado un conjunto de n actividades a realizar S = {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
22
Problema de Selección de ActividadesEjemplo
23
Problema de Selección de ActividadesAnálisis
24
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 la Mochila 0-125
Un ladrón encuentra n artículos en una tienda El 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 binariotienen subestructura óptima
El problema de la mochila binario no se resuelve con unalgoritmo voraz Sí con Programación Dinámica
Problema de la Mochila 0-126