# 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

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

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)

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.
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:
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.
Esta variable será inicializada en el cuerpo del módulo Nodos:
Respecto a las funciones de este módulo, en primer lugar la función NodoInicial deberá contener la disposición inicial del laberinto:
Siendo MURO una constante con el valor MAX(CARDINAL), que hace la función de ∞. El laberinto quedaría así:
    $Laberinto={\begin{pmatrix}1&0&0&0&MURO&0\\0&0&MURO&0&0&0\\0&MURO&MURO&0&MURO&0\\0&0&MURO&0&MURO&0\\MURO&0&MURO&0&0&0\\0&0&0&0&MURO&0\\\end{pmatrix}}$
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:
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:

### Funciones auxiliares
## 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