取法其上,得乎其中

DFS深度优先搜索算法与走迷宫

概念

DFS算法的思想实际上就是以优先搜索更深层次的目标为目的的一种编程算法。

假设拥有上图为例的二叉树数据。使用DFS这种思想进行遍历的顺序为:

1——2——4——5——3——6。当搜索的2的时候,它依然拥有子树,所以往下走,因此输出4,假设4下面还有,也会继续往下!当这条路线遍历完,它才会往上返回。 很明显,DFS需要掌握递归的思想。

使用

通过以上概念,实际上DFS就是暴力破解。而它能解决什么样的难题的呢?最为经典的一道就是 “走出迷宫”。

分析

我们都知道,当我们走进迷宫的时候,会有很多个方向让你选择,有的是死路,有的是活路,你只有依靠运气或者将每一个路线全部都走一遍,这样才能走出迷宫。在现实生活中如此,如果在计算机世界里,我们只需要使用DFS算法就可以做到。

通过以上概念分析,当我们使用DFS算法的概念去玩迷宫游戏的时候,它会对不同方向的路线一条路走到黑,当得知不通时便会返回测试下一条路线。

创建迷宫

我们直接采用一个二维数组作为迷宫,1为墙,即走不通,0为可走。见下图,以0,0坐标为起点,8,8为终点。其中一条能够通往重点的路线为:

0,0 =>0,1 =>1,1 =>2,1 =>3,1 =>4,1 =>5,1 =>5,2 =>6,2 =>7,2 =>7,3 =>7,4 =>7,5 =>7,6 =>7,7 =>7,8

代码

初看很是迷茫,实际上并不难。简单的思路便是,尝试所有上下左右是否可以进行走,如果可以那么就走,反之则不行。往上(y轴 -1)、往左(x轴 -1)、往下(y轴 +1)、往右 (x轴 +1)。

总的来说代码结构为:

  1. 判断当前坐标是否出界 + 是否为墙,或者产生了回路(在一个圆圈来回跑),当出现这些情况,直接返回,退出当前函数。
  2. 判断是否到达终点,如果是,就将这个路径保存起来(因为一个迷宫一般有多个路线,如果不需要可以直接在这一步停止递归)
  3. 如果以上条件都没有成立,那么就将当前坐标加入到存储路径的list中,然后测试当前上下左右是否可走。最后将当前的坐标从list中删除。

最绕的可能就是第三步,因为如果一条路是通的,那么必然会一直执行走到重点。反之必然会在一个函数中执行完毕,那么这条路就是走不通的。

	public static void f(int x,int y,List<int[]> path){
		if (x < 0 || y < 0 || x > map.length-1 || y > map.length-1 || map[x][y] == 1 || Isv[x][y] == 1) {
			return;
		}
		if (x == map.length-1 && y == map.length-1) {
			String temp = "";
			for (int i = 0; i < path.size(); i++) {
				temp += path.get(i)[0] + "," + path.get(i)[1];
				if (i < path.size() - 1) {
					temp += " =>";
				}
			}
			ans.add(temp);
		}else {
			Isv[x][y] = 1;
			int[] p = {x,y};
			path.add(p);
			f(x + 1, y, path);  
			f(x, y + 1, path); 
			f(x, y - 1, path); 
			f(x - 1, y, path); 
			Isv[x][y] = 0; 
			path.remove(path.size()-1);
		}
		
		
		
	}

}

DFS深度优先搜索算法与走迷宫

https://ku-m.cn/index.php/archives/270/

作者

KuM

发布时间

2020-01-28

许可协议

CC BY 4.0

添加新评论