Rozwiązywanie labiryntów z szerokim zakresem wyszukiwania

Question

Czy ktoś mógłby wyjaśnić, jak mogę rozwiązać labirynt, korzystając z pierwszego zakresu wyszukiwania? Muszę użyć szerokości pierwszego wyszukiwania, aby znaleźć najkrótszą ścieżkę przez labirynt, ale jestem tak zdezorientowany.

To pseudo kod z mojej książki:

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

Więc jeśli mam labirynt, który jest przechowywany w matrycy 2D, jest „root” (czyli punkt wyjścia), będzie w maze[x][y]?

Answer 1

Krótka odpowiedź: tak

Objaśnienie:

To pseudo kod reprezentuje drogę przez labirynt jako ścieżkę do liści drzewa. Każde miejsce w labiryncie jest węzłem na drzewie i każde nowe miejsce, do którego można przejść, jest potomkiem tego węzła.

Aby wykonać pierwsze wyszukiwanie, algorytm musi najpierw rozważyć wszystkie ścieżki w drzewie długości 1, a następnie długości 2 itd., Aż osiągnie koniec, co spowoduje zatrzymanie algorytmu od zakończenia bez dzieci, co powoduje pustą kolejkę.

Kod śledzi węzły, które musi odwiedzić za pomocą kolejki (Q). Najpierw ustawia początek labiryntu do katalogu głównego drzewa, odwiedza go (sprawdza, czy to koniec), a następnie usuwa root z kolejki i powtarza proces z każdym dzieckiem. W ten sposób odwiedza węzły w post-rzędzie, tj. Root (każde dziecko root), (każde dziecko pierwszego dziecka), (każde dziecko drugiego dziecka) itd., Aż do końca.

edytuj: W stanie, algorytm może nie kończyć się, gdy dojdzie do końca z powodu innych węzłów po nim w kolejce. Będziesz musiał sam rozwiązać warunek zakończenia.

Answer 2

Oto pełny solver BFS Maze. Zwraca pełną najkrótszą ścieżkę do punktu końcowego, jeśli zostanie znaleziony.

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(); 
     } 

    } 

}