8

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

这是我书中的伪代码：

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]？

4

2 回答 2

13

这是一个完整的 BFS 迷宫求解器。如果找到，它将返回到终点的完整最短路径。在迷宫数组中arr：0表示未探索的空间，5是墙壁空间，9是目标空间。空间-1被访问后用 a 标记。

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

    }

}
于 2014-11-13T11:07:40.190 回答
6

简短的回答：是的

解释：

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

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

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

编辑：就目前而言，由于队列中的其他节点，算法在到达末尾时可能不会终止。您必须自己制定终止条件。

于 2013-05-03T20:32:11.207 回答