Maze solving con ampiezza prima ricerca

Question

Qualcuno può spiegare come posso risolvere un labirinto utilizzando la ricerca per ampiezza prima? Devo usare la ricerca per ampiezza per trovare il percorso più breve attraverso un labirinto, ma sono così confuso.

Questo è il codice pseudo dal mio libro:

void breadth_first_search(tree T) { 
    queue!; 
    node u, v; 

    initialize(Q); 
    v = root of T; 
    visit v; 
    enqueue(Q, v); 

    while (!empty(Q)) { 
    dequeue(Q, v); 
    for (each child u of v) { 
     visit u; 
     enqueue(Q, u); 
    } 
    } 
} 

Quindi, se ho un labirinto che è memorizzato in una matrice 2D, è la "radice" (vale a dire il punto di partenza), sta per essere in maze[x][y]?

Answer 1

Risposta breve: sì

Spiegazione:

Che il codice pseudo sta rappresentando il percorso attraverso il labirinto come un percorso alla foglia di un albero. Ogni punto del labirinto è un nodo sull'albero e ogni nuovo punto a cui puoi andare da lì è figlio di quel nodo.

Per eseguire una ricerca per ampiezza, un algoritmo deve prima considerare tutti i percorsi attraverso l'albero di lunghezza uno, poi la lunghezza due, ecc. Fino a raggiungere la fine, che causerà l'arresto dell'algoritmo poiché la fine ha nessun bambino, risultante in una coda vuota.

Il codice tiene traccia dei nodi che deve visitare utilizzando una coda (Q). Prima imposta l'inizio del labirinto alla radice dell'albero, lo visita (controlla se è la fine), quindi rimuove la radice dalla coda e ripete il processo con ogni bambino. In questo modo, visita i nodi in post-it i.e. root, (ogni figlio di root), (ogni figlio del primo figlio), (ogni figlio di second child), ecc. Fino a quando non arriva alla fine.

modifica: Allo stato attuale, l'algoritmo non può terminare quando raggiunge la fine a causa di altri nodi dopo di esso nella coda. Dovrai risolvere da solo le condizioni per la rescissione.

Answer 2

Ecco un risolutore labirinto BFS completo. Se trovato, restituisce un percorso completo più breve fino al punto finale.

import java.util.*; 

public class Maze { 

    public static int[][] arr = new int[][] { 
      {0,0,0,0,0,0,0,0,0}, 
      {5,5,5,0,0,0,0,0,0}, 
      {0,0,0,5,0,0,0,0,0}, 
      {0,0,0,0,0,0,0,0,0}, 
      {0,0,0,0,0,0,0,0,0}, 
      {0,0,0,0,0,0,0,0,0}, 
      {0,0,0,0,0,0,0,0,0}, 
      {0,0,0,0,0,0,0,0,0}, 
      {0,0,0,0,0,0,0,0,9}, 
    }; 

    private static class Point { 
     int x; 
     int y; 
     Point parent; 

     public Point(int x, int y, Point parent) { 
      this.x = x; 
      this.y = y; 
      this.parent = parent; 
     } 

     public Point getParent() { 
      return this.parent; 
     } 

     public String toString() { 
      return "x = " + x + " y = " + y; 
     } 
    } 

    public static Queue<Point> q = new LinkedList<Point>(); 

    public static Point getPathBFS(int x, int y) { 

     q.add(new Point(x,y, null)); 

     while(!q.isEmpty()) { 
      Point p = q.remove(); 

      if (arr[p.x][p.y] == 9) { 
       System.out.println("Exit is reached!"); 
       return p; 
      } 

      if(isFree(p.x+1,p.y)) { 
       arr[p.x][p.y] = -1; 
       Point nextP = new Point(p.x+1,p.y, p); 
       q.add(nextP); 
      } 

      if(isFree(p.x-1,p.y)) { 
       arr[p.x][p.y] = -1; 
       Point nextP = new Point(p.x-1,p.y, p); 
       q.add(nextP); 
      } 

      if(isFree(p.x,p.y+1)) { 
       arr[p.x][p.y] = -1; 
       Point nextP = new Point(p.x,p.y+1, p); 
       q.add(nextP); 
      } 

      if(isFree(p.x,p.y-1)) { 
       arr[p.x][p.y] = -1; 
       Point nextP = new Point(p.x,p.y-1, p); 
       q.add(nextP); 
      } 

     } 
     return null; 
    } 


    public static boolean isFree(int x, int y) { 
     if((x >= 0 && x < arr.length) && (y >= 0 && y < arr[x].length) && (arr[x][y] == 0 || arr[x][y] == 9)) { 
      return true; 
     } 
     return false; 
    } 

    public static void main(String[] args) { 

     Point p = getPathBFS(0,0); 

     for (int i = 0; i < 9; i++) { 
      for (int j = 0; j < 9; j++) { 
       System.out.print(arr[i][j]); 
      } 
      System.out.println(); 
     } 

     while(p.getParent() != null) { 
      System.out.println(p); 
      p = p.getParent(); 
     } 

    } 

}