Problema de la mochila
Páginas: 5 (1228 palabras)
Publicado: 26 de febrero de 2012
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 mochilatiene 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 lamochila 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 delproblema 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úmerosenteros. 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 dela 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). Laidea 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 aplazo 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 puedeformular 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
Laprogramació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...
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 mochilatiene 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 lamochila 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 delproblema 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úmerosenteros. 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 dela 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). Laidea 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 aplazo 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 puedeformular 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
Laprogramació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...
Leer documento completo
Regístrate para leer el documento completo.