05/04/2019Artículo original

Este artículo se basa en las prácticas que he hecho para una asignatura llamada Algorítmica. Dichas prácticas consistían en realizar el problema de la Mochila usando las técnicas algorítmicas que veíamos en la asignatura.

¿En qué consiste el problema de la mochila? Tenemos una mochila con una determinada capacidad y un conjunto de objetos para meter en la mochila. Cada objeto tiene asociado un peso y un beneficio. El problema consiste en llenar la mochila de tal forma que el beneficio obtenido sea el máximo.

Las distintas técnicas algorítmicas que hemos usado para implementar este problema han sido:

Algoritmos voraces

Los algoritmos voraces son la idea más intuitiva y fácil de implementar: tenemos una colección de objetos candidatos a solución, unas determinadas condiciones que debe cumplir la solución y un conjunto de objetos solución, que es un subconjunto de la primera colección de objetos. El ejemplo que me dieron en clase fue el siguiente: vamos al súper a comprar 2kg de patatas. Vamos cogiendo patatas que nos gusten y las vamos echando a la bolsa hasta llegar a los 2 kg. Con este tipo de algoritmos no examinamos toda la colección de objetos candidatos, por eso son bastante rápidos. El inconveniente que tienen es que tampoco nos dan la solución óptima, aunque dan aproximaciones bastante buenas.

En el caso del problema de la mochila, se implementaría de la siguiente forma:

Ordenamos nuestro conjunto de objetos candidatos (una lista de objetos con un peso y un beneficio) de mayor cociente $$\frac{beneficio}{peso}$$ al menor.
Vamos cogiendo objetos hasta llenar la mochila.
Ahora tenemos dos opciones: si el siguiente objeto ya no cabe completo en la mochila podemos quedarnos con una fracción de él (obteniendo un beneficio igual a $$(pesototal – pesoactual)/pesoobjeto$$) o no meter ningún objeto más en la mochila. La primera opción se la conoce como mochila fraccional y la segunda, como mochila 0/1.

list<float>Mochila(intlim_peso,list<Objeto>&objetos){list<float>sol;intpeso_actual=0;list<Objeto>::iteratorit;for(it=objetos.begin();it!=objetos.end()&&lim_peso>peso_actual;++it){if((peso_actual+(*it).peso)<=lim_peso){sol.push_back(1);peso_actual+=(*it).peso;}else{sol.push_back((lim_peso-peso_actual)/((*it).peso));peso_actual=lim_peso;}}while(it!=objetos.end()){sol.push_back(0);++it;}returnsol;}

Así obtenemos una lista donde especificamos qué fracción de cada objeto de nuestra lista inicial hemos tomado para la solución.

Programación dinámica

La programación dinámica es, por decirlo de una forma intuitiva, una manera iterativa de implementar algoritmos recursivos. Además tiene una ventaja sobre la recursividad: no repetimos operaciones ya hechas, sino que todos los cálculos que hacemos, los vamos guardando en una tabla y así nos ahorramos un montón de operaciones (piensa en el árbol recursivo que sale al implementar Fibonacci de manera recursiva).

El developer feliz: qué buscamos y qué necesitamos

En el problema de la mochila, la ecuación recursiva que deberíamos seguir sería la siguiente:

\[\text{Mochila(k,m) =}\begin{cases}0 & \text{si } k = 0 \text{ ó } m = 0,\newline-\infty & \text{si } k<0 \text{ ó } m<0\newlinemax{Mochila(k-1,m), b_k + Mochila(k-1,m-p_k)}\end{cases}\]

Es decir, el caso base sería o bien no tener ningún objeto ($$k = 0$$) o que el peso de nuestra mochila sea 0 ($$m = 0$$). El caso general sería quedarnos con lo que más beneficio nos dé: o coger el objeto ($$Mochila (k-1, m-p_k)$$) o no cogerlo ($$Mochila(k-1, m)$$).

Con esta función rellenamos la tabla de beneficios, pero no sabemos qué objetos cogemos y cuáles no.

