Los algoritmos voraces (greedy algorithms en inglés) son unas rutinas muy eficientes (O(n), O(n2)) aunque no suelen proporcionar la mejor solución a un problema. Existen algoritmos voraces muy conocidos, como el Algoritmo de Dijkstra o el Algoritmo de Kruskal. Vamos a resolver mediante un algoritmo voraz el conocido Problema del cambio de monedas. El problema se presenta de la siguiente forma: Dado un sistema monetario S de longitud K y una cantidad de cambio C, devolver una solución (si existe) que nos indique el número de monedas de S equivalente a C, es decir, que nos muestre el cambio para C a partir de monedas de S. Veamos un ejemplo:
En este ejemplo nos proporcionan un sistema monetario que contiene monedas de valor 10, 6, 5 y 1. La cantidad que debemos cambiar es C=12. El algoritmo voraz siempre intentará realizar el cambio mediante monedas del mayor valor posible. Si en algún paso C es menor estricto que S[t] (t≤K), se incrementará t y repetiremos el mismo paso para la siguiente moneda de S. Al finalizar, el algoritmo voraz nos indica que el cambio resultante para 12 son dos monedas de 1 y una de 10. Cómo he comentado al principio los algoritmos voraces en muchas ocasiones no presentan la mejor solución, pues en éste ejemplo sería mejor cambiar 12 por dos monedas de 6, entendiendo por mejor solución devolver el menor número de monedas posibles.
También cabe decir que a veces los algoritmos voraces nos indican que no existe solución cuando realmente sí la hay. Un ejemplo de ello es el siguiente:
El esquema básico de un algoritmo voraz es el siguiente:
Clase EsquemaVoraz
proc voraz()
alg
inicializa()
mientras (No fin())
seleccionaYElimina()
si (prometedor()):
anotaEnSolucion()
fsi
fmientras
fin
Para usar el esquema para resolver el Problema del cambio de moneda debemos de implementar los métodos inicializa, fin, seleccionaYElimina, prometedor y anotaEnSolucion.
- inicializa(): Crea e inicializa a ceros el array de enteros dónde se anotará la solución y pone a cero el puntero k.
- fin(): Comprueba si hemos terminado verificando que se cumpla que hemos llegado al final del recorrido del sistema monetario (es decir, que ya no hay monedas de valor más pequeño) o el cambio se haya completado (c=0).
- seleccionaYElimina(): Incrementamos el puntero k para seleccionar una moneda de menor valor.
- prometedor(): Nos indica si la moneda candidata es solución para realizar el cambio (condición: que la moneda tenga un valor inferior al cambio).
- anotaEnSolución(): Si el candidato cumple la condición lo anotamos en el array de solución.
Clase CambiodeMonedas hereda EsquemaVoraz m: array[1..n] de Entero c: Entero k: Entero sol: array[1..n] de Enteroproc inicializa()
alg sol:= k:=0 finfunc fin() dev (b: Lógico)
alg b:=((k=n) ó (c=0)) finproc seleccionaYElimina()
alg k:=k+1 finfunc prometedor() dev (b: Lógico)
alg b:=(m[k]Más información | <a href="http://en.wikipedia.org/wiki/Greedy_algorithm">Greedy algorithm en Wikipedia</a>
Comentarios
Curiosamente, los algoritmos greedy también son llamados "algoritmos miopes", porque su principal característica es no detenerse a "pensar" en los candidatos a examinar; simplemente toma "el más apetecible" (la moneda de más valor en el ejemplo), y nunca vuelve hacia atrás (a diferencia de los algoritmos que utilizan backtracking).
Para alguien interesado en el tema, agregar que la solución óptima al problema de la devolución del cambio lo da un algoritmo que utiliza la técnica de "programación dinámica" (curioso el nombre, ya que en realidad no es ni programación, ni dinámica) y que se basa en una tabla que almacena las monedas a devolver según el cambio que se desee dar.
Más información en el "Problema de las monedas con programación dinámica"
Salu2
PD: Ojalá hubiésemos tenido esos gráficos de apoyo. Digamos que la motricidad fina era escasa.
De hecho, el algoritmo voraz no da una solución a un problema de cambio con un sistema monetarios genérico, sino que los valores de las monedas que hay en el sistema son específicos para que al dar el cambio lo optimo sea utilizar un algorimo voraz. Es lógico ya que es muy fácil para nosotros las personas dar el cambio eligiendo siempre la moneda de más valor que no se pase de lo que hay que devolver.
Por ejemplo, si las monedas disponibles fueran de 12, 6, 4 y 1 céntimos no funcionaría para cambio de 20 ya que seleccionaría:
12
6
1
1
y el óptimo sería
12
4
4
Un saludo.
Clasificar Dijkstra o Kruskal como algoritmos voraces no es del todo correcto. Ambos proporcionan siempre la solución correcta, lo que no ocurre con los algoritmos "voraces" clásicos.
En realidad un algoritmo voraz no es aquél que da la solución correcta de vez en cuando, sino que trabaja basándose en el principio de elegir siempre el candidato "más prometedor", y rechazarlo o anexarlo a la solución después de evaluarlo y comprobar si viola o no las restricciones del problema.
En este sentido tanto Dijkstra como Kruskal (o Prim) son algoritmos greedy, porque siempre eligen el candidato más prometedor (la arista de un grafo más corta o de menor valor)
Salu2
El algoritmo de Dijkstra ha sido siempe y será un algoritmo de programación dinámica, deberías saberlo también lo explican en ADA (aunque un poco después).
Dijktra es un algoritmo Voraz, vamos no tiene nada que ver con programación dinámica, ni necesitas probar el principio de optimalidad ni subdividir el problema, y por tanto, no necesitas utilizar resultados calculados anteriormente para hacerlo más eficiente.
Trackbacks