• Author / Uploaded
• Nohely Ruth Molina Huaquisto

Citation preview

El Problema De La Mochila El problema de la mochila consiste en llenar una mochila con una serie de objetos que tienen una serie de pesos con un beneficio asociado. Es decir, se dispone de n tipos de objetos y que no hay un número limitado de cada tipo de objeto (si fuera limitado no cambia mucho el problema). Cada tipo i de objeto tiene un peso Pi y un valor Bi beneficio asociado. La mochila tiene una capacidad de peso igual a M. Se trata de llenar la mochila de tal manera que se maximice el valor de los objetos incluidos pero respetando al mismo tiempo la restricción de capacidad. Notar que no es obligatorio que una solución óptima llegue al límite de capacidad de la mochila. El objetivo es llenar la mochila, de capacidad M, de manera que se maximice el beneficio. El problema de la mochila es uno de los 21 problemas NP-completos de Richard Karp, expuestos en su artículo de 1972. Ha sido estudiado desde mitades del siglo XX y se encuentran referencias desde 1897, en un artículo de George Ballard Mathews. La formulación del problema se bastante sencillo, pero su solución es más compleja. Los algoritmos existentes pueden resolver casos concretos pero la estructura singular del problema y el hecho que es un sub-problema otros problemas más generales, hacen que actualmente todavía sea estudiado por diferentes grupos de búsqueda científica. Existen diferentes variantes para este problema algunas son: * El problema de la mochila Variables continuas: El problema de la mochila en variables continúas (LKP) se obtiene sacando la restricción de que las variables sean números enteros. Es decir que se permite coger simplemente una fracción de los objetos dentro de la mochila: xϵ [0,1] . * El problema de la mochila multe-objetivo: Una variante del problema consiste, a partir de objetos que tienen varios valores, maximizar varías funciones objetivo, es el problema de la mochila multe-objetivo (MOKP). * El problema de la mochila cuadrático: En el problema de la mochila de elige múltiple (MCKP), los objetos se reagrupan en clases, y simplemente se tiene que coger un solo representante de cada clase. Por ejemplo, si se quiere diseñar una caja de herramientas. Si hay cinco llaves inglesas se puede elegir, o bien la menos pesada para poder coger un martillo bueno que es pesado, o elegir la clave más versátil y un martillo de gama baja (poco pesado). La idea general es que no se puede coger más de una clave ni más de un martillo. * Problema de la mochila múltiple: El problema de la mochila múltiple (MKP) consiste a repartir un conjunto de objetos en varias mochilas de capacidades diferentes. El valor de un objeto depende ahora de la mochila en que se ha colocado. Por ejemplo, se puede considerar que un euro tiene más valor en una cuenta a plazo fijo que en una cuenta corriente. El Problema de la Mochila 0 1 La mochila 0-1 es un caso especial del problema original de la mochila en el cual cada artículo de la entrada no se puede subdividir para llenar un envase en el cual esa entrada quepa parcialmente. Problema de la mochila 0-1 restringe el número de cada clase de artículo, xj, a cero o a uno. El problema 0-1 se puede formular matemáticamente como: Maximize: bixi con 1≥ i ≥ n conforme a: pixi ≤M con 1≥ i ≥ n no pone ningún límite en el número de cada artículo. De interés particular está el caso especial del problema con estas características:

* Es un problema de la decisión * Es un problema de 0/1 * Para cada artículo, el coste iguala el valor: M = V Programación Dinámica La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas. El diseño de un algoritmo de Programación Dinámica consta de los siguientes pasos: 1. Planteamiento de la solución como una sucesión de decisiones y verificación de que ésta cumple el principio de óptimo. 2. Definición recursiva de la solución. 3. Cálculo del valor de la solución óptima mediante una tabla en donde se almacenan soluciones a problemas parciales para reutilizar los cálculos. 4. Construcción de la solución óptima haciendo uso de la información contenida en la tabla anterior. Problema de la Mochila 0/1 Programación Dinámica for(int i=1;i=1;i--) { if(V[i][j]==V[i-1][j]) x[i-1]=0; else { x[i-1]=1; j =j-p[i]; } } Función de Tiempo de ejecución: i=1n(j=1M1)+n= i=1nM=n*M+n Tn=nM+1 → Tn∈O(n.M) Programación Vuelta Atrás (Backtracking) Es una estrategia para encontrar soluciones a problemas que satisfacen restricciones. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en los años 1950s. En su forma básica, la idea de backtracking se asemeja a un recorrido en profundidad dentro de un grafo dirigido. El grafo en cuestión suele ser un árbol, o por lo menos no contiene ciclos. Sea cual sea su estructura, existe sólo implícitamente. El objetivo del recorrido es encontrar soluciones para algún problema. Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estas soluciones parciales limitan las regiones en las que se puede encontrar una solución completa. El recorrido

tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En este caso el algoritmo puede bien detenerse (si lo único que se necesita es una solución del problema) o bien seguir buscando soluciones alternativas (si deseamos examinarlas todas). Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puede completar. En tal caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminando sobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve a un nodo que tiene uno o más vecinos sin explorar, prosigue el recorrido de una solución. Problema de la Mochila 0/1 Programación Vuelta Atrás mochila(int i, int r, int solucion, int optimo,int n,int Peso,int sol) { int k; int valor[]= {2,3,4,5}; int peso[]={1,2,3,4}; int s=4; for (k = i; k