Amigos de lo Ajeno

El método de diseño de algoritmos Ramificación y poda (también llamado Ramificación y Acotación) es una variante del Backtracking mejorado sustancialmente y se aplica mayoritariamente para resolver cuestiones o problemas de optimización.

La técnica de Ramificación y poda se suele interpretar como un árbol de soluciones, donde cada rama nos lleva a una posible solución posterior a la actual. La característica de esta técnica con respecto a otras anteriores (y a la que debe su nombre) es que el algoritmo se encarga de detectar en qué ramificación las soluciones dadas ya no están siendo óptimas, para «podar» esa rama del árbol y no continuar malgastando recursos y procesos

Presentación del problema

A partir del siguiente algoritmo para la resolución de la Mochila 0/1 mediante Ramificación y Poda, he implementado un programa en C# que resuelve este problema con las siguientes estrategias:

• FIFO – ( First In First Out ) Primero en entrar – Primero en salir
• LIFO – (Last In First Out ) Ultimo en entrar Primero en salir. ( PILA)
• LC – LIFO – Array Ultimo en entrar Primero en salir.(ARRAY DE PILAS)
• LC – FIFO – Array Primero en entrar Primero en salir.(ARRAY DE COLAS)

La Lista de nodos vivos (LNV) estará formada por objetos de la clase Nodo, que se define de la siguiente manera:

Proceso de resolución

1. Se ordenan los vectores de beneficio y peso según el cociente B/P.
2. Una vez hecho esto se genera el nodo raíz y se añade a la lista de nodos vivos.
3. En este momento se entra en un bucle donde se repiten hasta que la LNV este vacía las siguientes operaciones:
4. Si el nodo extraído promete mejor beneficio que el que llevamos hasta ahora se estudia (primera poda ) genero sus hijos en el nodo y.
5. Para cada hijo si el peso que contiene es > que el peso máximo permitido no lo trato (NO HAGO NADA) por que en el constructor de la clase nodos ya he inicializado los valores de cotas a números muy pequeños.
6. De lo contrario trato el nodo y genero las estimaciones correspondientes.
7. Luego se comprueba si la situación actual es solución y si lo es se actualiza el nodo solución.
8. Si no es solución se mira si la cota superior del nodo que estamos tratando es mayor o igual a la C que llevamos( poda 2 ) se añade a LNV si no no.

Objetivo:

El objetivo es obtener la solución óptima al problema de la mochila con las distintas estrategias y comparar los números de nodos generados en cada una de ellas para ver cual es más eficiente en caso de empates.

Solución propuesta

Este proyecto contiene  el código que resuelve el problema por las 4 estrategias citadas previamente. También he incluido una memoria con la explicación al detalle, así como una comparativa con trazas de cada una de las estrategias, donde se aprecian el número de nodos podados y el número de nodos generados, permitiendo realizar comparativas.