Problema de la Mochila

Problema de la Mochila

El Problema de la Mochila (conocido también como Knapsack Problem o simplemente KP) es un problema clásico de la Investigación de Operaciones y en particular de la Programación Entera. Consiste en un excursionista que debe preparar su mochila, la cual tiene una capacidad limitada y por tanto no le permite llevar todos los artículos que quisiera tener en la excursión. Cada artículo que el excursionista puede incluir en la mochila le reporta una determinada utilidad. Luego el problema consiste en seleccionar un subconjunto de objetos de forma tal que se maximice la utilidad que el excursionista obtiene, pero sin sobrepasar la capacidad de acarrear objetos. 

La programación dinámica nos ayuda a optimizar los problemas sin verificar todos los casos posibles, pues van a aquellos  que mejor lo resuelven, para el algoritmo de la mochila lo que queremos es  llenarla con objetos que sea muy valiosos y de menor peso.

ejemplo: ingreso n: cantidad de objetos y Cap: capacidad máxima de la mochila

Los datos del problema se pueden expresar en términos matemáticos. 

• Los objetos están numerados por el índice i variando de 1 a n. 
• Los números wi y pi representan el peso y el valor del número i. 
• La capacidad de la bolsa se denomina en esta formula W.

Existen muchas manera de llenar la mochila, para decidir a cada uno de ellos debemos de decir para cada objeto si lo metemos a la mochila o no, pudiendo utilizar el código binario que cuando xi = 1, metemos el objeto a la mochila, o xi = 0, se pone afuera, y para ir llenando esta mochila podemos utilizar un vector de contenido, que comprende: X = (x1, x2, ..., xn), entonces podemos expresar una función del contenido del vector.

Para un contenido dado X, el valor total de la bolsa es:

De la misma manera, la suma de los pesos de los objetos es:

El problema entonces lo podemos enunciar como un contenido de vectores X = (x1, x2, ..., xn), que tienen componentes de ceros y unos, teniendo como máximo la restricción de la función z(X).

Esto quiere decir que la suma de los pesos (o sea, la función w(X)), de los objetos que pusimos en la mochila no deben de superar la capacidad de esta, (o sea, la W).

Podemos decir que:

• z(X) es una función objetivo (como su nombre lo dice, representa el objetivo del problema, esta expresión se maximiza o se minimiza.
• Un vector X que cumple con la restricción W en la tercera formula se le nombra factible (o sea, que se pude hacer).
• Si tenemos un resultado máximo en z(X), entonces X es óptimo.

Se le pueden agregar otras restricciones según tengamos un caso, en esta liga, encontramos diferentes casos singulares.

Con esto podemos argumentar que tenemos un problema de decisión cuando para decidir a cada uno de ellos debemos de decir para cada objeto si lo metemos a la mochila o no, que cuando xi = 1, metemos el objeto a la mochila, o xi = 0, se pone afuera y podemos decir que es un problema de optimización porque podemos encontrar funciones objetivo, valores óptimos utilizando las declaraciones matemáticas.

El problema es NP-completo porque se puede representar como una toma de decisiones mediante el reemplazo del máximo, utilizando la siguiente pregunta: 

Dado el número k, existe un valor xi para el cual  

Existe un vinculo entre la version de decisión y la version de optimización del problema en que si existe un algoritmo polinomial que resuelve la versión de decisión,  por lo tanto, las dos versiones del problema son de dificultad similar.

El problema de optimización es NP-hard, su resolución es al menos tan difícil como el problema de decisión.

La prueba de que el problema es NP-completo fue presentado por Michail G. Lagoudakis, se puede encontrar en la misma liga

Algoritmos existentes

Algoritmo Greddy o voraz: La idea es añadir un objeto prioritario mas efectivo hasta la saturación de la mochila. La complejidad de estos algoritmos se basa en la inversa de la calidad esperada.

Las dos fases del algoritmo voraz

Podemos ver las dos fases del algoritmo voraz.
      A) el ordenamiento de las cajas según un interes (en este caso en peso en $/kg)
      B) si es posible la entrar a la mochila.  


