ALGORITMOS PYTHON-páginas-52

Vista previa del material en texto

[240]
Figura 4. Algoritmo voraz para solucionar el cambio
Como se puede observar el conjunto solución inicialmente está vacío, luego mientras haya elemen-
tos en el conjunto de candidatos y no se llegue a una solución se procede con el algoritmo. Primero 
se selecciona el mejor candidato –para nuestro caso la moneda de mayor valor– y se verifica si 
puede formar parte de la solución. Para esto se chequea si el valor de dicha moneda es menor que 
el importe a devolver; si es así se determina cuántas monedas de ese monto se pueden utilizar y se 
agrega al conjunto solución. Y continuamos repitiendo este procedimiento hasta que no se cumpla 
una de las condiciones mencionadas previamente, finalmente evaluamos si el conjunto solución 
es una solución factible, de ser así devolvemos el conjunto solución en caso contrario el algoritmo 
devolverá None. La función solución se encarga de evaluar si la suma de los elementos almacenados 
en el conjunto soluciones es igual al importe del monto a devolver.
El algoritmo codicioso del cambio produce una solución óptima general debido a las propiedades 
de las monedas, siempre y cuando existan los valores de monedas que permitan devolver cualquier 
valor –no todos los sistemas monetarios lo tienen –. Ahora, ¿qué pasa si eliminamos las monedas de 1 y 
2 euros de nuestro sistema monetario y agregamos una de valor 0.75? Si se debe dar como vuelto 1 euro, 
la solución de nuestro algoritmo voraz es una moneda de 0.75, una de 0.2, y una de 0.05. Pero, ¿esa es 
la solución óptima? Como se habrán dado cuenta no lo es, la solución óptima es dos monedas de 0.5. 
Por eso es que el algoritmo que se diseñe también dependerá del problema y de las características 
de los elementos que forman parte del conjunto de candidatos.
Ahora veamos otro ejemplo, supongamos que debemos resolver el problema de la mochila: el mis-
mo consiste en llenar una mochila que soporta un peso máximo con un conjunto de objetos, cada 
uno de estos con un peso y un beneficio; los objetos colocados en la mochila deben maximizar el 
beneficio obtenido sin exceder el límite de peso que soporta la mochila. Este problema tiene su 
origen en los primeros trabajos del matemático Tobias Dantzig, quien hace referencia al problema 
de empacar los artículos más valiosos o útiles sin sobrecargar el equipaje.
Formalmente se puede definir el problema de la siguiente manera: se dispone de n objetos de los 
cuales supondremos cantidades x infinitas –inicialmente para simplificar el problema–, cada uno 
de dicho objetos tiene un peso p y un beneficio b, la mochila además tiene una capacidad máxi-
ma cmax. El objetivo es llenar la mochila maximizando el beneficio total obtenidos de los objetos 
almacenados, sin exceder la capacidad de la mochila. Por lo tanto, el problema se puede expresar 
matemáticamente de la siguiente manera:
[241]
Siguiendo con el ejemplo de la mochila, en la figura 5 y 6 se describe la implementación de la fun-
ción “es solución” y el algoritmo voraz para resolver el problema de la mochila, para este caso solo 
hay una unidad de cada elemento, no son infinitos ni fraccionables. Como pueden observar las 
funciones son muy similares a las utilizadas en el problema del cambio dado que la estrategia es 
la misma.
Figura 5. Función es solución para el algoritmo ávido de la mochila
Figura 6. Algoritmo ávido para el problema de la mochila
Como ya se mencionó previamente la función que selecciona el mejor candidato del conjunto de 
soluciones es quizás el punto crítico para que el algoritmo logre encontrar una solución óptima, 
para este caso particular de los elementos almacenados en el conjunto de candidatos se conoce: 
nombre, peso y beneficio. Entonces lo que podemos hacer es agregar un nuevo valor, que es be-
neficio dividido el peso del elemento, para poder obtener una medida del beneficio del elemento 
respecto de su peso. Luego ordenamos el vector de candidatos de menor a mayor tomando como 
criterio de orden este nuevo valor –es decir que al final del vector estarán los elementos con mejor 
[242]
relación beneficio-peso. Esto le permite al algoritmo en cada iteración tomar el elemento con mejor 
relación beneficio -peso para agregarlo al conjunto solución, siempre y cuando no se exceda la capa-
cidad máxima de la mochila. Cabe aclarar que a diferencia del caso anterior puede que no se utilice 
toda la capacidad de la mochila, es decir, que seguramente quedará un sobrante de capacidad dis-
ponible dado que los elementos son fraccionables.
Para este caso en particular el problema a resolver es poner en el portatermo (mochila) los ele-
mentos que nos brinden mayor beneficio. La implementación de lo mencionado anteriormente se 
puede apreciar en la figura 7.
Figura 7. Conjunto de elementos válidos y criterio de orden
En resumen, el esquema voraz es una estrategia heurística que no siempre conduce a la solución 
óptima, es muy útil cuando la solución óptima general puede construirse a partir de la selección 
de óptimos locales que se toman en cada paso sin depender de las futuras selecciones. Podríamos 
decir que esta estrategia voraz es del tipo top-down tomando una decisión voraz tras otra –es decir 
comiendo la mejor parte en cada etapa– reduciendo iterativamente el problema.
Divide y vencerás, también aplica 
al diseño de algoritmos
 Esta es quizás una de las técnicas más importantes y utilizadas para el diseño de algoritmos eficien-
tes, la cual consiste en descomponer un problema de tamaño n en subproblemas más pequeños 
del mismo problema –hasta que el problema se vuelva muy sencillo y la solución sea muy obvia–. 
Luego se resuelve cada subproblema de manera independiente de los demás y a partir de la so-
lución de cada uno de estos, se combinan para construir la solución al problema completo. Cabe 
aclarar que esta técnica se aplica de manera recursiva o mediante el uso de pilas para sustituir las 
llamadas recursivas.