首页 文章

迷宫解决广度优先搜索

提问于
浏览 次
7

有人可以解释我怎样才能使用广度优先搜索来解决迷宫问题？我需要使用广度优先搜索来找到迷宫中的最短路径，但我很困惑 .

这是我书中的伪代码：

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矩阵中的迷宫，那么"root"（即起点）是否会在_2781371中？

breadth-first-search maze

2 回答

  • 5

    简短回答：是的

    说明：

    伪代码表示通过迷宫的路径作为树叶的路径 . 迷宫中的每个点都是树上的一个节点，您可以从那里去的每个新点都是该节点的子节点 .

    为了进行广度优先搜索，算法首先必须考虑通过长度为1的树，然后是长度为2的树的所有路径，直到它到达结尾，这将导致算法停止，因为结束没有子节点，结果在一个空的队列中 .

    代码使用队列（Q）跟踪它需要访问的节点 . 它首先将迷宫的起点设置为树的根，访问它（检查它是否结束），然后从队列中删除根并为每个子节点重复该过程 . 以这种方式，它按顺序访问节点，即根，（根的每个孩子），（第一个孩子的每个孩子），（第二个孩子的每个孩子）等，直到它结束 .

    编辑：就目前而言，算法在到达末尾时可能不会因为队列中的其他节点而终止 . 你必须自己做好终止条件 .

    回复于
  • 11

    这是一个完整的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();
        }

    }

}
    回复于

相关问题