広範囲の最初の検索で迷路を解決する

Question

広大な最初の検索を使用して迷路を解決するにはどうすれば説明できますか？私は迷路を通る最短経路を見つけるために幅優先探索を使う必要がありますが、私はとても混乱しています。

これが私の本からの擬似コードである：私は2D行列に格納された迷路を持っている場合

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

だから、であることを行って、「ルート」（すなわち出発点）でありますmaze[x][y]？

Answer 1

短い答え：はい

説明：

擬似コードは、ツリーのリーフへのパスとして迷路のパスを表すされていること。迷路の各スポットは、ツリー上のノードであり、そこから行くことができる新しいスポットはそのノードの子です。

幅広い最初の検索を行うために、アルゴリズムは最初に、長さが1、次に長さが2などのすべてのパスを終点に達するまで考慮しなければなりません。子はなく、結果として空のキューになります。

コードは、キュー（Q）を使用して訪問する必要があるノードを追跡します。最初に迷路の始まりをツリーのルートに設定し、それを訪問し（終わりであるかどうかをチェックする）、ルートからキューを削除し、各子と共にプロセスを繰り返します。このようにして、ノードはポストオーダー、すなわちルート、ルートの各子、（第1の子の各子）、（第2の子の各子）などを最後まで訪れる。

編集：それは、キュー内の他のノードのためにアルゴリズムが終了に達したときに終了しないことがあります。あなたは自分自身を終了するための条件をライトアップする必要があります。

Answer 2

完全なBFS迷路ソルバーです。見つかった場合、エンドポイントまでの完全な最短パスを返します。

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

    } 

}