深度优先与广度优先搜索求解(以迷宫问题为例)

一、迷宫问题介绍

给定一个迷宫(以5×5为例),指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(maze problem)。

迷宫可以以二维数组来存储表示。0表示通路,1表示障碍。注意这里规定移动可以从上、下、左、右四方方向移动。坐标以行和列表示,均从0开始,给定起点(0,0)和终点(4,4),找出一条可行的线路(如果有,没有返回错误信息)。

二、求解思路

因为迷宫问题很难直接通过数学方法求解,故遍历是解决此问题的最有效方式。由数据结构的相关知识知,迷宫问题的求解可以抽象为连通图的遍历,故深度优先搜索和广度优先搜索是解决此问题的两种有效方法。

1、深度优先搜索(DFS)

其优点:无需记录前驱结点确认后退情况。

其缺点:找到的第一条可行路径不一定是最短路径。
(如果需要找到最短路径,那么需要找出所有可行路径后,再逐一比较,求出最短路径)

2、广度优先搜索(BFS)

其优点:找出的第一条路径就是最短路径。

其缺点:需要记录结点的前驱结点,来形成路径,开支较高。

三、数据结构知识补充(知晓请跳过此部分)

以下资料来自维基百科(中文版)对应词条,略做改动。

队列,即queue,是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现(在Java中可以直接将某一链表赋值给队列,我们稍后可能会在BFS算法中用到)。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。

堆栈,即stack,又称为栈或堆叠,是一种特殊的串列形式的数据结构(用一维数组或连结串列的形式来完成),其特殊之处在于只能允许在链接串列或阵列的一端(称为堆叠顶端指标,top)进行加入数据(push)和输出数据(pop)的运算;由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。

四、算法解释+代码实现

一、深度优先搜索(DFS)[代码由 韩宝坤 提供,感谢!]

韩宝坤先(da)生(lao)暂未给出解释说明,请大家根据代码自行理解……

import java.util.*;

public class Maze {
    private int width;
    private int height;
    private int[][] map;  // 地图  , 左上角起点,右下角终点
    // 0 表示可以走,1 表示墙不能走
    private int[][] deepth; //记录走过的距离
    private int step;// 步数
    private int[][] route; //  route[n][2],表示路线
    private int direction[][]; //方向

    public Maze() {
        height = 16;
        width = 16;
        step=0;
        initDirection();
        makeMap();
    }
    public Maze(int height,int width) {
        this.height=height;
        this.width=width;
        step=0;
        initDirection();
        makeMap();
    }
    private void  initDirection(){
        direction = new int[4][2];
        direction[0][0] = 0;
        direction[0][1] = 1;
        direction[1][0] = 1;
        direction[1][1] = 0;
        direction[2][0] = -1;
        direction[2][1] = 0;
        direction[3][0] = 0;
        direction[3][1] = -1;
    }
    public void makeMap() {
        map = new int[height + 5][width + 5];
        Random random = new Random();
        for (int i = 1; i <= height; i++) {
            for (int j = 1; j <= width; j++) {
                int tmp = random.nextInt() ;
                if (tmp<0) tmp=-tmp;
                map[i][j]=tmp%4;
                if (map[i][j] != 0) map[i][j] = 0;
                else map[i][j] = 1;
            }
        }
        map[1][1] = 0;
        map[height][width] = 0;
    }

    private boolean dfs(int x, int y, int step) {
        if (x < 1 || x > height || y < 1 || y > width) return false;
        if (map[x][y] == 1) return false;
        if (step >= deepth[x][y]) return false;
        deepth[x][y] = step;
        if (x == width && y == width) {
            route[step][0] = x;
            route[step][1] = y;
            this.step++;
            return true;
        }
        for (int i = 0; i < 4; i++) {
            if (dfs(x + direction[i][0], y + direction[i][1], step + 1) == true) {
                route[step][0] = x;
                route[step][1] = y;
                this.step++;
                return true;
            }
        }
        return false;
    }

    public boolean findRoute() {
        deepth = new int[height + 5][width + 5];
        route = new int[(height + 5) * (width + 5)][2];
        step = 0;
        for (int i = 1; i <= height; i++) {
            for (int j = 1; j <= width; j++) {
                deepth[i][j] = 1000;
            }
        }
        dfs(1, 1, 0);
        if (deepth[height][width] == 1000) return false;
        else return true;
    }

