Introducción
Ámbito de aplicación: problema de OPTIMIZACIÓN
sujeto a unas RESTRICCIONES,
con una FUNCIÓN OBJETIVO conocida y explícita, y
donde la estrategia de solución se basa también en la TOMA SECUENCIAL DE DECISIONES
El esquema VORAZ ofrece menos dificultad que otros esquemas para generar el algoritmo solución. De hecho, son los más fáciles. No hay necesidad de evaluar alternativas, ni de emplear sofisticados procedimientos de seguimiento que permitan deshacer las decisiones anteriores:
MIOPE, toma decisiones basándose en la información que tiene disponible de modo inmediato, sin tener en cuenta los efectos que esas decisiones puedan tener en un futuro.
TOZUDO, ya que una vez tomada esa decisión (sea la que fuera) ya no ofrece la posibilidad de reconsiderarla.
Estrategia:
En cada decisión, a partir de la información disponible, eligen la mejor opción.
Lo hacen de acuerdo a un criterio tan razonable como sea posible.
¿Qué sucede?: esa mejor opción lo es de acuerdo a ese criterio razonable, pero no podemos garantizar que corresponda a la solución óptima final.
Ventajas:
De fácil diseño e implementación
Cuando funcionan, suelen ser algoritmos muy eficientes
Desventaja:
Como no todo es tan sencillo, hay muchos problemas que no se pueden resolver correctamente con un enfoque tan simple
Ejemplo: Devolver cambio
Supongamos que somos el empleado de una tienda y que tenemos que devolver un cambio a un cliente por importe de N €.
Para ello disponemos de tres tipos de monedas:
1€,
2€ y
5€.
Se supone que en caja hay un número inagotable de monedas de cada tipo.
Nos hemos fijado el objetivo de minimizar el número de monedas incluidas en el cambio.
La solución se plantea como una secuencia de decisiones.
Función objetivo: utilizar el menor número de monedas para componer la cantidad N euros.
Y las condiciones de factibilidad son:
En todo momento la cantidad “construida” debe ser menor o igual que N.
Y finalmente, claro está, debe de ser N.
Estrategia Voraz.- elegir en cada etapa el tipo de moneda de mayor valor.
Ejemplo: N = 18€ y Tipos de monedas = { 1€, 2€, 5€ }
No puede generalizarse, pues depende del sistema monetario.
Es fácil convencerse, pero difícil de probar formalmente, que con los valores dados para las monedas y disponiendo de un suministro adecuado de cada tipo de moneda, esta estrategia que acabamos de mostrar siempre produzca la solución óptima.
Sin embargo, con una serie de valores de monedas diferentes, o si el suministro de alguna moneda está limitado, esa estrategia voraz puede no funcionar.
En algunos casos, puede seleccionar un conjunto de monedas que no sea óptimo, mientras que quizás en otros casos no llegue a encontrar ninguna solución aún cuando esta exista.
Ejemplo: N = 36€ y Tipos de monedas = { 1€, 5€, 12€, 25€ }
¡¡ SOLUCIÓN NO ÓPTIMA !! con la estrategia voraz
siendo la SOLUCIÓN ÓPTIMA: 3 monedas ( 3 de 12€ )
Ejemplo: N = 36€ y Tipos de monedas = { 5€, 12€, 25€ }
Cuando sí que hay solución, siendo ésta además de la SOLUCIÓN ÓPTIMA: 3 monedas ( 3 de 12€ )
Demostrar con generalidad si la solución voraz en el problema de devolver el cambio es óptima o no, es un problema complejo que no abordaremos aquí.
Hemos visto que dependiendo de los tipos de monedas disponibles el algoritmo voraz puede no funcionar de la manera esperada ya que:
en algunos casos puede seleccionar un conjunto de monedas que no sea óptimo y
en otros casos puede no llegar a encontrar la solución, aún cuando ésta sí que exista.
Ocurre lo mismo si el suministro de alguno de los tipos de monedas es limitado.
Resumen de la estrategia
Funcionamiento por etapas (BUCLE).
En cada etapa (iteración) seleccionamos el tipo de moneda de mayor valor.
Una vez seleccionado un tipo de moneda:
Se añade a la solución siempre y cuando su valor sea menor o igual que la cantidad a devolver o
Se rechaza si su valor es mayor ya que sino la solución no cumpliría las restricciones del problema
Una vez seleccionado un tipo de moneda, pase o no a formar parte de la solución, no se vuelve a seleccionar en etapas (iteraciones) posteriores (decisiones irrevocables). Se genera una ÚNICA secuencia de decisiones.
Función Devolver_cambio ( N : entero) retorna ( S : conjunto de monedas)
C = { 1, 5, 12, 25 } # C es el sistema monetario disponible
cantidad = N # cantidad es (y será) la cantidad que falta por cubrir
C = C - { x }
si cantidad ≥ x entonces
y = cantidad / x # división entera
cantidad = cantidad - x * y
fsi
fmientras
ffuncion
Last updated
