首页 > 作文

详解Java利用深度优先遍历解决迷宫问题

更新时间:2023-04-04 21:19:01 阅读: 评论:0

目录
什么是深度优先一个简单的例子程序实现

什么是深度优先

什么是深度,即向下,深度优先,即向下优先,一口气走到底,走到底发现没路再往回走。

在算法实现上来讲,深度优先可以考虑是递归的代名词,深度优先搜索必然需要使用到递归的思路。

有的人可能会说了,我可以用栈来实现,以迭代的方式,那么问题来了,栈这种数据结构,同学们认为是否也囊括了递归呢?java语言的方法区本身也是实现在一个栈空间上的。

一个简单的例子

我们以一个简单的迷宫为例,以1代表墙,0代表路径,我们构造一个具有出入口的迷宫。

1 1 0 1 1 1 1 1 1

1 0 0 0 0 0 0 1 1

1 0 1 1 1 1 0 1 1

1 0 0 0 0 1 0 0 1

1 1 1 1 1 1 1 0 1

以上面这个0为入口,下面这个0为出口,那么深度优先的算法遍历顺序,方向的遍历顺序为左下右上,以dp[0][2]为入口,我把这个过程列在下面了:

第一步:

dp[0][2] -> dp[1][2]

第二步:

dp[1][2] -> dp[1][1]

第三步:

dp[1][1] -> dp[2][1]

第四步:

dp[2][1] -> dp[3][1]

第五步:

dp[3][1] -> dp[3][2]

第六步:

dp[3][2] -> dp[3][3]

第七步:

dp[3][3] -> dp[3][4]

第八步:

dp[3][4] -> dp[3][5] 由于 dp[3][5]是墙,所以深度优先算法需要开始回退,最终会回退到dp[1][2]这个位置,然后向右走

第八步:

dp[1][2] -> dp[1][3]

第九步:

dp[1][3] -> dp[1][4]

第十步:

dp[1][4] -> dp[1][5]

第十一步:

dp[1][5] -> dp[1][6]

第十二步:

dp[1][6] -> dp[2][6]

第十三步:

dp[2][6] -> dp[3][6]

第十四步:

dp[3][6] -> dp[3][7]

第十五步:

dp[3][7] -> dp[4][7] 终点,程序退出

可以发现,深度优先算法有点像我们的人生,需要不断试错,错了就退,直到找到一条通往出口的路。

现在让我们动手用代码实现一下上面的步骤吧。

程序实现

以深度优先的方式解决这个问题,主要考虑两点,首先是如何扩展节点,我们的顺序是左,下,右,上,那么,应该以什么样的方式实现这个呢?第二点,就是如何关于老师的歌实现深度优先,虽然原理上肯定是递归,但是应该如何递归呢?要解决这两个问题,请看示例代码,以java为例:

