Algoritmo recursivo para 2D laberinto?

(Esto no es un duplicado) Tenemos un 2D laberinto rodeado de X en todos los 4 lados y hay bloques interiores también.
Todos estos personajes de el laberinto se almacena en la matriz 2D. El programa debe encontrar la ruta de acceso de inicio de ‘objetivo ‘G’. Para ello, un método booleano llamado ‘resolver(int fila, int col) se usa y se inicializa con la fila y la columna de índice de ‘S’. El algoritmo debe ser recursivo. Debe devolver true si su poder encontrar el camino de la ‘G’ y false en otro sabio. He aquí cómo he tratado de abordar este problema, que muestra «parcial resultado correcto».

public boolean solve(int row, int col) {
  char right = this.theMaze[row][col + 1];
  char left = this.theMaze[row][col - 1];
  char up = this.theMaze[row - 1][col];
  char down = this.theMaze[row + 1][col];
  if (right == 'G' || left == 'G' || up == 'G' || down == 'G') {
    return true;
  }
  System.out.println("position=>"+"("+row + ":" + col+")");
  if (right == ' ') {
    return solve(row,col+1);
  }
  if (down == ' ') {
    return solve(row+1,col);
  }
  if (left == ' ') {
    return solve(row,col-1);
  }
  if (up == ' ') {
    return solve(row-1,col);
  }
  return false;
}

Aquí está la salida se resuelve :

   0 1 2 3 4 5 6 7 8 9 10 
0  X X X X X X X X X X X 
1  X X S X X X X X   X X 
2  X X   X X X X X   X X 
3  X X   X X X X X   X X 
4  X X   X X X X X   X X 
5  X X   X X X X X   X X 
6  X X   X X X X X   X X 
7  X X   X X X X X G X X 
8  X X               X X 
9  X X X X X X X X X X X 

position=>(1:2)
position=>(2:2)
position=>(3:2)
position=>(4:2)
position=>(5:2)
position=>(6:2)
position=>(7:2)
position=>(8:2)
position=>(8:3)
position=>(8:4)
position=>(8:5)
position=>(8:6)
position=>(8:7)
true

Pero cuando pongo ‘G’ un paso (a 6,8). Muestra de stackOverflow de error. La razón es porque la repetición se produce entre 2 puntos en este estado (de alguna manera como la recursividad indirecta).

¿Cómo puedo solucionar este problema. Es de todos modos hay que decir que el programa para mover hacia arriba en lugar de hacia abajo? Cambio de la posición de enunciados condicionales que no funcionan bien. Y creo que una posición que tiene más de un camino para ir, pero sólo uno lleva a la ‘G’. ¿Cómo volver a la posición inicial y probar otro camino ? Gracias de antemano.

Actualización:

Aquí es un Repo en Github enlace a la solución de este problema por mí.

