Ricerca in ampiezza su una griglia 8x8 in Java

Question

Quello che sto cercando di fare è contare quanti spostamenti ci vogliono per raggiungere l'obiettivo utilizzando il percorso più breve. Deve essere fatto utilizzando una ricerca per ampiezza prima. Metto la griglia 8x8 in un array 2d che è riempito con uno di quattro caratteri, E per vuoto (può spostarsi in questi punti), B per bloccato (non può spostarsi qui), R per robot (punto di partenza) o G per obiettivo. L'algoritmo doveva controllare gli spazi mobili nell'ordine in alto, a sinistra, a destra, poi in basso, che credo di aver fatto correttamente. Dopo aver controllato un nodo, cambia il suo contenuto in una "B". Se non è possibile raggiungere l'obiettivo, è necessario restituire 0.

Ho modificato il mio codice per implementare quello che mi ha detto Kshitij e funziona perfettamente. Ero troppo stanco per vedere che non stavo inizializzando la mia coda dopo ogni nuovo set di dati lol. Grazie per l'aiuto!

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

Avrete bisogno di memorizzare 2 cose nella vostra coda. Chiamiamo ogni elemento della tua coda un nodo.

1. posizione (che già negozio)
2. conteggio (mosse necessarie per raggiungere questa posizione dalla posizione di partenza)

Si inizia assegnando il numero della vostra posizione iniziale a 0.

il modo in cui funziona l'algoritmo è:

1. si pop un nodo dalla coda
2. si determina dove si può andare dalla posizione specificata dal nodo appena spuntato. Cioè, se lo tratti come "fare un albero al volo", stai determinando i figli del nodo che hai prelevato dalla coda
3. aggiungi questi bambini alla coda.

Nel terzo passaggio, quando si aggiunge un nodo figlio alla coda, è necessario determinare il conteggio da aggiungere a questo nodo. Questo conteggio è semplicemente il count of the parent node (that you popped in step 1) + 1

Infine, il valore restituito sarebbe il numero associato al nodo che trasporta la posizione di destinazione.

Ad esempio, consente di lavorare con una griglia 4x4, in cui la posizione [0,0] è l'inizio e la posizione [0,3] è la destinazione.

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

Inizialmente, la coda sarebbe:

[{(0, 0), 0}] 

in cui il valore all'interno della () è la posizione, e il secondo valore all'interno della {} è il conteggio.

Si apre questo nodo dalla coda e si stabilisce che è possibile ottenere posizioni (0,1) e (1,0). Quindi aggiungi gli articoli {(0, 1), 1} e {(1, 0), 1} alla coda. Si noti che il conteggio è 1 perché il conteggio del nodo spuntato era 0 e abbiamo incrementato che di 1. La coda ora assomiglia:

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

si pop il primo elemento, rendersi conto che non ha figli vitali, così vai avanti

Si apre l'elemento rimanente e si scopre che fornisce un nodo a cui è possibile accedere, in posizione (2, 0). Poiché il nodo che hai fatto scoppiare ha il conteggio 1, aggiungi questa nuova posizione accoppiata con count = 1 + 1 = 2 alla coda.

Alla fine, si pop il nodo gol di coda, ed è conteggio sarà 9.

Modifica

Se si desidera ottenere il percorso dalla sorgente alla destinazione, il la codifica corrente non funziona così com'è. Avresti bisogno di mantenere un array 2D separato di dimensione 8x8 con i conteggi invece di codificarli nel nodo stesso. E quando finalmente trovi il conteggio per la destinazione, fai il backtrack dalla destinazione alla sorgente usando l'array di conteggi 2D. In sostanza, se puoi raggiungere la destinazione in 9 mosse, puoi raggiungere una delle sue posizioni adiacenti in 8 mosse. Quindi trovi la posizione che conta 8 ed è adiacente alla destinazione. Si ripetono iterativamente fino a quando non si arriva alla fonte.

Il metodo che hai descritto, in cui aggiungi un elemento aggiuntivo ai nodi, non funziona. Lascerò a voi per scoprire perché, dal momento che questo è i compiti :)

Answer 2

Ecco una bella alternativa al codice. Esattamente la stessa idea, ma non c'è bisogno delle tante "se" condizioni in cui si controlla la validità di ciascuna coordinata. Tutto questo può essere fatto in un colpo solo. Dare un'occhiata.

Ho commentato la spiegazione il più possibile. È leggibile anche per le persone che non hanno la minima idea. Mi è capitato di imbattersi nella tua domanda quando stavo implementando una soluzione per un problema simile (lo stesso?) In cui un ragazzo intrappolato in un labirinto doveva trovare la sua via d'uscita. C'erano trappole (B) e aree mobili (E) nella griglia. L'obiettivo era raggiungere la sua destinazione (G).

Ad ogni modo, ecco il codice generalizzato. Prendo il no di righe, colonne e poi la griglia completa. Sto solo stampando se è possibile RAGGIUNGERE la destinazione o no. Il resto lo lascio fino a qualcuno che sta leggendo questo come un esercizio per essere sicuri di aver capito il codice;)

mente il fatto che il obiettivo principale della mia risposta è quello di mostrare che la dimensione dei tuoi BFS la funzione potrebbe essere ridotta. Sto postando la mia intera soluzione solo per dare l'idea generale di BFS applicata in una griglia da quando ho faticato durante l'apprendimento. Si spera che questo possa aiutare qualcuno bloccato nella stessa situazione. Se vuoi che la posizione o il percorso seguiti o qualcosa, seguire le istruzioni delle risposte in questa domanda. Fai da te;)

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 
     } 
    } 
} 

Codice in azione: http://ideone.com/jiZKzn

Eventuali suggerimenti più benvenuti. Saluti: D