欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

啊哈算法之解救小哈

程序员文章站 2022-10-08 18:59:29
简述 本算法摘选自啊哈磊所著的《啊哈!算法》第四章第二节的题目——DFS算法解救小哈。文中代码使用C语言编写,博主通过阅读和理解,重新由Java代码实现了一遍,以此来加深对DFS算法的印象。 游戏设置 迷宫由n行m列的单元格组成(n和m小于等于50),每个单元格要么是空地要么是障碍物,障碍物是不能通 ......

简述

本算法摘选自啊哈磊所著的《啊哈!算法》第四章第二节的题目——dfs算法解救小哈。文中代码使用c语言编写,博主通过阅读和理解,重新由java代码实现了一遍,以此来加深对dfs算法的印象。

游戏设置

迷宫由n行m列的单元格组成(n和m小于等于50),每个单元格要么是空地要么是障碍物,障碍物是不能通行的,要求从迷宫起点开始找到一条通往迷宫中某个点的最短路径。

解法思路

首先用一个二维数组来存储迷宫,刚开始假设从迷宫入口(0, 0)开始,目标位置在(q, p),此行目的就是找到从(0, 0)到(q, p)的最短路径。如果从入口的点,那么下一步只能是往右或者往下走,如果是到了迷宫中间的某个点,那么可能是往上下左右四个方向走,只能一个个去尝试,索性我们这里就定义个顺序,按照顺时针(即右、下、左、上)的方向逐个尝试

还有一个问题值得注意,就是已经路过的点,肯定是不需要计算在接下来尝试的点上了,这里为了方便判断,可以利用熟悉的桶来标记,已经经过的点都标记在桶里,使用完之后回来再清理桶标记位就行了。对于障碍物,遇到障碍物就换个方向重新开始,这里就是重新返回到下一次递归循环就行了。

注意,当我们遍历之后找到了目标点位,但可能不是到达所使用的最短路径,所以在找到目标点位之后,需要返回重新尝试从其他的方向寻找,直到把所有的可能性都尝试完了,最后才把最短的那条路径输出来。

现在我们使用深度优先搜索算法dfs来尝试实现这个算法。先从dfs函数开始,思考当前步骤是什么样的,下一步和当前步骤是一样的,边界条件是什么样的。

我们给dfs函数定义三个参数x、y和step,分别表示下一步达到的坐标以及当前步数,如果判断已经找到目标位置,即判断(x, y)是否与目标位置相等即可,同时用当前所走的step数去判断是否是最小步数,是则更新记录到最小步数值。

在具体的代码实现中,我们还应该关注到如何从顺时针的四个方向上开始搜索目标,如何定位到下一个点位,同时判断是否越界,或者是否是障碍物、或者该点位之前已经路过等等之类的问题。

代码实现

 1 public class mazedfs {
 2 
 3     /** 迷宫矩阵的大小:n行 m列 */
 4     private static final integer n = 10, m = 10;
 5     /** 迷宫中的目标位置 */
 6     private static final integer q = 6, p = 6;
 7     /** 从起点到目标位置所行的最小步数 */
 8     private static integer minstep = 999;
 9     /** 迷宫地图 */
10     private static int[][] maze = new int[50][50];
11     /** 桶,记录步行经过的路径位置 */
12     private static int[][] book = new int[50][50];
13 
14     /**
15      * 递归函数
16      * 往前走一步,查看当前位置是否目标位置,否则继续往下一个方向前进
17      * @param x
18      * @param y
19      * @param step
20      */
21     public void dfs(int x, int y, int step) {
22         // 定义四个方向,依照顺时针方向,依次向右、向下、向左、向上
23         int[][] next = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
24 
25         system.out.println("当前坐标点:" + x + " " + y);
26 
27         // 判断是否到达目标位置
28         if(x == q && y == p) {
29             // 更新最小步数值
30             if(step < minstep) {
31                 minstep = step;
32             }
33             // 按照当前方式找到,则返回,换其他方式继续找
34             return;
35         }
36 
37         // 枚举四个方向的找法
38         int tx, ty, k;
39         for(k = 0; k < 4; k++) {
40             // 计算出下一个步入的点的位置
41             tx = x + next[k][0];
42             ty = y + next[k][1];
43 
44             // 判断这个方向的下一步是否越界
45             if(tx < 0 || tx >= n || ty < 0 || ty >= m) {
46                 continue;
47             }
48 
49             // 判断该点是否为障碍物或者刚才已经路过
50             if(maze[tx][ty] == 0 && book[tx][ty] == 0) {
51                 // 标记这个点已经路过
52                 book[tx][ty] = 1;
53                 // 接着尝试下一个点
54                 dfs(tx, ty, step + 1);
55                 // 尝试结束,取消这个点的标记
56                 book[tx][ty] = 0;
57             }
58         }
59         return;
60     }
61 
62     public static void main(string[] args) {
63         mazedfs mazedfs = new mazedfs();
64        // 初始化,把迷宫矩阵用二维数组表示出来,空地用“0”表示,障碍物用“1”表示
65         // todo
66 
67         // 从起点开始搜索,这里假设起点位置[0, 0],开始时步数为0
68         int startx = 0, starty = 0, step = 0;
69         // 在桶中标记起点已经历
70         book[startx][starty] = 1;
71         // 从第一个位置开始
72         mazedfs.dfs(startx, starty, step);
73 
74         // 输出最少步数
75         system.out.println(string.format("从起点开始最少经过%d步可以到达目标位置。", minstep));
76     }
77 
78 }

参考资料

1、《啊哈!算法》/ 啊哈磊著. 人民邮电出版社