Capítulo 20. Algoritmos Greedy: Ejemplo de la mochila (Parte II)

Presentamos el pseudocódigo del ejemplo que resolvimos manualmente en el capítulo anterior.

Pseudocódigo

Análisis de Complejidad Temporal

Cabe señalar una importante diferencia respecto del análisis temporal para el ejemplo del cambio. Fijemos nuestra atención en el bloque 'mientras' y las condiciones:

i <= longitud(S) y capacidadParcial < P

En el peor de los casos, el bloque se ejecutará 'n' veces, siendo 'n' la cantidad de elementos en la secuencia S. Es decir, tiene mayor peso la condición i <= longitud(S) que la condición capacidadParcial < P.

Esto es así debido a que los objetos son finitos y no pueden repetirse en el armado de la solución final. Distinto era el caso en el ejemplo del cambio donde teníamos instancias infinitas de cada moneda y el objetivo era cubrir un importe P.

 

Las sentencias contenidas en el bloque 'mientras' tienen una complejidad constante dando un costo de O(n) para todo el bloque por lo explicado anteriormente.

Se observa entonces que la complejidad temporal del algoritmo dependerá del método de ordenamiento elegido para "ordenarPorBeneficioPeso". Si utilizamos MergeSort la complejidad temporal de MOCHILA_GREEDY nos queda en O(n*log(n)).

No debe sorprendernos que la complejidad en algoritmos Greedy venga dada por el método de ordenamiento utilizado ya que es la forma más eficiente que encontramos para implementar la estrategia de selección.

En el próximo capítulo haremos una ligera modificación al pseudocódigo de forma que nos permita guardar los elementos que serán almacenados en la mochila.

Fuentes:

Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda

Capítulo 19. Algoritmos Greedy: Ejemplo de la mochila (Parte I)

Continuando con los Algoritmos Greedy, centraremos nuestra atención en el ejemplo de la mochila. La descripción del problema es la siguiente:

Se tienen n objetos y una mochila con capacidad P. Cada uno de los n objetos tiene dos propiedades: peso y beneficio. Para i = 1, 2, ..., n, el objeto i tiene un peso p_i y un beneficio b_i. Tanto el peso como el beneficio son siempre positivos.

Además, los objetos pueden ser fraccionados, esto quiere decir que puedo llevar 1/2, 1/3 o cualquier otra fracción de un objeto.

Matemáticamente si una fracción x_i (0<x_i<1) del objeto i es colocada en la mochila, esta fracción contribuye en un peso x_i*p_i y en un beneficio x_i*b_i.

Para dejar en claro esto último, si tengo un objeto i cuyo peso es 12 y beneficio es 9, si decido llevar 1/3 del objeto, la contribución de este objeto al problema sería:

Peso = x_i*p_i = 1/3*12 = 4. 
Benefición = x_i*b_i = 1/3*9 = 3. 

Aclarado todo esto, el objetivo del problema es llenar la mochila de forma tal que se maximice el beneficio de los objetos transportados sin exceder la capacidad P (peso total) de la mochila.

Vamos a resolver un ejemplo de este problema en forma manual y en el siguiente capítulo lo haremos a través del pseudocódigo. Supongamos entonces que tenemos la siguiente instancia del problema:

La capacidad P de la mochila es 12 y poseemos el conjunto de elementos:

Elementos = { (p = 5; b = 4) , (p = 7; b = 5), (p = 2; b = 3), (p = 6; b = 3), (p = 4; b = 5) }

Con el fin de abreviar la nomenclatura representaremos a cada elemento e_i con el par (p_i, b_i). De esta forma, el conjunto anterior es simplemente:

Elementos = { (5,4), (7,5), (2,3), (6,3), (4,5) }

Recordemos que en los algoritmos Greedy podía identificarse una función selección, muchas veces asociada a la forma de ordenar el conjunto de elementos candidatos. En forma intuitiva, ya que el objetivo es maximizar el beneficio y los objetos pueden fraccionarse, convendría ordenar los elementos por su relación beneficio/peso en forma decreciente. Así, el conjunto de elementos ordenado por b/p nos queda:

Elementos = { (2,3), (4,5), (5,4), (7/5), (6, 3) }

Ahora, deberíamos ir tomando cada uno de estos elementos y verificar que no nos excedamos de la capacidad P de la mochila. Llamaremos W al peso parcial y B al beneficio parcial tras la elección de cada elemento (actúan como contadores).

Empecemos entonces tomando el primer elemento del conjunto ordenado, el (2,3). Nuestros contadores quedan:

W = 2
B = 3

Ya que no nos excedimos de la capacidad P, procedemos a elegir el siguiente elemento (4, 5):

W = 2 + 4 = 6
B = 3 + 5 = 8

Siendo que 6 es menor a P = 12 elegimos un tercer elemento, el (5,4):

W = 6 + 5 = 11
B = 8 + 4 = 12

El peso parcial acumulado aún no excede la capacidad de nuestra mochila, es por ello que podemos elegir un nuevo elemento: el (7,5).

W = 11 + 7 = 18 
B = 12 + 5 = 17

¿Qué ha pasado? Hemos superado la capacidad total P de la mochila. Siendo que el peso acumulado W del paso anterior era igual a 11, sólo necesitábamos contribuir en 1 para alcanzar la capacidad total. Aquí es cuando debemos fraccionar el elemento.

Es fácil ver que con la fracción 1/7 cumpliremos nuestro cometido y los acumuladores quedarán:

W = 11 + 1/7*7 = 12
B = 12 + 1/7*5 = 89/7

Todo esto realizado en forma intuitiva deriva en la solución óptima. Vale aclarar que debería demostrarse matemáticamente, cosa que excede el alcance de nuestro curso.

Esto mismo que hemos hecho manualmente, se verá plasmado en pseudocódigo en el siguiente capítulo.