Estrategia avariciosa (Greedy)

Vista previa del material en texto

Estrategia avariciosa (Greedy)
Lic. Ciencia de datos
Antony Arturo García Pérez
Maestro. Rodolfo Martínez Zúñiga
Análisis y Diseño de Algoritmos
25 de marzo de 2021
Algoritmo avaricioso
En ciencias de la computación, un algoritmo voraz (también conocido como goloso, ávido, devorador o greedy) es una estrategia de búsqueda por la cual se 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.
Esquema
Dado un conjunto finito de entradas C, un algoritmo voraz devuelve un conjunto S (seleccionados) tal que S c C  y que además cumple con las restricciones del problema inicial. A cada conjunto S 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 S es una solución óptima
Elementos de la estrategia avariciosa
C: candidatos, entradas del problema
Función solución. Comprueba, en cada paso, si el subconjunto actual de candidatos elegidos forma una solución
Función de selección. Informa cuál es el elemento más prometedor para completar la solución. Este no puede haber sido escogido con anterioridad. Cada elemento es considerado una sola vez.
Función de factibilidad. Informa si a partir de un conjunto se puede llegar a una solución.
Función objetivo. Es aquella que queremos maximizar o minimizar, el núcleo del problema.
Funcionamiento
El algoritmo escoge en cada paso al mejor elemento x є C posible, conocido como el elemento más prometedor. Se elimina ese elemento del conjunto de candidatos (C ← C \ {x}) y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados (S U {x}) produce una solución factible.
Problema de selección de actividades (Planteamiento)
El problema de selección de actividades es un problema en el que una persona tiene una lista de trabajos por hacer. Cada una de las actividades tiene una hora de inicio y una hora de finalización. Necesitamos programar las actividades de tal manera que la persona pueda completar un número máximo de actividades.
Dado que el tiempo de las actividades puede colapsar, es posible que no sea posible completar todas las actividades y, por lo tanto, debemos programar las actividades de tal manera que se pueda completar el número máximo de actividades.
Solución de un problema de actividades
Se tiene la siguiente tabla con las actividades (ai) y sus horas de inicio (si) y de fin (fi)
Para tomar el elemento con el menor tiempo de finalización, iteraremos sobre la lista de actividades y seleccionaremos la primera actividad y luego seleccionaremos la actividad que comienza después de que finalice la actividad actualmente seleccionada.
Códigos de Huffman
Es un algoritmo usado para compresión de datos. El término se refiere al uso de una tabla de códigos de longitud variable para codificar un determinado símbolo (como puede ser un archivo), donde la tabla ha sido rellenada de una manera específica basándose en la probabilidad estimada de aparición de cada posible valor de dicho símbolo.
Ejemplo de código de Huffman
Árbol de Huffman generado para las frecuencias de apariciones exactas del texto "ESTO ES UN EJEMPLO DE UN ARBOL DE HUFFMAN"
Matroides y la estrategia avariciosa
En la optimización matemática, los algoritmos codiciosos resuelven de manera óptima problemas combinatorios que tienen las propiedades de las matroides y dan aproximaciones de factor constante a los problemas de optimización con estructura submodular.
Se le llama matroide a una estructura que toma y generaliza el concepto de independencia lineal en los espacios vectoriales.