Analisis de algoritmos

Solo disponible en BuenasTareas
  • Páginas : 15 (3602 palabras )
  • Descarga(s) : 0
  • Publicado : 27 de octubre de 2010
Leer documento completo
Vista previa del texto
INTRODUCCION

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes; es por esto que nos detenemos a evaluar los algoritmos de laprogramación dinámica y vuelta atrás para solucionar el problema de la mochila.

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.[1] La formulación del problema se bastante sencillo, pero su solución esmá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.
“el problema de la mochila”, que responde a la siguiente situación: imagínese hacer una excursión a la que solo podemos llevar unamochila que, lógicamente, tiene una capacidad limitada. Cada objeto que introducimos ocupa un volumen dentro de la misma y en contrapartida durante el viaje nos proporcionará un beneficio o utilidad (ejemplo: una cantimplora), el problema surge cuando debemos elegir qué objetos seleccionar para llevar en la mochila de forma que nuestro beneficio sea máximo (tengamos todo lo necesario) sin excedersu capacidad.
Esta situación se presenta con cierta frecuencia en los ámbitos económico e industrial, donde la mochila suele representar la restricción presupuestaria (cantidad máxima de recursos económicos de los que se dispone) y donde la utilidad de los objetos seleccionados se equipara a un beneficio económico por adquirir o llevar a cabo ciertas acciones.
Formulación
Para facilitar lacomprensión del lector, antes de incorporar a este escrito la formulación del problema, analizaremos las partes de las que se compone la misma.
Datos del problema
- n: número de objetos entre los que se puede elegir.
- ci: peso del objeto “i” - se refiere el objeto “í”-ésimo que no es más que una forma de hacer referencia a un objeto cualquiera que pueda ser incluido en la mochila -, es decir, cirepresenta el coste de escoger un objeto, en tanto en cuanto va a ocupar un “espacio de la mochila” que dejará fuera otros objetos.
- bi: utilidad o beneficio que proporciona cada objeto, de nuevo se hace referencia al objeto i-ésimo.
- P: capacidad de la mochila, equivale al presupuesto máximo del que se dispone.
Variables a tener en cuenta
Los elementos a introducir en la mochila van a sernuestras variables objeto de análisis, cada variable la denotaremos como xi. El rasgo más importante de nuestras xi es que se tratan de variables dicotómicas o binaria, es decir, sólo pueden tomar dos valores, en este caso, escogeremos el valor “1” (si el objeto se incluye en la mochila) ó “0” (si el objeto se excluye de la mochila)
Restricciones
La restricción vendrá marcada por la capacidadmáxima de la mochila, de tal forma que la suma de todos los objetos multiplicados por el espacio que ocupan en la mochila no podrá exceder dicha capacidad máxima. Su formulación matemática es la que sigue:
Función a maximizar
Tal y como se expresa en la definición, el objetivo de este problema es seleccionar aquellos objetos que introducidos en la mochila nos proporcionan una mayor utilidad. Enotras palabras, lo que debemos hacer es maximizar la utilidad de nuestra mochila.
Si redefinimos el problema introduciendo los elementos que mencionamos en las líneas precedentes llegaremos a la siguiente formulación:
“El problema de la mochila consiste en llenar una mochila con n objetos. Cada objeto i tiene un peso determinado ci siempre positivo y una utilidad o valor asociado, también...
tracking img