资讯专栏INFORMATION COLUMN

采用矩阵+深度优先算法解决迷宫问题

yankeys / 2921人阅读

摘要:所谓深度优先算法,百科的解答是这样的深度优先搜索算法,简称是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。这一过程一直进行到已发现从源节点可达的所有节点为止。

所谓深度优先算法,百科的解答是这样的

深度优先搜索算法(Depth-First-Search),简称DFS,是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

通俗的说,就是足够“深”的遍历树的所有节点分支并且遍历过的节点不会再去访问,很适合做网络爬虫,你懂得^ ^

而迷宫问题也是数据结构里面一道经典的问题了,首先我们先用矩阵创建一个迷宫;

const arr = [
        [0,0,0,1,0],
        [0,1,1,1,0],
        [0,1,0,0,0],
        [0,0,0,1,0],
        [0,1,1,1,0]
    ];

其中数字1代表墙壁,数字0代表路,最左上角代表入口,最右下角代表出口,这里我们不考虑“死路”的情况

const arr = [
    [0,0,0,1,0],
    [0,1,1,1,0],
    [0,1,0,0,0],
    [0,0,0,1,0],
    [0,1,1,1,0]
];//创建迷宫

const pathX = [1,-1,0,0];//创建一个数组代表上下左右,在advance这个函数会用到
const pathY = [0,0,-1,1];//同上,区别在于矩阵的行和列
let _arrLength = arr.length-1;
let _arrElementLength = arr[0].length-1;
let i=0,j=0;
(function(){
    console.time("time")//用于测试运算时间

    arr[0][0] = 3;//数字3代表已经走过的路,一开始默认从入口进入

    function matrix(i,j){

        let k,newi,newj;

        for(k = 0;k<4;k++){ //上下左右总共四个方向

            if (advance(i,j,k)) {   
                /*
                通过advance函数的判断返回一个可走的路的点
                */
                newi = i + pathX[k];
                newj = j + pathY[k];   
                
                arr[newi][newj] = 3;//将这个点定义为已走过的点
                
                /*
                判断此时是否已经到了终点如果没有则递归
                */
                if (newi == _arrLength && newj == _arrElementLength) {
                    end()
                } else {   
                    matrix(newi,newj);   
                }   
            }
        }
        arr[i][j] = 2

    }
    matrix(0,0)

    function advance(i,j,k){
        var bool = true;
         /*
        每走一步路就判断其上下左右是否还有路可走
        */
        i += pathX[k];
        j += pathY[k];
        /*
        判断临界范围,保证在迷宫范围内
        */
        if(i<0||i>_arrLength||j<0||j>_arrElementLength){
            bool = false;
        }else if(arr[i][j]!=0){
            bool = false;
        }
        return bool;
    }


    /*
    负责输出结果
    */
    function end(){
        let i,j,newArr=[];
        for (i = 0; i < _arrLength+1; i++) {   
            for (j = 0; j < _arrLength+1; j++) {   
                if (arr[i][j] == 3) { 
                    newArr.push("V");  
                } else {   
                    newArr.push("*");   
                }
            }   
        }
        /*
        下面这段代码只是为了能够在控制台看得更直观,可无,因为写得有点笨拙
        */
        newArr.splice(0,0,"")
        newArr.splice(6,0,"
");
        newArr.splice(12,0,"
");
        newArr.splice(18,0,"
");
        newArr.splice(24,0,"
");
        console.log(newArr.join(" "));
    }
    console.timeEnd("time")
})()

最终的路线图如下

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/81299.html

相关文章

  • 采用矩阵+深度优先算法解决迷宫问题

    摘要:所谓深度优先算法,百科的解答是这样的深度优先搜索算法,简称是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。这一过程一直进行到已发现从源节点可达的所有节点为止。 所谓深度优先算法,百科的解答是这样的 深度优先搜索算法(Depth-First-Search),简称DFS,是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过...

    bang590 评论0 收藏0
  • 算法(第4版) Chapter 4.1 无向图

    摘要:边仅由两个顶点连接,并且没有方向的图称为无向图。用分隔符当前为空格,也可以是分号等分隔。深度优先算法最简搜索起点构造函数找到与起点连通的其他顶点。路径构造函数接收一个顶点,计算到与连通的每个顶点之间的路径。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter...

    kamushin233 评论0 收藏0
  • 回溯算法

    摘要:回溯算法主要思想回溯算法的基本思想是从一条路往前走,能进则进,不能进则退回来,换一条路再试。回溯算法说白了就是穷举法。回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。用回溯算法解决问题的一般步骤为定义一个解空间,它包含问题的解。 回溯算法 主要思想 回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。八皇后问题就是回溯算法的典型,第一步按照顺序放一个皇...

    ctriptech 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<