Búsqueda en primer lugar en una grilla de 8x8 en Java

Question

Lo que trato de hacer es contar cuántos movimientos se necesitan para llegar a la meta utilizando la ruta más corta. Debe hacerse usando una primera búsqueda de amplitud. Puse la grilla de 8x8 en una matriz de 2d que está llena con uno de cuatro caracteres, E para vacía (puede moverse en estos puntos), B para bloqueada (no se puede mover aquí), R para robot (punto de inicio) o G para el objetivo El algoritmo tenía que buscar espacios movibles en el orden arriba, izquierda, derecha, y abajo, lo cual creo que he hecho correctamente. Después de comprobar un nodo, cambia su contenido a 'B'. Si no se puede alcanzar el objetivo, se debe devolver 0.

He cambiado mi código para implementar lo que Kshitij me dijo, y funciona muy bien. Estaba demasiado cansado para ver que no estaba inicializando mi cola después de cada nuevo conjunto de datos jajaja. ¡Gracias por la ayuda!

public static int bfSearch(){ 
    Queue <int []> queue = new LinkedList <int []>(); 
    int [] start = {roboty,robotx,0}; 
    queue.add(start); 

    while (queue.peek() != null){ 
     int [] array = queue.remove(); 

      if(array[0]-1 >= 0 && grid[array[0]-1][array[1]] != 'B'){ 

       if (grid[array[0]-1][array[1]] == 'G'){ 
        return array[2]+1; 
       } 
       else{ 
        grid[array[0]-1][array[1]] = 'B'; 
        int [] temp = {array[0]-1, array[1], array[2]+1}; 
        queue.add(temp); 
       } 
      } 

      if(array[1]-1 >= 0 && grid[array[0]][array[1]-1] != 'B'){ 

       if (grid[array[0]][array[1]-1] == 'G'){ 
        return array[2]+1; 
       } 
       else{ 
        grid[array[0]][array[1]-1] = 'B'; 
        int [] temp = {array[0], array[1]-1, array[2]+1}; 
        queue.add(temp); 
       } 
      } 

      if(array[1]+1 <= 7 && grid[array[0]][array[1]+1] != 'B'){ 

       if (grid[array[0]][array[1]+1] == 'G'){ 
        return array[2]+1; 
       } 
       else{ 
        grid[array[0]][array[1]+1] = 'B'; 
        int [] temp = {array[0], array[1]+1, array[2]+1}; 
        queue.add(temp); 
       } 
      } 

      if(array[0]+1 <= 7 && grid[array[0]+1][array[1]] != 'B'){ 

       if (grid[array[0]+1][array[1]] == 'G'){ 
        return array[2]+1; 
       } 
       else{ 
        grid[array[0]+1][array[1]] = 'B'; 
        int [] temp = {array[0]+1, array[1], array[2]+1}; 
        queue.add(temp); 
       } 
      } 
     }   
    return 0; 
} 

Answer 1

Tendrá que almacenar 2 cosas en su cola. Llamemos a cada elemento de su cola un nodo.

1. posición (que ya la tienda)
2. recuento (movimientos necesarios para llegar a esta posición desde la posición inicial)

Te comenzar mediante la asignación de la cuenta de su posición inicial a 0.

la forma en que funciona el algoritmo es:

1. usted hace estallar un nodo de la cola
2. determina dónde puede ir desde la posición especificada por el nodo que acaba de abrir. Es decir, si trata esto como "hacer un árbol sobre la marcha", está determinando los elementos secundarios del nodo que ha salido de la cola
3. y agrega estos elementos secundarios a la cola.

En el tercer paso, cuando agrega un nodo hijo a la cola, debe determinar el recuento que debe agregarse a este nodo. Este conteo es simplemente el count of the parent node (that you popped in step 1) + 1

Finalmente, su valor de retorno sería el recuento asociado con el nodo que lleva la posición de destino.

Por ejemplo, vamos a trabajar con una cuadrícula de 4x4, donde la posición [0,0] es el inicio, y la posición [0,3] es el destino.

S E E B 
E B E E 
B B B E 
G E E E 

Inicialmente, la cola sería:

[{(0, 0), 0}] 

donde el valor dentro de la () es la posición, y el segundo valor dentro de la {} es el recuento.

Extrae este nodo de la cola y determina que puede acceder a las posiciones (0,1) y (1,0). Entonces agrega elementos {(0, 1), 1} y {(1, 0), 1} a la cola. Tenga en cuenta que el recuento es 1 porque el recuento del nodo aparecido era 0 y que incrementa en 1. que su cola de ahora queda como:

[{(0, 1), 1}, {(1, 0), 1}] 

Se hace estallar el primer elemento, darse cuenta de que no tiene hijos viables, por lo sigues adelante

Aparece el elemento restante y descubre que le proporciona un nodo al que puede acceder, en la posición (2, 0). Como el nodo que ha insertado tiene el número 1, agrega esta nueva posición emparejada con conteo = 1 + 1 = 2 a la cola.

Con el tiempo, se le hace estallar el nodo objetivo de la cola, y es el recuento será 9.

Editar

