Algoritmos Voraces

Tal y como indica su nombre estos algoritmos intentan buscar la solución desde el primer momento. El enfoque que utilizan es ir construyendo la solución en cada paso.

Este tipo de algoritmos es muy empleado en los llamados problemas de optimización. Son problemas que a partir de una colección de elementos tratan de obtener un subconjunto de los mismo que optimice la consecución del objetivo. En algunos caso se trata de obtener un orden entre los elementos de entrada con el fin de optimizar una medida. Ejemplos de este tipo de problemas donde aplicar esta técnica son:

• Tenemos un ascensor capaz de transportar un máximo de kilos k y tenemos un grupo de personas cuyos pesos suman más de la capacidad del ascensor. El problema sería llenar el ascensor con el máximo número de pasajeros sin sobrepasar su capacidad
  
  
• ¿Cómo podemos grabar una cinta de música de manera que el orden de grabación nos permita minimizar el tiempo de acceso a las canciones?
  

El esquema que va a seguir la técnica voraz es ir construyendo una solución parcial y evaluando qué elemento de entre el conjunto de candidatos añadir en el siguiente paso. Para ello se ayudará de una función de selección que en el caso del ascensor podría ser tan sencilla como "escoger el más ligero". Esta función ha de diseñarse de forma que garantice la obtención de la solución óptima, sin prejuicio de que existan más de una. Los algoritmos voraces nunca rectifican: una vez que un elemento de la entrada ha pasado a formar parte de la solución, permanece como integrante de ésta hasta que el algoritmo termina.

Como se puede observar, una vez seleccionado el candidato y tras haber comprobado que añadido a la solución parcial construida es una solución válida, se añade este a la misma. Se continúa seleccionando candidatos. Este proceso acaba cuando ya no quedan candidatos del conjunto de elementos de entrada ó cuando se ha alcanzado una solución.

El problema de la mochila es el ejemplo típico de problemas de optimización, que puede resolverse eficientemente mediante la técnica voraz. Tenemos una mochila y una serie de objetos que queremos meter en la mochila. El número de objetos que podemos meter en la mochila está limitado por la capacidad (C) de la mochila y el peso de cada uno de los objetos (Pi). Sin embargo daremos más importancia a unos objetos sobre otros, otorgándoles a cada objeto i = 1, .., n un peso Wi = W1, ..., Wn.

Tendremos por tanto dos vectores:

• Vector de pesos: [P1, ..., Pn]
  
  
• Vector de precios: [B1, ..., Bn]
  
  

Podremos meter en la mochila los objetos enteros o fracciones de los mismos (vector de fracciones [X1, ..., Xn]). El objetivo final es encontrar este vector, donde cada Xi expresa la fracción del objeto i-ésimo que se introduce en la mochila de forma que maximize la función

Supondremos que la suma de los pesos de todos los objetos es mayor que la capacidad máxima de la mochila. Por tanto, la solución que encontremos deberá incluir el máximo de objetos ó fracciones sin sobrepasar esta capacidad. Detectaremos que hemos alcanzado esta solución cuando se cumpla que:

es decir, que se ha llenado completamente la mochila

Para encontrar la solución óptima es importante elegir adecuadamente la función de selección. Plantearemos a continuación tres criterios para ir construyendo la solución:

• Escoger en cada momento el objeto más caro, con mayor precio Bi.
  
  
• Escoger el objeto menos pesado para que me quede espacio para mas cosas.
  
  
• Elegir el objeto que ofrece mayor relación precio/peso.
  

Con el siguiente ejemplo veremos que criterio utilizaremos. Si tenemos una mochila con capacidad, C = 14 y con el siguiente vector de pares (peso, precio):

( (10, 30), (4, 8), (6, 24) )

Las soluciones generadas por los tres criterios son:

• Criterio 1: (1, 0, 4/6), peso del contenido: 46
  
  
• Criterio 2: (4/10, 1, 1), peso del contenido: 44
  
  
• Criterio 3: (8/10, 0, 1), peso del contenido: 48
  
  

Veamos ahora una implementación imperativa del algoritmo. Supondremos, con objeto de facilitar la elección del siguiente objeto, que los elementos estarán ordenados en función de la relación beneficio/peso.

La variable resto indica en todo momento la capacidad aún no completada de la mochila. Se inicializa el vector de fracciones todo a cero. Dentro del bucle cuando el peso del elemento no sobrepasa la capacidad restante se introduce completamente en la mochila. En caso de que no quede capacidad suficiente se introduce la fracción correspondiente.