Algoritmo genético: se utiliza a menudo en problemas de optimización difíciles, como este, facil de implementar y obtener rapidamente una solución.

 

Ejemplo de la evolución de una población con
un algoritmo genetico.

Los objetos son utilizados para el algoritmo voraz, por ejemplo el genoma (0,1,0,0,0) corresponde a un cuadro de selección de 12 kg de peso 7.


Programación dinámica: El problema de la mochila tiene la propiedad que le permite utilizar el metodo de resolución de programación dinámica.
Este algoritmo tiene una complejidad en tiempo y espacio que tiene como ventajas la velocidad y no hay necesidad de ordenar las variables, pero como desventajas es que gasta mucha memoria, por lo tanto no puede ser solución para problemas grandes.

Aplicaciones en la vida real

En la vida real, se utiliza para modelar diferentes situaciones:

• en los sistemas de apoyo a las finanzas: para encontrar el mejor equilibrio entre el capital y rendimiento financiero.
• en la carga del barco o avión: todo el equipaje debe ser llevado, sin ser sobrecargado.
• en el corte de materiales: para minimizar las caídas.
• entre otras...

Referencias

El Problema de la mochila, Universidad de Murcia. aqui.
Diapositivas de la clase: Optimización combinatoria. aqui.
Lecture: The knapsack problem. Technische Universiteit Eindhoven. aqui.
Reducibility among combinatorial problems de Richard M. Karp. aqui.
Encontré mucha información. aqui.

Videos

https://youtu.be/ZGD7te3FntI

Algoritmo Código de Huffman

El término se refiere al uso de una tabla de códigos de longitud variable para codificar un determinado símbolo (como puede ser un carácter en un archivo), donde la tabla ha sido rellenada de una manera específica basándose en la probabilidad estimada de aparición de cada posible valor de dicho símbolo. Fue desarrollado por David A. Huffman mientras era estudiante de doctorado en el MIT, y publicado en "A Method for the Construction of Minimum-Redundancy Codes".

El algoritmo de construcción del árbol puede resumirse así:

1. Crear un nodo hoja para cada símbolo, asociando un peso según su frecuencia de aparición e insertarlo en la lista ordenada ascendentemente.
2. Mientras haya mas de un nodo en la lista:
   1. Eliminar los dos nodos con menor probabilidad de la lista
   2. Crear un nuevo nodo interno que enlace a los nodos anteriores, asignándole como peso la suma de los pesos de los nodos hijos.
   3. Insertar el nuevo nodo en la lista, (en el lugar que le corresponda según el peso).
3. El nodo que quede es el nodo raíz del árbol.

Github

https://github.com/ingenierajessica/Algoritmos/blob/master/Algoritmo%20Greedy%20C%C3%B3digos%20de%20Huffman.ipynb

Material de apoyo

Material de Apoyo

Algoritmo de Huffman (clic aquí)

Quick Sort

QuickSort (en inglés, ordenamiento rápido). Es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

Descripción del algoritmo

El algoritmo consta de los siguientes pasos:

1. Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
2. Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
3. La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
4. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Eficiencia del algoritmo

La eficiencia del algoritmo depende de la posición en la que termine el pivote elegido. En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n•log n). En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente. En el caso promedio, el orden es O(n•log n). Y no es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.

Github

El código de esté algoritmo se puede consultar en la siguiente ruta:

https://github.com/ingenierajessica/Algoritmos/blob/master/Quick%20Sort.ipynb

Demostración

Suponiendo que el número total de elementos a ordenar es potencia de dos, es decir, n = 2k. De aquí podemos ver que k = log2(n), donde k es el número de divisiones que realizará el algoritmo.

