Algoritmos Voraces: Problema del cambio de monedas

Los algoritmos voraces (greedy algorithms en inglés) son unas rutinas muy eficientes (O(n), O(n²)) 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:

Ejemplo 1

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:

Ejemplo 2

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 Entero

	proc inicializa()
    alg
       sol:=
       k:=0
    fin

	func fin() dev (b: Lógico)
    alg
       b:=((k=n) ó (c=0))
    fin

	proc seleccionaYElimina()
    alg
       k:=k+1
    fin

	func 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>

Más noticias sobre: Matemáticas, Programación
Comentarios (7) | Trackback

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.

#1 | Escrito por Juan José | 07 sep 2006 00:03:47

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.

#2 | ricky | 07 sep 2006 00:25:31

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.

#3 | Escrito por Zifra | 07 sep 2006 00:25:40

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

#4 | Escrito por Juanjo | 07 sep 2006 00:48:07

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).

#5 | Joselu | 08 sep 2006 02:40:31

Algoritmos Voraces: Problema del viajante con prisa

Seguimos con problemas que se pueden resolver mediante algoritmos voraces. Vamos imaginar que tenemos a una persona que desea viajar en coche desde un punto A hasta otro punto B (n kilómetros). El viajante dispone de un mapa de carretera que indica la...

#6 | Escrito por genciencia | 13 sep 2006 18:19:25

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.

#7 | Ricky | 13 sep 2006 19:33:24

¡Añade tu comentario!