6 Kommentare

  1. 5

    Se podría llenar en otro símbolo en los espacios que usted entró a través de la ya de forma que su programa sabrá que él ya estaba allí.

  2. 1

    Puede utilizar un DFS o BFS.
    La DFS es la más fácil. Sólo tiene que hacer una recursividad, navegar en todos los 4/8-direcciones y marca, que en lugar de (X,Y) como la visita. Si es usted el destino de la «G», devolver true de lo contrario continúe.

    Consejos:

    • No utilizar la misma matriz a leer el mapa y se marca como visitado, BESO
    • Usted tiene que comprobar constantemente si usted ha descubierto G. Usted puede hacer esto mediante la devolución siempre FALSO o VERDADERO, o puede utilizar una variable global.

    Si usted tiene problemas en la implementación de tratar de google para algunas código fuente acerca de este problema:
    http://en.wikipedia.org/wiki/Flood_fill

    http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

  3. 1

    En el presente código, hay una posibilidad de que regrese a cabo false sin mirar a otro conectado posiciones.

    Usted debe buscar a través de otras posibilidades antes de regresar de la if condición.

    También, usted debe comprobar si la posición ha sido visitada para evitar la recursividad infinita.

    Cambiar su código para:

    bool solved = false;
    visited[row][col] = true;
    
    if (right == ' ' && !visited[row][col+1]) {
        solved = solve(row,col+1);
    }
    if (down == ' ' && !solved && !visited[row+1][col]) {
        solved = solve(row+1,col);
    }
    if (left == ' ' && !solved && !visited[row][col-1]) {
        solved = solve(row,col-1);
    }
    if (up == ' ' && !solved !visited[row-1][col]) {
        solved = solve(row-1,col);
    }
    return solved;
  4. 0

    Aquí es un pseudo código para resolver el laberinto y también recorrer la solución : –

    boolean Solve(int x,int y) {
    
       if(isTarget(x,y)) 
           return(true)
    
       if(valid(x+1,y)&&Map[x+1][y]==' ') {
          Map[x][y] = 'D'
          if(Solve(x+1,y))
             return(true)
          Map[x][y] = ' '
       }
       if(valid(x-1,y)&&Map[x-1][y]==' ') {
          Map[x][y] = 'U'
          if(Solve(x-1,y))
             return(true)
          Map[x][y] = ' '
       }
       if(valid(x,y+1)&&Map[x][y+1]==' ') {
          Map[x][y] = 'R'
          if(Solve(x,y+1))
             return(true)
          Map[x][y] = ' '
       }
       if(valid(x,y-1)&&Map[x][y-1]==' ') {
          Map[x][y] = 'L'
          if(Solve(x,y-1))
             return(true)
          Map[x][y] = ' '
       }
    
       return(false);
    }
  5. 0

    Inspirado por este artículo La resolución de un Laberinto 2D, una solución recursiva

    JS:

    const CORRIDOR = 0;
    const WALL = 1;
    const EXIT = 2;
    
    //board - 2D array
    //start - [row, column] location of start point
    
    function findPath(board, start) {
      let seenPath = new Set();
    
      findPathRecur(board, start, seenPath)
    
      return Array.from(seenPath);
    }
    
    function findPathRecur(board, point, seenPath) {
      let row = point[0],
        column = point[1];
        
      //Base Case
      if (!isValidPathPoint(board, point, seenPath)) {
        return false;
      }
    
      if (board[row][column] === EXIT) {
        seenPath.add(point.toString());
        return true;
      }
    // console.log("Curr -", point, ", Seen -", Array.from(seenPath));
    
    	seenPath.add(point.toString());
    
      let leftColumn = [row, column - 1],
        rightColumn = [row, column + 1],
        topRow = [row - 1, column],
        bottomRow = [row + 1, column];
    
      if (findPathRecur(board, leftColumn, seenPath)) {
        return true;
      }
      if (findPathRecur(board, rightColumn, seenPath)) {
        return true;
      }
      if (findPathRecur(board, topRow, seenPath)) {
        return true;
      }
      if (findPathRecur(board, bottomRow, seenPath)) {
        return true;
      }
    
      seenPath.delete(point.toString());
    
      return false;
    }
    
    //Check if the point is on valid path
    function isValidPathPoint(board, point, seenPath) {
      let row = point[0];
      let column = point[1];
    
      //Check if point exists
      if (board[row] != null && board[row][column] != null) {
    
        //To avoid cycle
        if (!seenPath.has(point.toString())) {
          //Not a Wall
          if (board[row][column] !== WALL) {
            return true;
          }
        }
      }
      return false;
    }
    
    //Test Program
    let maze = [
      [1, 1, 1],
      [0, 0, 1],
      [1, 2, 1]
    ];
    
    let testStart = [
    	[1,0],
      [1,1],
      [2,1],
      [0,0],
      [5,5]
    ];
    
    testStart.forEach(function(start, i) {
    	console.log("Test Case:",i);
      console.log("\tStart -", start, "Path -", findPath(maze, start));
    })

Kommentieren Sie den Artikel

Bitte geben Sie Ihren Kommentar ein!
Bitte geben Sie hier Ihren Namen ein

Pruebas en línea