En la primera fase del algoritmo habrán n comparaciones, en la segunda fase el algoritmo creará dos sublistas aproximadamente de tamaño n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n.

En conclusión, el número total de comparaciones que hace el algoritmo es:

n + n + n + ..... + n = kn, donde k = log2(n), por tanto el tiempo de ejecución del algoritmo en el mejor caso es O(n.log2n)

Optimización del algoritmo

Cabe destacar que de usarse en su versión recursiva las siguientes optimizaciones y sus desventajas no se ven vistas en el tiempo de ejecución del mismo manteniéndose, así el tiempo de ejecución planteado en un principio.

Técnicas de elección del pivote

El algoritmo básico del método Quicksort consiste en tomar cualquier elemento de la lista al cual denominaremos como pivote, dependiendo de la partición en que se elija, el algoritmo será más o menos eficiente.
Tomar un elemento cualquiera como pivote tiene la ventaja de no requerir ningún cálculo adicional, lo cual lo hace bastante rápido. Sin embargo, esta elección «a ciegas» siempre provoca que el algoritmo tenga un orden de O(n²) para ciertas permutaciones de los elementos en la lista.
Otra opción puede ser recorrer la lista para saber de antemano qué elemento ocupará la posición central de la lista, para elegirlo como pivote. Esto puede hacerse en O(n) y asegura que hasta en el peor de los casos, el algoritmo sea O(n•log n). No obstante, el cálculo adicional rebaja bastante la eficiencia del algoritmo en el caso promedio.
La opción a medio camino es tomar tres elementos de la lista - por ejemplo, el primero, el segundo, y el último - y compararlos, eligiendo el valor del medio como pivote.

Técnicas de reposicionamiento

Una idea preliminar para ubicar el pivote en su posición final sería contar la cantidad de elementos menores que él, y colocarlo un lugar más arriba, moviendo luego todos esos elementos menores que él a su izquierda, para que pueda aplicarse la recursividad.

Existe, no obstante, un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos índice izquierdo, y j, al que llamaremos índice derecho. El algoritmo es el siguiente:

Recorrer la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento). Cuando lista[i] sea mayor que el pivote y lista[j] sea menor, se intercambian los elementos en esas posiciones.

Repetir esto hasta que se crucen los índices.
El punto en que se cruzan los índices es la posición adecuada para colocar el pivote, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados).

Funcionamiento

1. Se debe llamar a la función Quicksort desde donde quiera ejecutarse.
2. Ésta llamará a colocar pivote para encontrar el valor del mismo.
3. Se ejecutará el algoritmo Quicksort de forma recursiva a ambos lados del pivote.

Implementación

int colocar(int *v, int b, int t){
 int i;
 int pivote, valor_pivote;
 int temp;
 pivote = b;
 valor_pivote = v[pivote];
 for (i=b+1; i<=t; i++){
  if (v[i] < valor_pivote){
  pivote++; 
  temp=v[i];
  v[i]=v[pivote];
  v[pivote]=temp;
  }
 }
 temp=v[b];
 v[b]=v[pivote];
 v[pivote]=temp;
return pivote;
} 
void Quicksort(int* v, int b, int t){
 int pivote;
 if(b < t){
 pivote=colocar(v, b, t);
 Quicksort(v, b, pivote-1);
 Quicksort(v, pivote+1, t);
 } 
} 

Nota: Los tres parámetros de la llamada inicial a Quicksort serán array[0], 0, numero_elementos -1, es decir, si es un array de 6 elementos array[0], 0, 5

Referencias

• Curso de programación II, Universidad de Ciencias Informáticas.
• PEÑA M., Ricardo. Diseño de programas. Formalismo y abstracción. Prentice-Hall, 1998.
• WEISS, M. A., Estructuras de datos y algoritmos. Addison-Wesley Iberoamericana, 1995.
• WIRTH, Niklaus. Algoritmos y Estructuras de Datos. Pentice Hall, 1987.

