BACKTRACK PARA LABERINTO

Backtracking para Resolver Laberintos: Guía Completa con Ejemplos

El Backtracking es una técnica algorítmica que permite resolver problemas de manera sistemática, probando todas las posibles soluciones. En este artículo, te explicamos cómo usar Backtracking para resolver laberintos, con ejemplos prácticos en código.

¿Qué es el Backtracking?

El Backtracking es una técnica de búsqueda que explora todas las posibles soluciones a un problema, retrocediendo cuando encuentra un camino inválido. Es especialmente útil para problemas como:

• Resolver laberintos.
• Encontrar rutas en grafos.
• Resolver puzzles como el Sudoku.

En el caso de los laberintos, el Backtracking permite encontrar una ruta desde el punto de inicio hasta la salida, retrocediendo cuando se encuentra un callejón sin salida.

¿Cómo Funciona el Backtracking en Laberintos?

El algoritmo de Backtracking para laberintos sigue estos pasos:

1. Inicio: Comienza en la posición inicial del laberinto.
2. Exploración: Intenta moverse en todas las direcciones posibles (arriba, abajo, izquierda, derecha).
3. Validación: Si el movimiento es válido (no es una pared y no ha sido visitado), marca la celda como visitada y continúa.
4. Retroceso: Si no hay movimientos válidos, retrocede a la celda anterior y prueba otra dirección.
5. Finalización: Si se llega a la salida, se ha encontrado una solución. Si no, el laberinto no tiene solución.

Implementación del Backtracking en Código

A continuación, te mostramos cómo implementar el algoritmo de Backtracking para resolver un laberinto en Python.

Representación del Laberinto

El laberinto se representa como una matriz, donde:

• 0: Camino libre.
• 1: Pared.
• 2: Camino visitado.
• 3: Salida.

Código en Python

# Definimos el laberinto
laberinto = [
    [0, 1, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 3]
]

# Tamaño del laberinto
N = 5

# Función para imprimir el laberinto
def imprimir_laberinto(laberinto):
    for fila in laberinto:
        print(fila)

# Función para verificar si una celda es válida
def es_valida(x, y, laberinto):
    return x >= 0 and x < N and y >= 0 and y < N and laberinto[x][y] == 0

# Función de Backtracking
def resolver_laberinto(laberinto, x, y):
    # Si llegamos a la salida, retornamos True
    if laberinto[x][y] == 3:
        return True

    # Marcamos la celda como visitada
    laberinto[x][y] = 2

    # Movimientos posibles: arriba, abajo, izquierda, derecha
    movimientos = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    for dx, dy in movimientos:
        nx, ny = x + dx, y + dy
        if es_valida(nx, ny, laberinto):
            if resolver_laberinto(laberinto, nx, ny):
                return True

    # Si no hay movimientos válidos, retrocedemos
    laberinto[x][y] = 0
    return False

# Resolver el laberinto
if resolver_laberinto(laberinto, 0, 0):
    print("Solución encontrada:")
    imprimir_laberinto(laberinto)
else:
    print("No hay solución.")
    

Explicación del Código

• es_valida: Verifica si una celda es válida para moverse.
• resolver_laberinto: Implementa el algoritmo de Backtracking.
• imprimir_laberinto: Muestra el laberinto en la consola.

Ejemplo de Laberinto Resuelto

Para el laberinto definido en el código, la salida sería:

Solución encontrada:
[2, 1, 0, 0, 0]
[2, 1, 1, 1, 0]
[2, 2, 2, 1, 0]
[1, 1, 2, 1, 0]
[0, 0, 2, 2, 3]
    

Los números 2 representan el camino seguido desde el inicio hasta la salida.

Conclusión

El Backtracking es una técnica poderosa para resolver problemas como los laberintos. Aunque puede ser ineficiente para laberintos grandes, es una excelente manera de entender cómo funcionan los algoritmos de búsqueda. ¡Practica con este ejemplo y domina el uso del Backtracking!

Recursos Adicionales

Si quieres profundizar en el tema, te recomendamos los siguientes recursos:

• Khan Academy: Algoritmos
• GeeksforGeeks: Backtracking Algorithms
• Desmos: Calculadora Gráfica

© 2023 TuSitioWeb.com. Todos los derechos reservados.

BACKTRACK PARA LABERINTO.

Dado una matriz n x m, ingresar una posición inicial y otra final. Implementar el Algoritmos de BackTrack(), para este problema. Debe terminar la búsqueda cuando encuentre el primer camino solución. Ejecutar el algoritmo con a) Sin heurística, elegir siempre el primero, b) Con heurística, elegir el camino de menor distancia entre el objetivo y la regla (utilizar distancia entre dos puntos).

Ejecutar el Algoritmos, para valores de n y m grandes: a) Sin Atajos, b) con Atajos.  Para ambos casos con y sin heurística y comparar las longitudes de camino y la cantidad de vueltas.

Realizar los mismos casos para el Problema del Laberinto, para casos que se pueda mover inclusive por las diagonales.

SOLUCION:

Creación de la clase

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

public class Tarea2 {         public static int  c=0;     public static void main(String[] args) {         // TODO code application logic here                      int n=5;         int m[][]=new int[n][n];                 if (labeH(m, 0, 0, 3, 2, 1)) {             System.out.println("EXISTE SOLUCION");             mostrar(m);         }else             System.out.println("NO existe sol");         System.out.println("la cantidad de pasos que realiza es "+c);     }    public static boolean labeH(int m[][],int i,int j,int i1,int j1,int         paso){         m[i][j]=paso;         c++;         if (i==i1 &&j==j1) {            // mostrar(m);             return true;         }         LinkedList<Regla> L1=reglasAplicables(m, i, j);         while (!L1.isEmpty()) {                        Regla R=elegirMejorRegla(L1, i1, j1);             if (labeH(m, R.fil, R.col, i1, j1, paso+1)) {                 return true;             }             m[R.fil][R.col]=0;             c--;         }         return false;     } }

Metodos

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

public static boolean posValida(int m[][],int i,int j){          if (i<0|| i>=m.length) {              return false;          }          if (j<0 || j>=m[i].length) {              return false;          }          if (m[i][j]>0) {              return false;          }else{              return true;          }      }           //-----------------     public static LinkedList<Regla> reglasAplicables(int m[][],int i,int j){          LinkedList<Regla> L1=new LinkedList();          if (posValida(m, i-1, j)) {              L1.add(new Regla(i-1, j));          }          if (posValida(m, i, j-1)) {              L1.add(new Regla(i, j-1));          }          if (posValida(m, i, j+1)) {              L1.add(new Regla(i, j+1));          }          if (posValida(m, i+1, j)) {              L1.add(new Regla(i+1, j));          }                 return L1;      }        //-----     public static Regla elegirMejorRegla(LinkedList<Regla> L1,int         i1,int j1){         int distMenor=Integer.MAX_VALUE;         int posMenor=0;         int i=0;         while (i<L1.size()) {                        int dist=distancia(L1.get(i).fil, L1.get(i).col, i1, j1);               if (dist<distMenor) {                 distMenor=dist;                 posMenor=i;             }             i++;         }         Regla R=L1.get(posMenor);         L1.remove(posMenor);         return R;     }

-------------------------------------