走迷宫?基于深度优先搜索的路径查找算法

July 10, 2016
JavaData StructureAlgorithm

还记得以前文曲星或者学习机上的走迷宫游戏吧,小时候玩的不亦乐乎,可是怎么样让计算机去运算两个点的最优路径呢?这篇博客将会讲述深度优先搜索算法。

说走迷宫可能太大了,我们来将问题简化一下:

给定下面一副地图,黄色是路,蓝色是墙壁,需要设计程序从左上角出发,以最短的路径到达红点位置

所以说程序应该选择这样的路径:

而不是这样:

这时就可以用到深度优先搜索算法。

  • 定义

深度优先搜索(Depth First Search,
DFS),是一种搜索算法,经常用在,树(Tree)和图(Graph)的搜索中,不过不知道树和图的也没关系,这篇文章不会显性的出现这些东西。

这个搜索算法的关键在于解决, 现在该如何做 , 至于下一步要怎么办?这不就和现在该如何做是一样的问题嘛,比如我编写的处理当前改走那个方向的函数是
dfs(currentStep), 那么下一步不就是 dfs(currentStep+1)喽~ 看到这里有一定基础的人已经猜到了,这个算法要用到递归,没错。

深度优先搜索的基本模型大概是这样

  1. void dfs(int currentStep){
  2. if 到达边界
  3. return
  4. for each move //尝试每一种可能走法
  5. {
  6. dfs(currentStep+1); //进行下一步处理
  7. }
  8. return
  9. }

这一看就是典型的递归模型啦

就像我之前博客 递归算法初步:n阶矩阵行列式求解所说的那样

设计递归算法,需要包含以下两个基本法则:
1.基准情形(Base Case) ,必须总要有某些基准的清醒,在这个情形中,不执行递归就能求解。
2.不断推进(Making Progress)
,对于需要递归求解的情形,递归调用必须总能够朝着一个基准情形推进。这样的话,不断推进到基准情形,到达基准情形的时候递归才会推出,得到返回值。

  • 实现

好了基本的说了那么多,现在来看下这个算法的具体实现吧

首先是地图,我们将地图抽象成一个二维数组, 其中0代表空地,2代表障碍物,也就是墙壁,那么,博客一开始的那张地图就可以变成以下这个样子:

接下来就是要设计二位数组上每个点的抽象,为了方便,也可以不这么做:

我新建了一个类叫做MapPoint

  1. public class MapPoint {
  2. public static int MAP_PONIT_OCCUPIED = 1;
  3. public static int MAP_PONIT_EMPTY = 0;
  4. public static int MAP_PONIT_OBSTRUCTION = 2;
  5. private boolean occupied = false;
  6. private int type;
  7. public MapPoint(int type){}
  8. public int getType() {}
  9. public void setType(int type) {}
  10. public boolean isOccupied() {}
  11. }

这个类很简单只有一个属性,type,代表这个点,1代表占用,一会要用到,0代表空,2代表这个点为障碍物,并且提供三个函数来查看和设置点的相关属性。

并且,代表地图的二维数组也使用了一个Map类封装

  1. public class Map {
  2. private MapPoint[][] mapArr;
  3. int mapHeight;
  4. int mapWidth;
  5. public Map (String path){}
  6. public MapPoint[][] getMapArr() {} //得到地图二维数组
  7. public void setPoint(int i,int j,int type){} //设置点类型
  8. public MapPoint getPoint(int i,int j){} //获取指定坐标的点
  9. public void printMap(){} //打印地图
  10. public void readMapFromFile(String path){} //从文件读取地图
  11. }

Map类实现了对地图的各种操作:读取,打印输出,地图点编辑都由这个类处理

接下来就是算法的核心了

  • dfs函数

这个函数应该拥有三个参数,当先点的x,y坐标,当前步数(其实叫做搜索深度)

  1. void dfs(int x, int y, int step){}

至于实现递归的第一要素:基准情形,在这个问题中就是指判断是否到达终点,这个也很好写啊

  1. void dfs(int x, int y, int step){
  2. if (x == targetX && y == targetY){ //到达目标位置
  3. if (depth<minDepth){ //更新最小步数
  4. minDepth = depth;
  5. }
  6. return; //这个return用来结束当前递归,一定别忘了!!!
  7. }
  8. }

接下来,找出下一步可以走的地方,这个更简单啦,最多也就上下左右四个方向嘛~, 定义一个next数组:

  1. int[][] next = {
  2. {0,1},//Right
  3. {1,0},//Down
  4. {0,-1},//Left
  5. {-1,0}//Up
  6. };

接下来对每个点进行这四种可能的遍历就行了,这里要认真读代码,看起来比较抽象

  1. for (int k=0;k<=3;k++){
  2. //生成下一点的坐标
  3. nextX = x + next[k][0];
  4. nextY = y + next[k][1];
  5. //判断是否出现越界窗框
  6. if (nextX<0 || nextX>map.mapHeight-1 || nextY < 0 || nextY>map.mapWidth-1){
  7. continue; //结束当前进程而不退出循环
  8. }
  9. //判断这个点有没有被占用,或是障碍物(这个逻辑已在MapPoint类中封装好了)
  10. if (!map.getPoint(nextX,nextY).isOccupied()){
  11. map.setPoint(nextX,nextY,1); //标记这个点已经被走过了
  12. dfs(nextX,nextY,step+1); //调用自身,尝试下一个点
  13. map.setPoint(nextX,nextY,0); //尝试结束后取消这个点的占用标记
  14. }
  15. }

好了,这样就结束了,递归的两个要素都实现了~总共不超过50行吧~

到我的Github 去查看完整的代码吧。

但是当然还需要有一些其他的功能要实现啦,比如记录路径之类的;

记录路径的实现推荐去新建一个 双向链表 (Linked
List)来实现(如果用栈(Stack)的话输出的坐标就是从最后到第一个,效果不好,要是用队列的话,错的更是没边了。。队列不能移除最后一个元素,只能移除第一个),我这样做只是为了速度,其实用个一位数组也行啊,只不过这样做太傻了,编程的时候能正确的使用数据结构是很重要的:

  • 如果到达终点就把当前的链表复制一份当做最优路线
  • 每次标记点已经走过的时候,再把这个点插入到双向链表里
  • 尝试结束后取消点的占用标记的时候顺便移除双向链表的最后插入的元素

好了,看一下效果吧~

  1. public static void main(String[] args) {
  2. Map map = new Map("C:\\Users\\Mike\\Desktop\\map.txt");
  3. RouteFinder finder = new RouteFinder(map,0,0,4,3);
  4. finder.findBestRoute();
  5. }

看看,是不是和开始的预计一样呢~

可以再我的 Github 上查看或下载整个项目~

这只是深度优先搜索的一个基本应用,这个搜索算法还被广泛用在棋类AI中,以前我写过一篇博客三子棋AI实现:MiniMax算法 ,这个算法的主要核心就就是一个树的深度优先搜索。

可以再举几个简单的例子,求出 1,2,3 三个数的全排列 ,123,132,213 ,232 ,312 ,321
,编程的初学者都能做到,3个嵌套for循环。。。 求出 1, 2, 3,4 ,5 五个数的全排列,好,简单,5个嵌套for循环。。。 行,
那要是我想求出1到20中20个数字的全排列呢?20个for循环。。怎么可能。。当然是深度优先搜索了。

我的博客MikeTech app现已登陆iPhone和Android

iPhone版下载
Android版下载

Comments

July 21, 2018 at 10:52 am

There are no comments

keyboard_arrow_up