Algoritmo DFS

Github

https://github.com/ingenierajessica/Algoritmos/blob/master/Algoritmo%20DFS.ipynb

Descripción

El algoritmo de búsqueda que se explicará a continuación es Depth First Search ( DFS ) se explicará el algoritmo de manera similar a como se hizo BFS, proponiendo problemas y otorgando códigos del algoritmo en si.

El algoritmo DFS posee varias aplicaciones la mas importante es para problemas de conectividad,  si un grafo es conexo, detectar ciclos en un grafo,  numero de componentes conexas,  etc y es bastante útil en otro algoritmos como para hallar las componentes fuertemente conexas en un grafo ( Algoritmo de Kosaraju, Algoritmo de Tarjan), para hallar puntos de articulación o componentes biconexas ( puentes ),  para recorrido en un circuito o camino euleriano, topological sort, flood fill y otras aplicaciones.

Como trabaja

DFS va formando un árbol al igual que BFS pero lo hace a profundidad. Existen dos formas de hacer el recorrido una es usando una Pila y otra de manera recursiva:

Usando Stack

El concepto es el mismo que BFS solo que se cambia la Cola por una Pila, el proceso es como sigue: visitar el nodo inicial y ponerlo en la pila, ahora para ver los siguientes nodos a visitar sacamos el nodo tope de la pila y vemos sus adyacentes, los que no han sido visitados los insertamos en la pila. El proceso se repite hasta que la pila se encuentre vacía ( se han visitado todos los nodos ).

Algoritmo en pseudocodigo:

1  método DFS( origen):
2      creamos una pila S
3      agregamos origen a la pila S
4      marcamos origen como visitado
5      mientras S no este vacío:
6          sacamos un elemento de la pila S llamado v
7          para cada vertice w adyacente a v en el Grafo: 
8              si w no ah sido visitado:
9                 marcamos como visitado w
10                 insertamos w dentro de la pila S

Usando Recursión

Usar la recursión es mucho mas fácil y ademas muy útil, es la forma mas usada en la solución de problemas con este algoritmo.

Algoritmo en pseudocódigo:

1  método DFS( origen):
2      marcamos origen como visitado 
3          para cada vertice v adyacente a origen en el Grafo: 
4              si v no ah sido visitado:
5                 marcamos como visitado v
6                 llamamos recursivamente DFS( v )  

Tomemos como ejemplo el siguiente grafo no dirigido:

Al igual que con la pila requerimos un nodo inicial, de manera recursiva llamamos a los adyacentes del nodo inicial, de esta forma se puede ver si llamamos inicialmente a “1”:

Inicial “1”: marcamos “1” como visitado, sus adyacentes son “2”,  “3” y “5”.

• Visitados : 1.
• Adyacentes de 1: 2 , 3 , 5

En la llamada recursiva ira el primero insertado en la lista de adyacencia, en este caso “2”, marcamos como visitado. Ahora el inicial es “2”, sus adyacentes son “1” , “4” y “5”.

• Visitados: 1 , 2
• Adyacentes de 2: 1, 4 , 5

Evaluamos el 1ero de la lista que es “1” pero ya fue visitado por lo tanto sigo con el siguiente, en este caso “4” , marcamos como visitado. Ahora inicial es “4”, sus adyacentes son “2”.

• Visitados: 1 , 2 , 4
• Adyacentes de 4: 2

Tocaria el nodo 2 pero ya fue visitado termina la recursion por ese lado. El siguiente adyacente de “2” es “5”. Ahora inicial es “5”, marcamos como visitado, sus adyacentes son “1” y “2”.

• Visitados: 1 , 2 , 4 , 5
• Adyacentes de 5: 1 , 2

Igual que con nodo “4” sus adyacentes han sido visitados por lo tanto terminamos la recursion por el nodo “2”.

