Amigos de lo Ajeno

El problema del Laberinto

El problema consiste en atravesar un laberinto, dentro del cuál se encontrarán, como en cualquier laberinto, muros y callejones sin salida. El objetivo del problema es que partiendo de una posición inicial (entrada del laberinto), que llamaremos (0,0), se llegue a la posición final (salida del laberinto) (n-1,n-1). Para resolver este problema se diseñará un algoritmo de BackTracking de forma que se marcará en la misma matriz del laberinto un camino solución si existe.

Es necesario tener en cuenta las siguientes limitaciones:

• Nos encontramos en una entrada de un laberinto y debemos intentar atravesarlo.
• Representación: matriz de dimensión n×n de casillas marcadas como libre u ocupada por una pared.
• Es posible pasar de una casilla a otra moviéndose solamente en vertical u horizontal.
• Se debe ir de la casilla (1,1) a la casilla (n,n)

El problema de la Mochila

Un problema típico de programación entera es el que nos ocupa, “el problema de la mochila”, que responde a la siguiente situación: imagínese hacer una excursión a la que solo podemos llevar una mochila 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 exceder su capacidad.

A contunación tenemos la  implementación del algoritmo de la mochila SIN fraccionamiento. El algoritmo solicita al usuario el vector de beneficios, el vector pesos y la capacidad de la mochila y mostrar el beneficio total obtenido.

También se incluye la mejora el algoritmo anterior usando una estimación voraz y cambiando el recorrido del árbol. Se calcula el número de nodos generados y podados con cada una de las modificaciones.

A continuación podeis descargar un proyecto con mi propio código fuente que resuelve el problema del laberinto, el de la mochila y la mochila por estimación voraz.

[DESCARGA]