    public void showMap() {
        for (int i = 1; i <= height; i++) {
            for (int j = 1; j <= width; j++) {
                System.out.printf("%d ", map[i][j]);
            }
            System.out.println();
        }
    }

    public void showRoute() {
        for (int i = 0; i < step; i++) {
            System.out.println(route[i][0] + " " + route[i][1]);
        }
    }

}

public class Main {
    public static void main(String[] args) {
        Maze maze = new Maze();
        maze.showMap();
        boolean result =maze.findRoute();
        if (result==true) {
            System.out.println("路线为:");
            maze.showRoute();
        }else {
            System.out.println("路线不通");
        }
    }
}

二、广度优先算法(BFS)

我们从起点开始,将每一个坐标(基于Point类实例化的对象,同时记录当前位置和前步位置)排入队列中,然后在队列非空的情况下取出最上方的坐标对象(即最后一步的点)并压入堆栈并标记此位置被访问过,然后一次探索当前位置附近的四个位置以判断下一步的行走路线,若发现可行则建立新节点记录,同时排入队列,反之此路不通则放弃该路线,继续从队列中取出上一步的位置并继续探索,依次递归,直到进入迷宫出口。

出口位置通过最后一次的坐标(堆栈最顶端)的步数+1输出总步数,并从当前点坐标开始,依次取出堆栈中的元素,从而实现逆向输出此条可行路线,同时方法返回0,反之返回-1。主程序根据方法的返回值进行判断,若不为0则输出无可行路线。

以下为参考代码实现:

import java.util.LinkedList;
import java.util.Stack;         //堆栈,后进先出
import java.util.Queue;         //队列,先进先出

public class BFS {

    private static int N=5;

    int [][] maze;                    //定义迷宫地图
    int [][] visitedSign;             //定义访问过的位置
    int [][] direction={                         //{x,y}
            {-1,0},{0,-1},{1,0},{0,1}            //左,上,右,下
    };

    BFS(){
        maze=new int[][]{
            {0,0,0,0,0},
            {0,1,0,1,0},
            {0,1,1,0,0},
            {0,1,1,0,1},
            {0,0,1,0,0}
        };
        visitedSign=new int [N][N];
    }

    class Node{                     //建立一个类以记录节点位置信息
        int x,y;
        int step;
        int preX,preY;
        Node(int x, int y, int preX, int preY, int step){
           this.x=x;
           this.y=y;
           this.preX=preX;
           this.preY=preY;
           this.step=step;
        }
    }

    int bfsProcess(){
        Node node=new Node(0,0,-1,-1,0);
        Queue<BFS.Node> queue = new LinkedList<Node>();         //队列,先进先出
        Stack<BFS.Node> stack=new Stack<Node>();                //堆栈,后进先出
        queue.offer(node);                  //起点位置加入队列
        while(!queue.isEmpty()){
            Node head=queue.poll();         //取出队列最顶端元素
            stack.push(head);               //将其压入堆栈,用于回溯路径
            visitedSign[head.x][head.y]=1;
            for (int i=0; i<4; i++){                //四个方向依次判断
                int x=head.x+direction[i][0];
                int y=head.y+direction[i][1];
                if(x==N-1 && y==N-1 && maze[x][y]==0 && visitedSign[x][y]==0) {         //定义终点的操作
                    Node top=stack.pop();
                    System.out.println("总步数:" + (top.step + 1));
                    System.out.println("逆向路线:");
                    System.out.println("("+(N-1)+","+(N-1)+")");
                    System.out.println("("+top.x+","+top.y+")");
                    int preX=top.preX;
                    int preY=top.preY;
                    while (!stack.isEmpty()){
                        top=stack.pop();
                        if(preX==top.x && preY==top.y){
                            System.out.println("("+preX+","+preY+")");
                            preX=top.preX;
                            preY=top.preY;
                        }
                    }
                    return 0;
                }
                if(x>=0 && x<N && y>=0 && y<N && maze[x][y]==0 && visitedSign[x][y]==0){    //非边界,未撞墙,未曾到达过
                    Node newNode=new Node(x,y,head.x,head.y,head.step+1);
                    queue.offer(newNode);
                }
            }

        }
        return -1;
    }

    public static void main(String[] args) {
        BFS bfs=new BFS();
        if(bfs.bfsProcess()!=0){
            System.out.println("该迷宫没有出口。");
        }
    }

}

 

分享