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.
Un algoritmo voraz determina el mínimo número de monedas que debe devolverse en el cambio. En la figura se muestran los pasos que un ser humano debería seguir para emular a un algoritmo voraz para acumular 36 céntimos usando solamente monedas de valores nominales de 1, 5, 10 y 20. La moneda del mayor valor menor que el resto debido es el óptimo local en cada paso. Nótese que en general el problema de devolución del cambio requiere programación dinámica o programación lineal para encontrar una solución óptima. Sin embargo, en muchos sistemas monetarios, incluyendo el euro y el dólar estadounidense, son casos especiales donde en la estrategia del algoritmo voraz da con la solución óptima.
Esquema
Dado un conjunto finito de entradas , un algoritmo voraz devuelve un conjunto (seleccionados) tal que y que además cumple con las restricciones del problema inicial. A 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.
Elementos de los que consta la técnica
El conjunto de candidatos, entradas del problema.
Función solución. 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 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. 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.
Funcionamiento
El algoritmo escoge en cada paso al mejor elemento posible, conocido como el elemento más prometedor. Se elimina ese elemento del conjunto de candidatos () y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados () produce una solución factible.
En caso de que así sea, se incluye ese elemento en . Si la inclusión no fuera factible, se descarta el elemento. Iteramos el bucle, comprobando si el conjunto de seleccionados es una solución y, si no es así, pasando al siguiente elemento del conjunto de candidatos.
Brassard, Gilles; Bratley, Paul (1997). «Algoritmos voraces». Fundamentos de Algoritmia. Madrid: PRENTICE HALL. ISBN 84-89660-00-X.
Enlaces externos
Wikilibros alberga un libro o manual sobre Algoritmia/Algoritmos voraces.
En inglés:
Definición del NIST
Datos:Q504353
Multimedia:Greedy algorithms
Agosto 05, 2021
algoritmo, voraz, ciencias, computación, algoritmo, voraz, también, conocido, como, goloso, ávido, devorador, greedy, estrategia, búsqueda, cual, sigue, heurística, consistente, elegir, opción, óptima, cada, paso, local, esperanza, llegar, solución, general, ó. En ciencias de la computacion un algoritmo voraz tambien conocido como goloso avido devorador o greedy es una estrategia de busqueda por la cual se sigue una heuristica consistente en elegir la opcion optima en cada paso local con la esperanza de llegar a una solucion general optima Este esquema algoritmico es el que menos dificultades plantea a la hora de disenar y comprobar su funcionamiento Normalmente se aplica a los problemas de optimizacion Un algoritmo voraz determina el minimo numero de monedas que debe devolverse en el cambio En la figura se muestran los pasos que un ser humano deberia seguir para emular a un algoritmo voraz para acumular 36 centimos usando solamente monedas de valores nominales de 1 5 10 y 20 La moneda del mayor valor menor que el resto debido es el optimo local en cada paso Notese que en general el problema de devolucion del cambio requiere programacion dinamica o programacion lineal para encontrar una solucion optima Sin embargo en muchos sistemas monetarios incluyendo el euro y el dolar estadounidense son casos especiales donde en la estrategia del algoritmo voraz da con la solucion optima Indice 1 Esquema 1 1 Elementos de los que consta la tecnica 1 2 Funcionamiento 2 Ejemplos de algoritmos voraces 3 Temas relacionados 4 Referencias 5 Enlaces externosEsquema EditarDado un conjunto finito de entradas C displaystyle C un algoritmo voraz devuelve un conjunto S displaystyle S seleccionados tal que S C displaystyle S subseteq C y que ademas cumple con las restricciones del problema inicial A cada conjunto S displaystyle S que satisfaga las restricciones se le suele denominar prometedor y si este ademas logra que la funcion objetivo se minimice o maximice segun corresponda diremos que S displaystyle S es una solucion optima Elementos de los que consta la tecnica Editar El conjunto C displaystyle C de candidatos entradas del problema Funcion solucion Comprueba en cada paso si el subconjunto actual de candidatos elegidos forma una solucion no importa si es optima o no lo es Funcion de seleccion Informa cual es el elemento mas prometedor para completar la solucion Este no puede haber sido escogido con anterioridad Cada elemento es considerado una sola vez Luego puede ser rechazado o aceptado y pertenecera a C S displaystyle C setminus S Funcion de factibilidad Informa si a partir de un conjunto se puede llegar a una solucion Lo aplicaremos al conjunto de seleccionados unido con el elemento mas prometedor Funcion objetivo Es aquella que queremos maximizar o minimizar el nucleo del problema Funcionamiento Editar El algoritmo escoge en cada paso al mejor elemento x C displaystyle x in C posible conocido como el elemento mas prometedor Se elimina ese elemento del conjunto de candidatos C C x displaystyle C gets C setminus x y acto seguido comprueba si la inclusion de este elemento en el conjunto de elementos seleccionados S x displaystyle S cup x produce una solucion factible En caso de que asi sea se incluye ese elemento en S displaystyle S Si la inclusion no fuera factible se descarta el elemento Iteramos el bucle comprobando si el conjunto de seleccionados es una solucion y si no es asi pasando al siguiente elemento del conjunto de candidatos Ejemplos de algoritmos voraces EditarAlgoritmo de Kruskal Algoritmo de Prim Algoritmo de Dijkstra Algoritmo de triangulacion voraz Algoritmo para la ubicacion optimaTemas relacionados EditarAlgoritmo Algoritmo heuristicoReferencias EditarBrassard Gilles Bratley Paul 1997 Algoritmos voraces Fundamentos de Algoritmia Madrid PRENTICE HALL ISBN 84 89660 00 X Enlaces externos Editar Wikilibros alberga un libro o manual sobre Algoritmia Algoritmos voraces En ingles Definicion del NIST Datos Q504353 Multimedia Greedy algorithmsObtenido de https es wikipedia org w index php title Algoritmo voraz amp oldid 133465186, wikipedia, wiki, leyendo, leer, libro, biblioteca,
