Maze giải quyết với tìm kiếm đầu tiên rộng

Question

Ai đó có thể vui lòng giải thích làm thế nào tôi có thể giải quyết một mê cung bằng cách sử dụng tìm kiếm đầu tiên? Tôi cần phải sử dụng tìm kiếm đầu tiên chiều rộng để tìm đường đi ngắn nhất qua mê cung, nhưng tôi rất bối rối.

Đây là mã giả từ cuốn sách của tôi:

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

Vì vậy, nếu tôi có một mê cung được lưu trữ trong một ma trận 2D, là "gốc" (tức là điểm khởi đầu), sẽ ở maze[x][y]?

Answer 1

Câu trả lời ngắn: yes

Giải thích:

Đó là mã giả là đại diện cho con đường qua mê cung như một con đường để chiếc lá của một cây. Mỗi điểm trong mê cung là một nút trên cây và mỗi điểm mới bạn có thể đi từ đó là một đứa trẻ của nút đó.

Để thực hiện tìm kiếm đầu tiên, trước tiên, thuật toán phải xem xét tất cả các đường dẫn qua cây có chiều dài, sau đó là chiều dài hai, v.v. cho đến khi kết thúc, điều này sẽ khiến thuật toán ngừng không có trẻ em, dẫn đến một hàng đợi rỗng.

Mã theo dõi các nút cần truy cập bằng cách sử dụng hàng đợi (Q). Đầu tiên nó đặt khởi đầu của mê cung đến gốc cây, thăm nó (kiểm tra xem nó có phải là kết thúc), sau đó loại bỏ gốc từ hàng đợi và lặp lại quá trình với mỗi đứa trẻ. Bằng cách này, nó sẽ thăm các nút theo thứ tự, tức là, (mỗi đứa con của người chủ), (mỗi đứa con đầu tiên), (mỗi đứa con thứ hai), vv cho đến khi nó kết thúc.

chỉnh sửa: Khi nó đứng, thuật toán có thể không chấm dứt khi nó đạt đến kết thúc vì các nút khác sau khi nó trong hàng đợi. Bạn sẽ phải tự hoàn thiện điều kiện để tự chấm dứt.

Answer 2

Đây là bộ giải BFS Maze đầy đủ. Nó trả về một đường đi ngắn nhất đến điểm cuối nếu được tìm thấy.

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

    } 

}