Algoritmo Voráz
Se usan para optimizar o minimizar una función objetivo partiendo de un conjunto de entradas. Esta estrategia de solución consiste en ir seleccionando los elementos que conformaran (en su conjunto) una solución óptima global del problema. Debemos contar con una función local de selección que nos asegure una solución óptima global (en el mejor de los casos). Una vez seleccionado el candidato, no hay marcha atrás, de ahí la importancia de la función de la selección local.
Planteamiento
Dado un problema con n entradas el método consiste en obtener un subconjunto de éstas que satisfaga una determinada restricción definida por el problema.
Cada uno de los conjuntos que cumplan con estás restricciones, los llamaremos prometedores.
¿cómo distinguir un problema en donde aplicar este enfoque?
Serie de elementos que deben estár presente en el problema:
- Un conjunto de cadidatos (n entradas).
- Una función de selección que en cada momento identifique el candidato idóneo para formar la solución.
- Una función que compruebe si cierto subconjunto de candidatos es prometedor, es decir, que sea posible seguir añadiendo candidatos y encontrar una solución.
- Una función objetivo que determine el valor de la solución hallada. Es la función que debemos maximizar o minimizar.
- Otra función que compruebe si un subconjunto de estas entradas es solución al problema, sea óptimo o no.
¿Cómo funciona el algoritmo?
- El algoritmo tratará de encontrar un subconjunto de candidatos que cumplan las restricciones del problema y constituyan una solución óptima.
- Esto lo realiza por etapas, tomando en cada una de ellas la decisión que le parece mejor, sin considerar las consecuencias futuras, es decir, elegirá un óptimo local. Aunque con esto no se aseguré que formará parte de la solución global.
- Antes de añadir un candidato a la solución que se va construyendo, comprobará si al hacerlo la solución se vuelve prometedora. En caso de que lo sea se incluirá en la solución, si no es así el candidato es descartado y marcado (para no volver a considerarlo).
- Cada vez que se incluye un candidato comprabará si el conjunto obtenido es solución.
Resumen
Los algoritmos ávidos construyen la solución en etapas sucesivas, tratando siempre de tomar la decisión óptima para cada etapa.
Ejemplo. Dado una cantidad n conjunto de monedas (con los valores 200, 100, 50, 25, 10, 5 y 1), encontrar el número de monedas de cada denominación que se necesitan para representar dicha cantidad de entrada.
Implementación de la solución con un esquema ávido en C++.
#define N 7
main(){
int monedas[N] = {200,100,50,25,10,5,1}, //entrada de N elementos
cambio[N]; //vector solución
int i,j,n ;
while (scanf ("%d\n",&n) && n){
printf ("%d = ",n);
//inicialización
for (j=0; j<N; j++) cambio[j]=0;
//función objetivo: minimizar el número de monedas
for (i =0 ; i< N; i++) //óptimo local: Ci mejor que Ci+1
while (monedas[i] <= n)
cambio[i]++,
n=n-monedas[i];
for (j=0; j<N; j++)
printf ("%d(%d)",cambio[j],monedas[j]),
printf ("%s", j+1<N ? " + ": "\n");
}
}
Sample Input
123
23
3
1233
344393
2341123
93003
314
4555
111
344
203
0
Sample Output
123 = 0(200) + 1(100) + 0(50) + 0(25) + 2(10) + 0(5) + 3(1)
23 = 0(200) + 0(100) + 0(50) + 0(25) + 2(10) + 0(5) + 3(1)
3 = 0(200) + 0(100) + 0(50) + 0(25) + 0(10) + 0(5) + 3(1)
1233 = 6(200) + 0(100) + 0(50) + 1(25) + 0(10) + 1(5) + 3(1)
344393 = 1721(200) + 1(100) + 1(50) + 1(25) + 1(10) + 1(5) + 3(1)
2341123 = 11705(200) + 1(100) + 0(50) + 0(25) + 2(10) + 0(5) + 3(1)
93003 = 465(200) + 0(100) + 0(50) + 0(25) + 0(10) + 0(5) + 3(1)
314 = 1(200) + 1(100) + 0(50) + 0(25) + 1(10) + 0(5) + 4(1)
4555 = 22(200) + 1(100) + 1(50) + 0(25) + 0(10) + 1(5) + 0(1)
111 = 0(200) + 1(100) + 0(50) + 0(25) + 1(10) + 0(5) + 1(1)
344 = 1(200) + 1(100) + 0(50) + 1(25) + 1(10) + 1(5) + 4(1)
203 = 1(200) + 0(100) + 0(50) + 0(25) + 0(10) + 0(5) + 3(1)