Si desea obtener la ruta desde la fuente hasta el destino, el la codificación actual no funciona como está. Debería mantener una matriz 2D independiente de tamaño 8x8 con los recuentos en lugar de codificarlos en el nodo mismo. Y cuando finalmente encuentra el conteo para el destino, retrocede desde el destino hasta la fuente usando la matriz de conteo 2D. Esencialmente, si puede llegar al destino en 9 movimientos, puede llegar a una de sus posiciones adyacentes en 8 movimientos. Entonces, encuentra la posición que tiene el conteo 8 y está adyacente al destino. Repites iterativamente esto hasta llegar a la fuente.

El método que describió, donde agrega un elemento adicional a los nodos, no funciona. Lo dejaré para que descubras por qué, ya que esto es tarea :)

Answer 2

Aquí hay una buena alternativa corta a tu código. Exactamente la misma idea, pero no es necesario que haya tantas condiciones "si" para verificar la validez de cada coordenada. Todo esto se puede hacer de una vez. Echar un vistazo.

He comentado la explicación tanto como pude. Es legible incluso para personas que no tienen la menor idea. Supe por casualidad tu pregunta cuando estaba implementando una solución para un problema similar (¿el mismo?) Donde un tipo atrapado en un laberinto tuvo que encontrar la salida. Hubo trampas (B) y áreas movibles (E) en la grilla. El objetivo era llegar a su destino (G).

De todos modos, aquí está el código generalizado. Tomo el n. ° de filas, columnas y luego la grilla completa. Solo estoy imprimiendo si es posible llegar al destino o no. Os dejo el resto hasta que alguien que está leyendo esto como un ejercicio para asegurarse de que ha entendido el código;)

mente el hecho de que el objetivo principal de mi respuesta es que le muestre que el tamaño de sus BFS la función podría reducirse. Estoy publicando toda mi solución solo para dar la idea general de BFS aplicado en una grilla ya que tuve problemas mientras lo aprendía. Con suerte, esto ayudará a alguien atrapado en la misma situación. Si quiere la posición o la ruta seguida o algo, siga las instrucciones de las respuestas en esta pregunta. Hágalo usted mismo;)

import java.util.*; 

/** 
* Created by Shreyans on 4/30/2015 at 10:27 PM using IntelliJ IDEA 
*/ 

class MAZE 
{ 
    static int r,c,s1,s2,f1,f2;//Rows, Columns, Start Coordinates, Finish Coordinates 
    static int[] dx={1,-1,0,0};//right, left, NA, NA 
    static int[] dy={0,0,1,-1};//NA, NA, bottom, top 
    static char[][] grid;//Main grid 
    public static void main(String[] args) 
    { 
     Scanner sc=new Scanner(System.in);//I suggest using faster IO if you have performance concerns. I did. Scanner is readable hence the choice 
     r=sc.nextInt(); 
     c=sc.nextInt(); 
     grid=new char[r][c]; 
     for(int i=0;i<r;i++) 
     { 
      char[] s1=sc.next().toCharArray();//Reading a line of the Grid 
      System.arraycopy(s1,0,grid[i],0,c);//Nice inbuilt function to copy contents of an array. Also doable manually 
     } 
     s1=sc.nextInt()-1; 
     s2=sc.nextInt()-1; 
     f1=sc.nextInt()-1; 
     f2=sc.nextInt()-1; 
     if(MAZEBFS()) 
     { 
      System.out.println("PATH EXISTS"); 
     } 
     else 
     { 
      System.out.println("PATH DOES NOT EXIST"); 
     } 
    } 
    private static boolean MAZEBFS() 
    { 
     if(s1==f1&&s2==f2) 
     { 
      return true;//He's already there 
     } 
     else 
     { 
      grid [f1][f2]='G';//finish 
      Queue<int[]> q=new LinkedList<int[]>(); 
      int[]start={s1,s2};//Start Coordinates 
      q.add(start);//Adding start to the queue since we're already visiting it 
      grid[s1][s2]='B'; 
      while(q.peek()!=null) 
      { 
       int[]curr=q.poll();//poll or remove. Same thing 
       for(int i=0;i<4;i++)//for each direction 
       { 
        if((curr[0]+dx[i]>=0&&curr[0]+dx[i]<r)&&(curr[1]+dy[i]>=0&&curr[1]+dy[i]<c)) 
        { 
         //Checked if x and y are correct. ALL IN 1 GO 
         int xc=curr[0]+dx[i];//Setting current x coordinate 
         int yc=curr[1]+dy[i];//Setting current y coordinate 
         if(grid[xc][yc]=='G')//Destination found 
         { 
          //System.out.println(xc+" "+yc); 
          return true; 
         } 
         else if(grid[xc][yc]=='E')//Movable. Can't return here again so setting it to 'B' now 
         { 
          //System.out.println(xc+" "+yc); 
          grid[xc][yc]='B';//now BLOCKED 
          int[]temp={xc,yc}; 
          q.add(temp);//Adding current coordinates to the queue 
         } 
        } 
       } 
      } 
      return false;//Will return false if no route possible 
     } 
    } 
} 

Código en acción: http://ideone.com/jiZKzn

Cualquier sugerencia más que bienvenidos. Saludos: D