## 2.3.1 ELEMENTOS DE LA ESTRATEGIA ÁVIDA

Habitualmente, los elementos que intervienen en los algoritmos ávidos son:

- Un conjunto o lista de candidatos (tareas a procesar, vértices del grafo, etc.).
- Un conjunto de decisiones ya tomadas (candidatos ya escogidos).
- Una función que determina si un conjunto de candidatos es una solución al problema (aunque no tiene por qué ser la óptima).
- Una función que determina si un conjunto es completable, es decir, si añadiendo a este conjunto nuevos candidatos es posible alcanzar una solución al problema, suponiendo que esta exista.
- Una función de selección que escoge el candidato aún no seleccionado que es más prometedor.
- Una función objetivo que da el valor/coste de una solución (tiempo total del proceso, la longitud del camino, etc.) y que es la que se pretende maximizar o minimizar.

Para resolver el problema de optimización hay que encontrar un conjunto de candidatos que optimiza la función objetivo. Los algoritmos ávidos proceden por pasos.

Inicialmente el conjunto de candidatos es vacío. A continuación, en cada paso, se intenta añadir al conjunto el mejor candidato de los aún no escogidos, utilizando la función de selección. Si el conjunto resultante no es completable, se rechaza el candidato y no se le vuelve a considerar en el futuro. En caso contrario, se incorpora al conjunto de candidatos escogidos y permanece siempre en él. Tras cada incorporación se comprueba si el conjunto resultante es una solución del problema. Un algoritmo voraz es correcto si la solución así encontrada es siempre óptima.

Ejemplo: Mínimo número de monedas

Se desea pagar una cantidad de dinero a un cliente empleando el menor número posible de monedas. Los elementos del esquema anterior se convierten en:

- Candidato: conjunto finito de monedas de, por ejemplo, 1, 2, 5, y 10 unidades, con una moneda de cada tipo por lo menos.
- Solución: conjunto de monedas cuya suma es la cantidad a pagar.
- Completable: la suma de las monedas escogidas en un momento dado no supera la cantidad a pagar.
- Función de selección: la moneda de mayor valor en el conjunto de candidatos aún no considerados.
- Función objetivo: número de monedas utilizadas en la solución.

###