通过广度优先搜索解决迷宫

Question

有人可以解释一下如何使用广度优先搜索来解决迷宫吗？我需要使用广度优先搜索来找到穿过迷宫的最短路径，但我很困惑。

这是我书中的伪代码：

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

因此，如果我有一个存储在 2D 矩阵中的迷宫，那么“根”（即起点）将位于

maze[x][y]

？

Answer 1

这是一个完整的 BFS 迷宫求解器。如果找到，它将返回到终点的完整最短路径。迷宫数组

arr

中：

0

表示未探索的空间，

5

是墙壁空间，

9

是目标空间。空间在被访问后会标有

-1

。

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

    }

}

Answer 2

简短回答：是的

说明：

该伪代码将穿过迷宫的路径表示为通往树叶的路径。迷宫中的每个点都是树上的一个节点，您可以从那里到达的每个新点都是该节点的一个子节点。

为了进行广度优先搜索，算法首先必须考虑长度为一的树的所有路径，然后是长度为二的树，依此类推，直到到达末尾，这将导致算法停止，因为末尾没有子节点，导致队列空。

代码通过使用队列（Q）来跟踪它需要访问的节点。它首先将迷宫的起点设置为树的根，访问它（检查它是否是终点），然后从队列中删除根，并对每个孩子重复该过程。这样，它按后序访问节点，即根、（根的每个子节点）、（第一个子节点的每个子节点）、（第二个子节点的每个子节点）等，直到到达末尾。

编辑：就目前情况而言，算法在到达末尾时可能不会终止，因为队列中有其他节点在它后面。您必须自己写下终止条件。