Laberinto Ramificación y Poda
De Wikipedia, la enciclopedia libre
Este artículo o sección debería estar en Wikilibros ya que es una guía o manual en vez de un verdadero artículo enciclopédico. [ver página en Wikilibros] Si modificas este artículo dándole una orientación enciclopédica, elimina por favor esta plantilla. |
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.
Tabla de contenidos |
[editar] Descripción del problema
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.
[editar] Solución
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.
[editar] Implementación en pseudo-código (Modula-2)
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;
[editar] Funciones auxiliares
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;
[editar] Ejemplos relacionados con este artículo
- Ramificación y poda
- También está disponible la versión en Vuelta Atrás del Problema del laberinto