El nodo actual es “1”, sus adyacentes eran “2”, “5” y “3”, estabamos evaluando por “2” pero ya terminamos el siguiente es “5” el cual ya fue visitado, continuamos con “3” este no fue visitado, marcamos como visitado, vemos sus adyacentes “1”.

• Visitados: 1 , 2 , 4 , 5 , 3
• Adyacentes de 3: 1

Como nodo “1” ya fue visitado entonces termina la recursión y termina el recorrido DFS. Como se puede observar el orden en que fueron visitados los nodos es el recorrido DFS del grafo.

Posibles Paths en un grafo

Otra ayuda importantisima del algoritmo recursivo es que nos permite hallar todos los posibles paths( rutas) de un nodo inicial a otro final, ello lo conseguiremos usando backtracking dentro del algoritmo:

Algoritmo en pseudocódigo:

1  método DFS( origen,final):
2      marcamos origen como visitado 
3      recuperar el path si se llego a final
4          para cada vertice v adyacente a origen en el Grafo: 
5              si v no ah sido visitado:
6                 marcamos como visitado v
7                 llamamos recursivamente DFS( v )
8      marcamos origen como no visitado

Codigo C++:  Algoritmo DFS usando Recursion

Componentes Conexas

Algun problema puede ser que nos pida hallar la cantidad de componentes conexas, supongamos el siguiente grafo no dirigido:

La cantidad de componentes conexas es 2. El problema puede ser resuelto de la siguiente manera:

Evaluamos todos los vertices posibles y los tomamos como origen aquellos no visitados:

1 2 3 4 5 6 7 8

... for( int i = 1 ; i <= V ; ++i ){    //recorremos todos los posibles vertices     if( !visitado[ i ] ){          //si alguno no fue visitado tenemos una componente a partir de ese nodo        dfs( i );                  //recorremos a partir de nodo i todo el grafo que se forma        total++;                   //incrementamos cantidad de componentes     } } ...

Usamos el algoritmo estandar DFS para cada recorrido:

1 2 3 4 5 6 7 8 9

void dfs( int u ){     visitado[ u ] = true;     visitado_componente[ u ] = true;     for( int v = 0 ; v < ady[ u ].size(); ++v ){         if( !visitado[ ady[ u ][ v ] ] ){             dfs( ady[ u ][ v ] );         }     } }

Veamos gráficamente, el código anterior parte evaluando el vértice 1:

• i = 1
• Visitados: Ninguno

Como no fue visitado entonces hacemos recorrido DFS partiendo de ese vértice ( dfs( i = 1 ) ). Entonces veamos el recorrido:

• Vértice Actual: 1
• Vértices Adyacentes: 2
• Vértices Visitados: 1

El siguiente paso es evaluar los adyacentes:

• Vértice Actual: 2
• Vértices Adyacentes: 3
• Vértices Visitados: 1, 2

• Vértice Actual: 3
• Vértices Adyacentes: 2
• Vértices Visitados: 1, 2, 3

Terminamos la función de DFS partiendo del vértice 1. Ahora volvemos al for inicial e incrementamos las componentes.

1 2 3 4 5 6

... if( !visitado[ i ] ){     dfs( i );     total++; //incrementamos numero de componentes } ...

Ahora tenemos i = 2 pero 2 ya fue visitado por lo que no entraría al if, igual para i=3 que ya fue visitado; sin embargo para i=4 este no fue visitado por lo tanto hacemos recorrido dfs partiendo del vértice 4:

• i = 4
• Visitados: 1, 2, 3

• Vértice Actual: 4
• Vértices Adyacentes: 5
• Vértices Visitados: 1, 2, 3, 4

Como 5 no fue visitado es el siguiente a evaluar:

• Vértice Actual: 5
• Vértices Adyacentes: 4
• Vértices Visitados: 1, 2, 3, 4, 5

Terminamos DFS partiendo del vértice 4, entonces volvemos al if e incrementamos el numero de componentes, de esta manera el resultado será de 2 componentes.