Algoritmia/Laberinto Ramificación y Poda
Encontrar una ruta para salir de un laberinto es un típico ejemplo de un problema de programación. Si bien la generación de una solución se puede obtener por varios métodos (como puede ser la Vuelta Atrás), en el caso que nos atañe, emplearemos el esquema conocido como, Ramificación_y_poda.
Descripción del problema
[editar]Dada una matriz bidimensional n x n que representa un laberinto cuadrado, cada posición de la misma contiene un entero no negativo que indica si la casilla es transitable (0) o no lo es (∞). Las casillas [1,1] y [n, n] (salida y llegada del laberinto, respectivamente) siempre serán transitables. El problema radica en encontrar un algoritmo que encuentre un camino válido entre esas dos posiciones.
Solución
[editar]Para resolver este problema por Ramificación y Poda, podemos definir una función LC (Low Cost o Bajo Coste) usando como referencia la distancia Manhattan del punto donde nos encontremos actualmente hasta la salida, lo que quiere decir la distancia mínima.
Implementación en pseudo-código (Modula-2)
[editar]Usaremos un algoritmo de propósito general para la implementación de problemas de Ramificación y Poda (para encontrar la solución óptima, podríamos modificar este esquema general para obtener todas las soluciones o la primera solución), al cual, le serán definidas las funciones específicas de este caso particular.
PROCEDURE RyP():nodo;
VAR E: Estructura (* Estructura para almacenar los nodos *)
n,solucion:nodo;
hijos:ARRAY [1..MAXHIJOS] OF nodo; (* hijos de un nodo *)
numhijos,i,j,valor,valor_solucion:CARDINAL;
BEGIN
E:=Crear();
n:=NodoInicial();
Anadir(E,n,h(n)); (* h es la funcion de coste *)
solucion:=NoHaySolucion();
valor_solucion:=MAX(CARDINAL);
PonerCota(valor_solucion);
WHILE NOT EsVacia(E) DO
n:=Extraer(E);
INC(numanalizados);
numhijos:=Expandir(n,hijos);
INC(numgenerados,numhijos);
Eliminar(n);
FOR i:=1 TO numhijos DO
IF EsAceptable(hijos[i]) THEN
IF EsSolucion(hijos[i]) THEN
valor:=Valor(hijos[i]);
IF valor<valor_solucion THEN
Eliminar(solucion);
solucion:=hijos[i];
valor_solucion:=valor;
PonerCota(valor);
END;
ELSE
Anadir(E,hijos[i],h(hijos[i]))
END;
ELSE
Eliminar(hijos[i]);
INC(numpodados);
END;
END;
END;
Destruir(E);
RETURN solucion;
END RyP;
Comenzamos definiendo el tipo nodo. En primer lugar deberá de ser capaz
no sólo de representar el laberinto y en dónde nos encontramos en el momento
dado, sino que además debe contener la historia del recorrido (el camino
que hemos realizado hasta entonces). Para tal efecto definimos las
siguientes estructuras:
CONST dim = ...; (*dimensión del laberinto *)
TYPE laberinto = ARRAY [1..dim][1..dim] OF CARDINAL;
TYPE nodo = POINTER TO RECORD
x,y: CARDINAL;
l: laberinto;
END;
Las coordenadas x e y indican la casilla en donde nos encontramos, y los valores que vamos a almacenar en la matriz que define el laberinto indican el estado en el que se encuentra cada casilla, pudiendo ser:
- a) 0 si la casilla no ha sido visitada.
- b) MAX(CARDINAL) si la casilla no es transitable
- c) Un valor comprendido entre [1, dim x dim] que indica el orden en el que la casilla ha sido visitada.
De esta forma conseguimos que cada nodo sea autónomo, lo que quiere
decir, que cada uno contiene toda la información relevante para poder
realizar los procesos de bifurcación, poda y reconstrucción de
la solución encontrada hasta ese momento.
VAR cota : CARDINAL; (* número de movimientos de la mejor solución *)
Esta variable será inicializada en el cuerpo del módulo Nodos:
BEGIN (* Nodos *)
cota := MAX(CARDINAL);
END Nodos.
Respecto a las funciones de este módulo, en primer lugar la función
NodoInicial deberá contener la disposición inicial del laberinto:
CONST MURO = MAX(CARDINAL);
PROCEDURE NodoInicial():nodo;
VAR n: nodo; i,j:CARDINAL;
BEGIN
NEW(n);
(* rellenamos a cero el laberinto *)
FOR i:=1 TO dim DO
FOR j:=1 TO dim DO
n.l[i,j] :=0
END
END;
(* situamos la casilla inicial *)
n.x:=1; n.y:=1;
n.l[1,1]:=1;
(* podríamos implementar una función que los colocará aleatoriamente *)
(* por simplicidad del código colocaremos los bloques que forman los muros*)
n.l[1,5]:=MURO; n.l[2,3]:=MURO; n.l[3,2]:=MURO; n.l[3,3]:=MURO; n.l[3,5]:=MURO;
n.l[4,3]:=MURO; n.l[4,5]:=MURO; n.l[5,1]:=MURO; n.l[5,3]:=MURO; n.l[6,5]:=MURO;
RETURN n;
END NodoInicial;
Siendo MURO una constante con el valor MAX(CARDINAL), que hace la
función de ∞. El laberinto quedaría así:
La estrategia de ramificación está a cargo de la función Expandir. Cada
nodo puede generar un máximo de 4 hijos, que son los correspondientes a los
posibles movimientos que podemos realizar desde una casilla (arriba, abajo
izquierda y derecha). Esta función sólo generará aquellos movimientos
válidos, esto es, que no se salgan del laberinto, no se muevan sobre un muro
o sobre una casilla anteriormente visitada:
PROCEDURE Expandir (n: nodo; VAR hijos: ARRAY OF nodo):CARDINAL;
VAR i, j, nhijos:CARDINAL; p:nodo;
BEGIN
nhijos:=0;
i:=n.x;
j:=n.y;
(* y ahora vemos a donde lo podemos mover *)
IF ((i-1)>0) AND (n.l[i-1,j]=0) THEN (* arriba*)
INC(nhijos);
Copiar(n,p);
p.l[i-1,j]:=p.l[i,j]+1;
DEC(p.x);
hijos[nhijos-1]:=p;
END;
...............................................
(* ANÁLOGAMENTE PARA EL RESTO DE DIRECCIONES *);
Nota: El código de la función Copiar (n1,n2 :nodo) ha sido omitido por su simpleza, basta decir que la tarea de dicha función es copiar los atributos de n1 en el nodo n2 .
Nota 2: En este caso en particular y gracias a que estamos siguiendo una
estrategia LC y no una estrategia ciega (FIFO o LIFO) podemos
asegurar que el orden de generación de los nodos (y su posterior inserción
en la estructura) no va a tener una influencia relevante en el
comportamiento final del algoritmo.
La implementación de la función que poda quedaría de la siguiente
forma:
PROCEDURE EsAceptable (n:nodo): BOOLEAN;
BEGIN
RETURN Valor(n) <= cota;
END EsAceptable;
Funciones auxiliares
[editar]
PROCEDURE EsAceptable(n:nodo):CARDINAL;
BEGIN
RETURN n.l[n.x,n.y];
END Valor;
PROCEDURE h(n:nodo):CARDINAL;
BEGIN
RETURN (dim-n.x)+(dim-n.y);
END h;
PROCEDURE EsSolucion(n:nodo):BOOLEAN;
BEGIN
RETURN h(n)=0;
END EsSolucion;
PROCEDURE NoHaySolucion(n:nodo):nodo;
BEGIN
RETURN NIL ;
END NoHaySolucion;
PROCEDURE Eliminar(VAR n:nodo;
BEGIN
DISPOSE(n);
END Eliminar;
Ejemplos relacionados con este artículo
[editar]- Ramificación y poda
- También está disponible la versión en Vuelta Atrás del Problema del laberinto