文档章节

迷宫问题的求解(回溯法、深度优先遍历、广度优先遍历)

o
 osc_1ee7cxmx
发布于 2018/08/06 16:30
字数 2157
阅读 46
收藏 0

精选30+云产品,助力企业轻松上云!>>>

一、问题介绍

  有一个迷宫地图,有一些可达的位置,也有一些不可达的位置(障碍、墙壁、边界)。从一个位置到下一个位置只能通过向上(或者向右、或者向下、或者向左)走一步来实现,从起点出发,如何找到一条到达终点的通路。本文将用两种不同的解决思路,四种具体实现来求解迷宫问题。

  用二维矩阵来模拟迷宫地图,1代表该位置不可达,0代表该位置可达。每走过一个位置就将地图的对应位置标记,以免重复。找到通路后打印每一步的坐标,最终到达终点位置。

  封装了点Dot,以及深度优先遍历用到的Block,广度优先遍历用到的WideBlock。

private int[][] map = {                           //迷宫地图,1代表墙壁,0代表通路
        {1,1,1,1,1,1,1,1,1,1},
        {1,0,0,1,0,0,0,1,0,1},
        {1,0,0,1,0,0,0,1,0,1},
        {1,0,0,0,0,1,1,0,0,1},
        {1,0,1,1,1,0,0,0,0,1},
        {1,0,0,0,1,0,0,0,0,1},
        {1,0,1,0,0,0,1,0,0,1},
        {1,0,1,1,1,0,1,1,0,1},
        {1,1,0,0,0,0,0,0,0,1},
        {1,1,1,1,1,1,1,1,1,1}
    };
    
    private int mapX = map.length - 1;                //地图xy边界
    
    private int mapY = map[0].length - 1;
    
    private int startX = 1;                           //起点
    
    private int startY = 1;
    
    private int endX = mapX - 1;                      //终点
    
    private int endY = mapY - 1;

  //内部类,封装一个点
    public class Dot{
        private int x;            //行标
        private int y;            //列标
        
        public Dot(int x , int y) {
            this.x = x;
            this.y = y;
        }
        
        public int getX(){
            return x;
        }
        
        public int getY(){
            return y;
        }
    }
    
    //内部类,封装走过的每一个点,自带方向
    public class Block extends Dot{
        
        private int dir;          //方向,1向上,2向右,3向下,4向左
        
        public Block(int x , int y) {
            super(x , y);
            dir = 1;
        }
        
        public int getDir(){
            return dir;
        }
        
        public void changeDir(){
            dir++;
        }
    }
    
    /*
        广度优先遍历用到的数据结构,它需要一个指向父节点的索引
    */
    public class WideBlock extends Dot{
        private WideBlock parent;
        
        public WideBlock(int x , int y , WideBlock p){
            super(x , y);
            parent = p;
        }
        
        public WideBlock getParent(){
            return parent;
        }
    }

  

二、回溯法

  思路:从每一个位置出发,下一步都有四种选择(上右下左),先选择一个方向,如果该方向能够走下去,那么就往这个方向走,当前位置切换为下一个位置。如果不能走,那么换个方向走,如果所有方向都走不了,那么退出当前位置,到上一步的位置去,当前位置切换为上一步的位置。一致这样执行下去,如果当前位置是终点,那么结束。如果走过了所有的路径都没能到达终点,那么无解。下面看代码

private Stack<Block> stack = new Stack<Block>();  //回溯法存储路径的栈

public void findPath1(){
        Block b = new Block(startX,startY);
        stack.push(b);                                //起点进栈  
        while(!stack.empty()){                        //栈空代表所有路径已走完,没有找到通路
            Block t = stack.peek();
            
            int x = t.getX();                         //获取栈顶元素的x
            int y = t.getY();                         //获取栈顶元素的y
            int dir = t.getDir();                     //获取栈顶元素的下一步方向
            
            map[x][y] = 1;                            //把地图上对应的位置标记为1表示是当前路径上的位置,防止往回走
            
            if(t.getX() == endX && t.getY() == endY) {//已达终点
                return ;
            }                     
            
            switch(dir){
                case 1:                                     //向上走一步                           
                    if(x - 1 >= 0 && map[x - 1][y] == 0){   //判断向上走一步是否出界&&判断向上走一步的那个位置是否可达
                        stack.push(new Block(x - 1 , y));   //记录该位置
                    }
                    t.changeDir();                          //改变方向,当前方向已走过
                    continue;                               //进入下一轮循环
                case 2:
                    if(y + 1 <= mapY && map[x][y+1] == 0){
                        stack.push(new Block(x , y + 1));
                    }
                    t.changeDir();
                    continue;
                case 3:
                    if(x + 1 <= mapX && map[x+1][y] == 0){
                        stack.push(new Block(x + 1 , y));
                    }
                    t.changeDir();
                    continue;
                case 4:
                    if(y - 1 >= 0 && map[x][y - 1] == 0){
                        stack.push(new Block(x , y - 1));
                    }
                    t.changeDir();
                    continue;
            }
            t = stack.pop();                                    //dir > 4 当前Block节点已经没有方向可走,出栈
            map[t.getX()][t.getY()] = 0;                        //出栈元素对应的位置已经不再当前路径上,表示可达
            
        }
    }