package com.chaojilaji.book;import com.chaojilaji.book.util.inpututils;import java.util.hasht;import java.util.t;import static com.chaojilaji.book.util.checkutils.canadd;public class dfs {    public static integer dfs(string[][] a, int currentx, int currenty, int chux, int chuy, t<integer> cache) {        system.out.println(currenty + " " + currentx);        if (currentx == chux && currenty == chuy) {            return 1;        }        // todo: 2022/1/11 枚举子节点,左 下 右 上        int[] x = new int[]{-1, 0, 1, 0};        int[] y = new int[]{0, 1, 0, -1};        for (int i = 0; i < 4; i++) {            if (canadd(a, currentx + x[i], currenty + y[i], cache)) {                integer tmp = dfs(a, currentx + x[i], currenty + y[i], chux, chuy, cache);                if (tmp != 0) {                    system.out.println(currenty + " " + currentx + " 结果路径");                    return tmp + 1;                }            }        }        system.out.println(currenty + " " + currentx + " 回滚");        return 0;    }    public static integer getans(string[][] a) {        int m = a[0].length;        int n = a.length;        int rux = -1, ruy = 0;        int chux = -1, chuy = n - 1;        for (int i = 0; i < m; i++) {            if (a[0][i].equals("0")) {            become    // todo: 2022/1/11 找到入口                rux = i;            }            if (a[n - 1][i].equals("0")) {                chux = i;            }        }        t<integer> cache = new hasht<>();        cache.add(rux * 100000 + ruy);        system.out.println("打印行走过程");        return dfs(a, rux, ruy, chux, chuy, cache)-1;    }    public static void demo() {        string x = "1  1  0  1  1  1  1  1  1\n" +                "1  0  0  0  0  0  0  1  1\n" +                "1  0  1  1  1  1  0  1  1\n" +                "1  0  0  0  0  1  0  0  1\n" +                "1  1  1  1  1  1  1  0  1";        string[][] a = inpututils.getinput(x);        integer ans = getans(a);        system.out.println(ans == -1 ? "不可达" : "可达,需要行走" + ans + "步");    }    public 百家讲坛汉代风云人物static void main(string[] args) {        demo();    }}

这里的canadd方法是临界判断函数,如下:

/**     * 临界判断     * @param a     * @param x     * @param y     * @param cache     * @return     */public static boolean canadd(string[][] a, integer x, integer y, t<integer> cache) {    int m = a[0].length;    int n = a.length;    if (x < 0 || x >= m) {        return fal;    }    if (y < 0 || y >= n) {        return fal;    }    if (a[y][x].equals("0") && !cache.contains(x * 100000 + y)) {        cache.add(x * 100000 + y);        return true;    }    return fal;}

可以瞧见,这里面最冬天的形容词核心的代码在于dfs这个函数,让我们来深入分析一波

public static integer dfs(string[][] a, int currentx, int currenty, int chux, int chuy, t<integer> cache) {    system.out.println(currenty + " " + currentx);    if (currentx == chux && currenty == chuy) {        return 1;    }    // todo: 2022/1/11 枚举子节点,左 下 右 上    int[] x = new int[]{-1, 0, 1, 0};    int[] y = new int[]{0, 1, 0, -1};    for (int i = 0; i < 4; i++) {        if (canadd(a, currentx + x[i], currenty + y[i], cache)) {            integer tmp = dfs(a, currentx + x[i], currenty + y[i], chux, chuy, cache);            if (tmp != 0) {                system.out.println(currenty + " " + currentx + " 结果路径");                return tmp + 1;            }        }    }    system.out.println(currenty + " " + currentx + " 回滚");    return 0;}

首先,dfs深度优先,首先应该写的是判断终止条件,这里的终止条件就是到达终点,即目前的横纵坐标等于出口的横纵坐标。

然后,我们利用两个方向数组作为移动方案,也就是

// todo: 2022/1/11 枚举子节点,左 下 右 上    int[] x = new int[]{-1, 0, 1, 0};    int[] y = new int[]{0, 1, 0, -1};    for (int i = 0; i < 4; i++) {        if (canadd(a, currentx + x[i], currenty + y[i], cache)) {        }    }

这种方法,是数组类型的移动方式的兼容写法,不管你的移动方向有多少,都可以配在x和y两个数组中。定义了四个方向,现在我们需要思考递归的过程。

既然我完成的时候是返回1,那么其实如果在这条路上的所有都应该加1,所以,就有了下面的判断

if (canadd(a, currentx + x[i], currenty + y[i], cache)) {    integer tmp = dfs(a, currentx + x[i], currenty + y[i], chux, chuy, cache);    if (tmp != 0) {        system.out.println(currenty + " " + currentx + " 结果路径");        return tmp + 1;    }}

当子dfs出来的结果不为0,说明该子dfs是可以到达出口的,那么直接把结果加1返回氯化钠电解给上层即可。如果子dfs出来的结果为0,说明该子dfs是不能到达出口的,就直接返回0即可。

到此这篇关于详解java利用深度优先遍历解决迷宫问题的文章就介绍到这了,更多相关java深度优先遍历内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com!

本文发布于:2023-04-04 21:18:59,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/fanwen/zuowen/36386f06819b538830e2b7b35c1af8d9.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

本文word下载地址:详解Java利用深度优先遍历解决迷宫问题.doc

本文 PDF 下载地址:详解Java利用深度优先遍历解决迷宫问题.pdf

下一篇:返回列表
标签:递归   深度   遍历   节点
相关文章
留言与评论(共有 0 条评论)
   
验证码:
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图