Laberinto Ramificación y Poda

De Wikipedia, la enciclopedia libre

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 1 Descripción del problema 2 Solución 3 Implementación en pseudo-código (Modula-2) 3.1 Funciones auxiliares 4 Ejemplos relacionados con este artículo 5 Bibliografía

[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

[editar] Bibliografía

• Martí, Narciso; Verdejo, Alberto; Ortega, Yolanda (2003), Estructuras de datos y métodos algorítmicos: ejercicios resueltos, Madrid: Prentice Hall.