Algoritmos Voraces

Algoritmos Voraces

Algoritmo voraz

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.

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 sólo 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 dolar estadounidense, son casos especiales donde en la estrategia del algoritmo voraz da con la solución óptima.

Esquema

Dado un conjunto finito de entradas C C, un algoritmo voraz devuelve un conjunto S S tal que S ⊆ C y que además cumple con las restricciones del problema inicial. A cada conjunto S {\displaystyle S} 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 S es una solución

Elementos de los que consta la técnica

    El conjunto C {\displaystyle C} C 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 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 C ∖ S {\displaystyle C\setminus S} {\displaystyle C\setminus S}.
    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.

Obtenido de «https://es.wikipedia.org/w/index.php?title=Algoritmo_voraz&oldid=85648321»


Mis sitios nuevos:
Emprendedores
Politica de Privacidad