# 吃豆人寻路实验
# 一、实现 DFS 和 BFS
要优化之前首先要完成最基本的版本,因此首先完成了最基础的 dfs 和 bfs 的算法,算法的流程如下图:
![](https://www.writebug.com/myres/static/uploads/2022/9/17/ca24c90452f80e5c4bba61af9a33bd33.writebug)
图 1 算法流程 需要注意的是,dfs 扩展节点的时候会把节点放在队列首位,并在下次立刻取出;bfs 则会把节点放在队列尾部,并且当前面的遍历完后才会取出,分别对应的是“先入后出”和“先入先出”,因此使用的数据结构分别是“栈”和“队列”。
## 1.1 伪代码
| 接下来展示 dfs 和 bfs 在该问题中的伪代码: | 接下来展示 dfs 和 bfs 在该问题中的伪代码: | 接下来展示 dfs 和 bfs 在该问题中的伪代码: | 接下来展示 dfs 和 bfs 在该问题中的伪代码: |
|----|----|----|----|
| 1.1.1 DFS 伪代码 | | 1.1.2 BFS 伪代码 | 1.1.2 BFS 伪代码 |
| 定义 DFS 栈 | | 定义 BFS 队列 | 定义 BFS 队列 |
| 定义结果栈 | | 定义父亲节点字典 | 定义父亲节点字典 |
| 将起点放入栈 | | | 将起点放入队列 |
| While 栈非空: | | | While 队列非空: |
| 取出栈顶节点,再放入 | | | 取出队列头节点,并删掉 |
| 标记该点被访问 | | | 标记该点被访问 |
| If 到达终点: | | | If 到达终点: |
| 返回结果栈 | | | 根据字典,返回结果 |
| 对该节点进行扩展 | | | 对该节点进行扩展 |
| For 每个扩展节点: | | | For 每个扩展节点: |
| If 扩展节点没被访问: | | | If 扩展节点没被访问: |
| 入栈顶 ; If 该节点没有扩展节点: ; DFS 栈中删除该节点 结果栈中删除该节点 | | | 入队尾 |
## 1.2 结果展示
分别对 dfs 和 bfs 进行测试,可以得到下面的结果
### 1.2.1 DFS扩展结果
![](https://www.writebug.com/myres/static/uploads/2022/9/17/bdaa25e452529c04904910e09be13d2c.writebug)
图 1 普通 dfs 小地图
![](https://www.writebug.com/myres/static/uploads/2022/9/17/16f3bea65de9b4450dadaa60231e8ee6.writebug)
图 2 普通 dfs 中地图
![](https://www.writebug.com/myres/static/uploads/2022/9/17/19dd9da440e9e7171ab00fcebf00cb49.writebug)
图 3 普通 dfs 大地图
### 1.2.2 BFS扩展结果
![](https://www.writebug.com/myres/static/uploads/2022/9/17/bccd37f8711b643a90e30868af20307c.writebug)
图 4 普通 bfs 小地图
![](https://www.writebug.com/myres/static/uploads/2022/9/17/085ab6b00ea2e9542b3ef0100a7c78a1.writebug)
图 5 普通 bfs 中地图
![](https://www.writebug.com/myres/static/uploads/2022/9/17/25c7c6ee00fbc6c0f72bd160de55c385.writebug)
图 6 普通 bfs 大地图
接下来是地图遍历过程的展示
![](https://www.writebug.com/myres/static/uploads/2022/9/17/7313b50904ff46e608686dcea751975c.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/9/17/537e6df2066be0c11535e9d73800ab46.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/9/17/d891bf618928283d6b1a08026ed0ae83.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/9/17/e2e934e33f49f9b318691c7dfc193d24.writebug)
### 1.2.3 地图展示:
图 7 地图可视化结果
上图展示的地图结果,左边都是 dfs 的搜索方式,右边都是 bfs 的搜索方式,可以看到 dfs 的搜索策略经常是一条路走到黑,直到找到终点。而 bfs 会搜索全部可以到达的地点,直到找到终点。
这里需要说明的是,无论是 dfs 还是 bfs 我都只是单纯的设置“找到终点后就退出”,因此没有遍历完全部的路径,因为从道理上来说,dfs 和 bfs 的搜索方式都属于全部搜索的暴力式搜索,理应搜索出全部能到达终点的路径,并存起来,判断得到最优路径的。
# 二、对算法进行优化
在优化的过程中我询问了 111172 班的汪圣翔关于 DFS 优化的问题,最终达成共识 DFS 似乎没法进行优化…我的理解是这样的: 由于 DFS 的定义是在每次扩展的时候,直接对第一个被扩展到的节点进行向下搜索,因此 DFS 没有选择的余地。而对于 BFS 来说,它会列出所有被扩展到的节点,这样一来,就有了使用评价函数进行优化的余地了,可以在这一步对节点进行排序,将评价更高的节点进行扩展,这样就能比原来更快地找到到达终点的路径。
我一共写了三种优化方式,分别是贪心和 A*,用到了 util 中提供的优先队列的定义。这里只需要将各自的评价函数进行定义,就可以得到符合该算法的优先队列了,我的函数定义如下:
![](https://www.writebug.com/myres/static/uploads/2022/9/17/a94248dad934cbfe1fbf979889a16133.writebug)
图 8 启发式函数以及优先队列的定义,由于是在 DFS 的函数里面写的这个算法,因此变量名沿用了 dfs_stack 这个叫法 将启发函数定义翻译成中文,如下:
贪心:从该节点到终点的曼哈顿距离 A*: 从该节点到终点的曼哈顿距离 + 从该节点到起点的曼哈顿距离接下来是三种优化的结果展示,如下图所示:
## 2.1 贪心优化
![](https://www.writebug.com/myres/static/uploads/2022/9/17/feabf1d0e7fd058e0235ab7409900742.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/9/17/3b5754355058e78556f03ca431fd261d.writebug)
图 8 贪心优化 中地图
![](https://www.writebug.com/myres/static/uploads/2022/9/17/42aec907065ccd85cd12bd28968a9f7d.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/9/17/f90b095a6b1ee3192c5b3ec950e18c06.writebug)
图 9 贪心优化 大地图
## 2.2 *优化
![](https://www.writebug.com/myres/static/uploads/2022/9/17/1fcdb62d1616eef7b8aa16be013c5f1c.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/9/17/2142e9e1cd944a045731b47bfa65118b.writebug)
图 10 A*优化 中地图
![](https://www.writebug.com/myres/static/uploads/2022/9/17/6331e418aadcb781beb4051c9a1403a1.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/9/17/1cdf3e3ceecd10d2c4bfdaa2a79cbd13.writebug)
图 11 A*优化 大地图
最后附上表进行对比:表 1 扩展节点个数
| 单位:个 |DFS |BFS |贪心 |A* |
|----|----|----|----|----|
| 小地图 |24 |24 |16 |24 |
| 中地图 |274 |343 |152 |338 |
| 大地图 |601 |830 |677 |720 |
首先是扩展节点的个数。先对 DFS 和 BFS 进行对比,可以明显看到 BFS 扩展的节点都要大于等于 DFS 的节点个数,因为 BFS 的范围更广,更倾向于搜索全局的所有可能性,而DFS 只需要一个正确的就够了。
贪心算法相比其他的算法来说,扩展节点的个数更少,因为在贪心的代价函数下,我们只会选取离目标越来越近的节点,不会去拓展多余的节点。
A*算法的拓展节点个数和 BFS 的差不多一样多,主要是因为 A*的任务是一定要找到最近的一条路径,因此会更多的探索可能到达终点的路径。而它比 BFS 少的原因是因为 A*存在一个选择过程,只会扩展更加靠近终点的节点,而不会想 BFS 一样一股脑的全都扩展。
表 2 路径代价
| 单位:长度 |DFS |BFS |贪心 |A* |
|----|----|----|----|----|
| 小地图 |10 |8 |8 |8 |
| 中地图 |130 |68 |74 |68 |
| 大地图 |210 |210 |210 |210 |
接下来是路径代价的对比。可以看到和 DFS 相比,BFS 的算法更能找到距离短的路径(毕竟它探索的节点更多