DISEÑO Y ANÁLISIS DE UN ALGORITMO MEDIANTE BACKTRACKING PROBLEMA DE LA MOCHILA

[pic 1]

DISEÑO Y ANÁLISIS DE UN ALGORITMO MEDIANTE BACKTRACKING PROBLEMA DE LA MOCHILA

[pic 2]

UNIVERSIDAD AUTONOMA DE MANIZALES

DISEÑO DE ALGORITMOS

[pic 3]

Manizales (Caldas)

26 de Noviembre de 2021

Tabla de contenidos

Aplicabilidad        2

Diseño del algoritmo mediante backtracking        2

Implementación en Java        4

Clase Mochila        4

Clase Elemento        5

Algoritmo para seleccionar los elementos de la mochila        5

Prueba del algoritmo        6

Instrumentación para el conteo de instrucciones        7

Ejecución para diferentes tamaños del problema        7

Resultados de la gráfica        8

Análisis de la complejidad        8

Comparación de gráficas y conclusión        9

Referencias        10

Aplicabilidad

El problema de la mochila, comúnmente abreviado por KP (del inglés Knapsack problem) es un problema de optimización combinatoria. Busca la mejor solución entre un conjunto de posibles soluciones a un problema. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo.

Diseño del algoritmo mediante backtracking

Hay n tipos de elementos opcionales 1, ..., n, colocados en una mochila de capacidad c, para que los elementos cargados tengan el mayor beneficio.

• Datos del problema:

n: número de artículos

m: capacidad de la mochila

b1, b2, ..., bn: valor de beneficio de bienes individuales p1, p2, ..., pn: capacidad individual del artículo

• Formulación matemática

Maximizar

∑        𝑥𝑖 𝑏𝑖

𝑖=1...𝑛

sujeto a la restricción

∑        𝑥𝑖 𝑝𝑖 ≤ 𝑀, & 𝑥𝑖 ∈ {0, 1}

𝑖=1...𝑛

• Aplicación de backtracking (proceso metódico):

• Determinar cómo es la forma del árbol de backtracking, cómo es la representación de la solución.

• Con un árbol binario: 𝑆 = (𝑥1, 𝑥2,..., 𝑥𝑛), con 𝑥𝑖 ∈ {0, 1}

• xi = 0 No se coge el objeto i
• xi = 1 Sí se coge el objeto i
• xi = -1 Objeto i no estudiado
• En el nivel i se estudia el objeto i
• Las soluciones están en nivel n

[pic 4]

• Elegir el esquema de algoritmo adecuado, adaptándolo en caso necesario.[pic 5]

• Diseñar las funciones genéricas para la aplicación concreta: según la forma del árbol y las características del problema.

[pic 6]

Para los pasos anteriores tomando en cuenta ciertos cambios al hacer el programa en Java, las funciones genéricas pueden cambiar o unificarse en el desarrollo del progreso.

En el momento en el que el algoritmo no encuentra ningún valor que pueda ser asignado a la mochila, retorna las soluciones mediante backtracking para probar la siguiente configuración posible. Si se exploran todas las soluciones sin éxito, entonces el problema no tiene solución.

Implementación en Java

Clase Mochila

La clase mochila es la que cuenta con los datos necesarios para solucionar el problema, en esta podemos encontrar el beneficio actual, el peso máximo, el peso actual y la lista de objetos o elementos que están dentro de está. También se cuentan con diversos métodos dentro de esta clase, los cuales nos servirán para diferentes funciones como:

• Insertar o añadir un elemento en la lista de la mochila
• Verificar la existencia de un elemento dentro de la lista de la mochila
• Limpiar o eliminar los elementos y los valores del peso y el beneficio actual
• Mostrar los elementos dentro de la lista de la mochila con sus respectivos pesos y beneficios.
• Y por último, el método que nos interesa, el que nos permite llenar las mochilas evaluando que el peso que suman los elementos no sobrepasen el peso máximo, y que el beneficio conseguido de estos sea el más alto.

[pic 7]

Clase Elemento

La clase elemento es la que cuenta con los datos que vamos a obtener de cada elemento para poder agregarlo o no a la mochila, que quiere decir esto, que la clase elemento solo es una clase que nos sirve para almacenar información, más allá de eso, sus métodos son irrelevantes para la correcta solución de nuestro problema. Por lo descrito anteriormente, solo contaremos con un método que nos servirá para saber la información del elemento que está dentro de la mochila.

[pic 8]

Algoritmo para seleccionar los elementos de la mochila

El algoritmo de selección para los elementos consta de tres partes:

...