//打印栈
    public void printStack(){
        int count = 1;
        while(!stack.empty()){
            Block b = stack.pop();
            System.out.print("(" + b.getX() + "," + b.getY() + ") ");
            if(count % 10 == 0)
                System.out.println("");
            count++;
        } }

测试结果:

 

 递归实现:

    private Stack<Block> s = new Stack<Block>();      //回溯法全局辅助栈
   private Stack<Block> stack = new Stack<Block>();  //回溯法存储路径的栈
public void findPath2(){ if(startX >= 0 && startX <= mapX && startY >= 0 && startY <= mapY && map[startX][startY] == 0){ find(startX , startY); } } private void find(int x , int y){
     map[x][y] = 1;
if(x == endX && y == endY) { s.push(new Block(x , y)); while(!s.empty()){ stack.push(s.pop()); } //return ; //在此处返回会使后续递归再次寻找路线会经过这里,如果不返回,整个函数执行完毕,所有路径都会被访问到 } s.push(new Block(x , y));if( x - 1 >= 0 && map[x - 1][y] == 0 ){ //可以往上走,那么往上走 find(x - 1 , y); } if(x + 1 <= mapX && map[x + 1][y] == 0){ //可以往下走,那么往下走 find(x + 1 , y); } if(y - 1 >= 0 && map[x][y - 1] ==0){ //往左 find(x , y - 1); } if(y + 1 <= mapY && map[x][y + 1] == 0){ find(x , y + 1); } if(!s.empty()){ s.pop(); } }

测试结果:

三、深度优先遍历

  思路:和上面的回溯法思想基本一样,能向某个方向走下去就一直向那个方向走,不能走就切换方向,所有方向都不能走了就回到上一层位置。

 

private Stack<Dot> stackDeep = new Stack<Dot>();  //深度遍历时用的存储栈
    
    private Stack<Dot> sDeep = new Stack<Dot>();      //深度遍历时用到的辅助栈

   public void findPath3() { // 判断起点的合法性
        if (startX >= 0 && startX <= mapX && startY >= 0 && startY <= mapY && map[startX][startY] == 0) {
            deepFirst(startX, startY);
        }
    }
    public void deepFirst(int x, int y) {
        Dot b = new Dot(x, y);
        sDeep.push(b);
     map[x][y] = 1; // 标记已访问
        if (x == endX && y == endY) {
            while (!sDeep.empty()) {
                stackDeep.push(sDeep.pop());
            }
            //return ;                //此处的return和上一个递归的return一样,如果返回
        }                          

        for (int i = 1; i <= 4; i++) { // 在每个方向上进行尝试
            if (i == 1) { //
                if (x - 1 >= 0 && map[x - 1][y] == 0) {
                    deepFirst(x - 1, y);
                }
            } else if (i == 2) { //
                if (y + 1 <= mapY && map[x][y + 1] == 0) {
                    deepFirst(x, y + 1);
                }
            } else if (i == 3) { //
                if (x + 1 <= mapX && map[x + 1][y] == 0) {
                    deepFirst(x + 1, y);
                }
            } else { //
                if (y - 1 >= 0 && map[x][y - 1] == 0) {
                    deepFirst(x, y - 1);
                }
            }
        }
        if(!sDeep.empty()) {
            sDeep.pop(); // 四个方向都已尝试过,并且没成功,退栈
        }
    }

    //打印深度优先遍历的栈
    public void printDeepStack(){
        int count = 1;
        while(!stackDeep.empty()){
            Dot b = stackDeep.pop();
            System.out.print("(" + b.getX() + "," + b.getY() + ") ");
            if(count++ % 10 == 0){
                System.out.println("");
            }
        }
    }

 

测试结果:

 

  栈实现、递归和深度优先遍历,这三者的执行思路是一样的,都可以看做二叉树先根遍历的变体,起点看做根节点,每个选择方向看做一个分叉,四个方向对应四个子节点,如果某个节点四个方向都走不了,那么它就是叶子节点。每走到一个叶子节点就是一条完整的执行路径,只不过不一定到达了终点。按照先根遍历的方式,最终会走完每一条路径,如果在路径中找到了终点,那么记录下这条路径线索。二叉树先根遍历的递归实现对应了上面的递归实现,只不过这里是四叉树,栈实现可以看成先根遍历的非递归算法,而深度优先遍历和先跟遍历本就有异曲同工之妙。

 

四、广度优先遍历

  思路:这种方法和前面三种是不同的思路。先从根节点出发,将当前节点的所有可达子节点依次访问,在依次访问子节点的子节点,一直下去直到所有节点被遍历。

 

private WideBlock wb;                             //广度遍历的终点节点

    /*
        广度优先遍历
    */
    public void findPath4(){
        wideFirst();
    }
    
    public void wideFirst(){
        WideBlock start = new WideBlock(startX , startY , null);
        Queue<WideBlock> q = new LinkedList<WideBlock>();  
        map[startX][startY] = 1;                       
        q.offer(start);
        while(q.peek() != null){
            WideBlock b = q.poll();
            int x = b.getX();
            int y = b.getY();
            if(x == endX && y == endY){                 //判断当前节点是否已达终点
                wb = b;
                return;
            }
            if (x - 1 >= 0 && map[x - 1][y] == 0) {     //判断当前节点的能否向上走一步,如果能,则将下一步节点加入队列
                q.offer(new WideBlock(x - 1 , y , b));  //子节点入队
                map[x - 1][y] = 1;                      //标记已访问
            }
            if (y + 1 <= mapY && map[x][y + 1] == 0) {  //判断当前节点能否向右走一步
                q.offer(new WideBlock(x , y + 1 , b));
                map[x][y + 1] = 1;
            }
            if (x + 1 <= mapX && map[x + 1][y] == 0) {
                q.offer(new WideBlock(x + 1 , y , b));
                map[x + 1][y] = 1;
            }
            if (y - 1 >= 0 && map[x][y - 1] == 0) {
                q.offer(new WideBlock(x , y - 1 , b));
                map[x][y -1] = 1;
            }
        }
    }


    //打印广度遍历的路径
    public void printWidePath(){
        WideBlock b = wb;
        int count = 1;
        while(b != null){
            System.out.print("(" + b.getX() + "," + b.getY() + ") ");
            b = b.getParent();
            if(count++ % 10 == 0){
                System.out.println("");
            }
        }
    }

 

测试结果:

  广度优先遍历找出的路径和上面三种方式的结果不一样,它找出的是最短路径。这种方式是从根节点出发,一层一层的往外遍历,当发现某一层上有终点节点时,遍历结束,此时找到的也一定是最短路径,它和二叉树的层序遍历有异曲同工之妙。

  本文个人编写,水平有限,如有错误,恳请指出,欢迎评论分享

上一篇: thymeleaf 布局layout
下一篇: python内置小工具
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
游戏与常用的五大算法---下篇

前言: 心是一个人的翅膀,心有多大,世界就有多大。很多时候限制我们的,不是周遭的环境,也不是他人的言行,而是我们自己!看不开,放不下,忘不了,把自己囚禁在灰暗的记忆里;不敢想,不...

loving_forever_
2017/01/08
0
0
游戏与常用的五大算法---下篇

前言: 心是一个人的翅膀,心有多大,世界就有多大。很多时候限制我们的,不是周遭的环境,也不是他人的言行,而是我们自己!看不开,放不下,忘不了,把自己囚禁在灰暗的记忆里;不敢想,不...

loving_forever_
2017/01/08
0
0
迷宫问题的求解(回溯法、深度优先遍历、广度优先遍历)

一、问题介绍   有一个迷宫地图,有一些可达的位置,也有一些不可达的位置(障碍、墙壁、边界)。从一个位置到下一个位置只能通过向上(或者向右、或者向下、或者向左)走一步来实现,从起...

osc_f4sv21ws
06/16
7
0
迷宫问题的求解(回溯法、深度优先遍历、广度优先遍历)

一、问题介绍   有一个迷宫地图,有一些可达的位置,也有一些不可达的位置(障碍、墙壁、边界)。从一个位置到下一个位置只能通过向上(或者向右、或者向下、或者向左)走一步来实现,从起...

随性如风
2018/08/06
0
0
广度优先和深度优先算法

回溯法 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标。 但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择, 这种走不通就退回再走的技术...

osc_qpjywoo6
2019/08/24
1
0

没有更多内容

加载失败,请刷新页面

加载更多

使用amoeba实现mysql读写分离

转载马士兵连老师笔记 使用amoeba实现mysql读写分离 1、什么是amoeba? Amoeba(变形虫)项目,专注 分布式数据库 proxy 开发。座落与Client、DB Server(s)之间。对客户端透明。具有负载均衡、...

兵荒马乱的青春
4分钟前
0
0
学Vue,就要学会vue JSX(二)

学习JSX,先了解一下createElement 提到JSX,不可避免的就要提到createElement,当你看完本节,你会发现,奇怪的知识又增多了。ok,我们接着上一部分继续讲。这一次的准备工作是了解createEleme...

osc_kurqu050
4分钟前
0
0
学Vue,就要学会vue JSX(三)

是时候使用JSX代替createElement了 接着上面的讲,当我们看到上面用createElement去实现组件,太麻烦了,别说工作效率提高了,就是那些嵌套可以嵌套正确就很赞了,所以我们需要用JSX去简化整...

osc_tq5hz9vv
6分钟前
0
0
protocol buffer使用

protocol buffer使用例子 protocol buffer是什么 https://developers.google.com/protocol-buffers 这是protocol buffer的官方网站,上边有详细的使用方式。 一般常见的序列和反序列方式就是...

RandomObject
7分钟前
0
0
小白的前端之路-HTMl

HTML——超文本标记语言 HTMl里面有标签,标签又分为单标签和双标签,也分为行级元素和块级元素 标签是用<>包裹起来的,而且必须要有<>,否则会直接显示在浏览器上面哦 现在介绍一下常用标签...

osc_e45irv7l
7分钟前
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部