vector<vector<unsigned>>Mochila(vector<Elemento>&elems,unsignedm){unsignedi=0,j=0;vector<vector<unsigned>>V(elems.size()+1);// inicializamos los casos basefor(i=0;i<=elems.size();i++){V.at(i).resize(m+1);V.at(i).at(0)=0;}for(j=0;j<=m;j++)V.at(0).at(j)=0;// rellenamos la tablafor(i=1;i<=elems.size();i++){for(j=1;j<=m;j++){// el objeto no cabe en la mochilaintaux=j-elems[i-1].peso;if(aux<0)V.at(i).at(j)=V.at(i-1).at(j);else{unsignedben=elems.at(i-1).beneficio+(V.at(i-1).at(j-elems[i-1].peso));V.at(i).at(j)=Max(V.at(i-1).at(j),ben);}}}returnV;}

Para saber qué objetos cogemos y cuáles no, usamos la siguiente función:

vector<unsigned>Solucion(vector<vector<unsigned>>&mochila,vector<Elemento>&elems){vector<unsigned>sol(elems.size());intj=mochila.at(0).size()-1;for(inti=mochila.size()-1;i>0;i--){if(mochila.at(i).at(j)==mochila.at(i-1).at(j))sol.at(i-1)=0;else{// if (mochila.at(i).at(j) == mochila.at(i-1).at(j.elems[i-1].peso))+elems[i-1].beneficio)sol.at(i-1)=1;j-=elems[i-1].peso;}}returnsol;}

Branch & Bound

Los algoritmos Branch & Bound, a partir de un árbol de soluciones, funcionan de la siguiente manera: a partir de una cota inferior (que determina lo mínimo que podemos encontrar si vamos por esa rama del árbol) y una cota superior (que determina lo máximo que podemos encontrar en esa rama) van podando (según estemos maximizando o minimizando) ramas de manera que, cuanta más precisión tengamos estimando cotas, menos nodos del árbol exploraremos.

En el problema de la mochila, para estimar las cotas podemos hacer lo siguiente:

Para hacer la cota superior, usamos un algoritmo voraz fraccional + la suma de los beneficios de los objetos que hemos seleccionado hasta el momento
Para hacer la cota inferior, lo mismo pero con un algoritmo voraz 0/1.

Así, la función para explorar el árbol sería la siguiente:

vector<bool>Mochila(list<Elemento>&elementos,unsignedm){Nodoinic=NodoInicial(elementos,m);intC=inic.CI;priority_queue<Nodo>LNV;LNV.push(inic);ints=numeric_limits<int>::min();vector<bool>resultado;while(!LNV.empty()){Nodox=LNV.top();LNV.pop();if(x.CS>=C){for(unsignedk=0;k<2;k++){boolelec=(k==0)?false:true;Nodoy=Generar(x,elec,elementos,m);if(y.nivel==elementos.size()-1&&y.valor_actual>s){s=y.valor_actual;C=(C>=s)?C:s;resultado=y.tupla;}elseif(y.nivel<elementos.size()-1&&y.CS>=C){C=(C>=y.CI)?C:y.CI;LNV.push(y);}}}}returnresultado;}

Como véis, no generamos todo el árbol, sino que vamos generando nodos sobre la marcha según vamos explorando. La función para generar un nodo es:

NodoGenerar(Nodo&nodo_actual,booleleccion,list<Elemento>&objs,doublem){Nodores=Nodo(0,0,nodo_actual.nivel+1,0,0,nodo_actual.tupla);// cogemos el objeto que estamos considerandolist<Elemento>::iteratorobj_it=objs.begin();for(intk=0;k<res.nivel;k++)++obj_it;// generamos una lista con los objetos restantes que procesara el greedylist<Elemento>aux;list<Elemento>::iteratorax=obj_it;++ax;for(list<Elemento>::iteratora=ax;a!=objs.end();++a){aux.push_back(*a);}res.tupla.at(res.nivel)=eleccion;if(!eleccion){res.valor_actual=nodo_actual.valor_actual;res.peso_actual=nodo_actual.peso_actual;}else/*if (eleccion)*/{res.valor_actual=nodo_actual.valor_actual+(*obj_it).beneficio;res.peso_actual=nodo_actual.peso_actual+(*obj_it).peso;}res.CI=res.valor_actual+Greedy01((m-res.peso_actual),aux);res.CS=res.valor_actual+GreedyFraccional((m-res.peso_actual),aux);if(res.peso_actual>m){res.CI=numeric_limits<int>::min();res.CS=numeric_limits<int>::min();res.valor_actual=numeric_limits<int>::min();}returnres;}

La solución de nuestro programa sería la tupla del último nodo que exploremos.

Ejemplos de ejecución con cada algoritmo

Tras ver por encima en qué consiste cada algoritmo, vamos a pasar a ejecutar cada uno con un mismo ejemplo y ver las diferencias en tiempos de ejecución y en el resultado obtenido.

Chaos Engineering: ¿resistirían tus servidores en la nube el ataque de un ejército de monos locos?

El ejemplo a usar será el siguiente: Tenemos una mochila con una capacidad de 11 kg y los siguientes objetos:

Un objeto con peso 6 y beneficio 3
Un objeto con peso 4 y beneficio 2
Un objeto con peso 3 y beneficio 7
Un objeto con peso 2 y beneficio 4

Solución con Algoritmos Voraces

La salida que obtenemos en terminal es la siguiente:

[marta@marta-PC BaulP]$ ./mochila_voraz 7342243611La proporcion de cada uno que cogemos es:Peso: 3 Beneficio: 7(2.33333) -> 1Peso: 2 Beneficio: 4(2) -> 1Peso: 4 Beneficio: 2(0.5) -> 1Peso: 6 Beneficio: 3(0.5) -> 0.333333El beneficio total es, por tanto 14Tiempo: 8e-06

Este resultado tiene un pequeño problema, tenemos dos objetos con la misma proporción $$\frac{beneficio}{peso}$$ por lo tanto se queda con el primero que entramos por terminal (el objeto con beneficio 2 y peso 4), pero sin embargo, obtendríamos mayor beneficio si usásemos el objeto con beneficio 3 y peso 6.

Solución con Programación dinámica.

La salida obtenida en terminal es la siguiente:

[marta@marta-PC BaulP]$ ./mochila_din 734224361101234567891011----------------------------------------------------------------------------------------------0|0000000000001|0007777777772|00477111111111111113|00477111111111313134|0047711111111131314Los objetos utilizados son:Usamos el objeto Peso: 3 Beneficio: 7Usamos el objeto Peso: 2 Beneficio: 4NO usamos el objeto Peso: 4 Beneficio: 2Usamos el objeto Peso: 6 Beneficio: 3Tiempo: 3e-06

La tabla obtenida debemos interpretarla de la siguiente forma:

Las filas representan los objetos que tenemos
Las columnas, pesos de la mochila

Así, por ejemplo, si nos fijamos en la posición de la tabla fila 3, columna 4 tendremos un beneficio de 7. Esta solución sólo tiene en cuenta que tenemos una mochila con peso 3 y que sólo tenemos los 2 primeros objetos que insertamos por terminal. Así, la tabla va creciendo añadiendo cada vez más peso y más objetos hasta llegar a la esquina inferior derecha (en este caso fila 5 y columna 12) donde tendremos el beneficio total obtenido con el peso que le hemos dado a la mochila y teniendo en cuenta todos los objetos.

Como vemos en la tabla obtenemos “el mismo” beneficio que con algoritmos voraces, pero en realidad, no es así, ya que con algoritmos voraces cogemos una pequeña parte del objeto con beneficio 3 y peso 6 cuando en realidad eso nunca se hace (imagina que pides una guitarra y te traen un día las cuerdas, otro día el mástil y así…).

Por tanto, con programación dinámica hemos afinado bastante la solución obtenida con algoritmos voraces, hasta el punto de llegar a tener la solución óptima.

Los programadores open source están hartos: quieren que las empresas que se benefician de su trabajo gratuito empiecen a pagar

Solución con Branch & Bound

La salida obtenida por terminal es la siguiente:

[marta@marta-PC BaulP]$ ./mochila_bb 7342243611Peso de la mochila: 11Los objetos utilizados son:Usamos el objetoBeneficio=7Peso=3Usamos el objetoBeneficio=4Peso=2Usamos el objetoBeneficio=3Peso=6Tiempo: 2.7e-05

De nuevo hemos obtenido la solución óptima al problema. En esta versión, el tiempo es un poco mayor a las demás, pero éste siempre dependerá de cómo establezcamos las cotas y del número de nodos del árbol que exploremos.

Los tiempos de ejecución obtenidos no son comparables del todo, pues hemos usado un ejemplo con muy pocos objetos y además, sólo hemos hecho una ejecución, por lo que alguno de los tiempos podría haberse visto afectado por una interrupción del sistema operativo.

Conclusión

Estas técnicas algorítmicas clásicas nos sirven para encontrar la solución al problema de la mochila en un tiempo razonable. Aunque en el caso del algoritmo voraz, en este problema (dependiendo de los objetos de entrada) nos da una solución aproximada u óptima. Branch & Bound y Programación Dinámica nos aseguran la solución óptima pero tienen sus pros y sus contras:

La programación dinámica, al usar una matriz para guardar los valores que va calculando, está limitada por el tamaño de la memoria de nuestro ordenador
En Branch & Bound, si no definimos una buena estrategia de cotas y de poda, exploraremos muchísimos nodos y el tiempo de ejecución se nos subirá por las nubes.