Python实现基于DFS和BFS算法的吃豆人寻路实验

分手后的思念是犯贱 2024-04-06 10:08 141阅读 0赞

## 吃豆人寻路实验 ##

## 一、实现 DFS 和 BFS ##

要优化之前首先要完成最基本的版本，因此首先完成了最基础的 dfs 和 bfs 的算法，算法的流程如下图：

![在这里插入图片描述][b4f0c89b0f604caa962be514c9e0d32a.png]

图 1 算法流程 需要注意的是，dfs 扩展节点的时候会把节点放在队列首位，并在下次立刻取出；bfs 则会把节点放在队列尾部，并且当前面的遍历完后才会取出，分别对应的是“先入后出”和“先入先出”，因此使用的数据结构分别是“栈”和“队列”。

### 1.1 伪代码 ###

<table> 
 <thead> 
  <tr> 
   <th>接下来展示 dfs 和 bfs 在该问题中的伪代码：</th> 
   <th>接下来展示 dfs 和 bfs 在该问题中的伪代码：</th> 
   <th>接下来展示 dfs 和 bfs 在该问题中的伪代码：</th> 
   <th>接下来展示 dfs 和 bfs 在该问题中的伪代码：</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1.1.1 DFS 伪代码</td> 
   <td></td> 
   <td>1.1.2 BFS 伪代码</td> 
   <td>1.1.2 BFS 伪代码</td> 
  </tr> 
  <tr> 
   <td>定义 DFS 栈</td> 
   <td></td> 
   <td>定义 BFS 队列</td> 
   <td>定义 BFS 队列</td> 
  </tr> 
  <tr> 
   <td>定义结果栈</td> 
   <td></td> 
   <td>定义父亲节点字典</td> 
   <td>定义父亲节点字典</td> 
  </tr> 
  <tr> 
   <td>将起点放入栈</td> 
   <td></td> 
   <td></td> 
   <td>将起点放入队列</td> 
  </tr> 
  <tr> 
   <td>While 栈非空：</td> 
   <td></td> 
   <td></td> 
   <td>While 队列非空：</td> 
  </tr> 
  <tr> 
   <td>取出栈顶节点，再放入</td> 
   <td></td> 
   <td></td> 
   <td>取出队列头节点，并删掉</td> 
  </tr> 
  <tr> 
   <td>标记该点被访问</td> 
   <td></td> 
   <td></td> 
   <td>标记该点被访问</td> 
  </tr> 
  <tr> 
   <td>If 到达终点：</td> 
   <td></td> 
   <td></td> 
   <td>If 到达终点：</td> 
  </tr> 
  <tr> 
   <td>返回结果栈</td> 
   <td></td> 
   <td></td> 
   <td>根据字典，返回结果</td> 
  </tr> 
  <tr> 
   <td>对该节点进行扩展</td> 
   <td></td> 
   <td></td> 
   <td>对该节点进行扩展</td> 
  </tr> 
  <tr> 
   <td>For 每个扩展节点：</td> 
   <td></td> 
   <td></td> 
   <td>For 每个扩展节点：</td> 
  </tr> 
  <tr> 
   <td>If 扩展节点没被访问：</td> 
   <td></td> 
   <td></td> 
   <td>If 扩展节点没被访问：</td> 
  </tr> 
  <tr> 
   <td>入栈顶 ； If 该节点没有扩展节点: ； DFS 栈中删除该节点 结果栈中删除该节点</td> 
   <td></td> 
   <td></td> 
   <td>入队尾</td> 
  </tr> 
 </tbody> 
</table>

### 1.2 结果展示 ###

分别对 dfs 和 bfs 进行测试，可以得到下面的结果

#### 1.2.1 DFS扩展结果 ####

![在这里插入图片描述][dd3533e247714b7380454872fa2a43dc.png]

图 1 普通 dfs 小地图

![在这里插入图片描述][db586ffe6a944ed1944eb6d8af0c29de.png]

图 2 普通 dfs 中地图

![在这里插入图片描述][2b793627792149838ae46f034b7f49f9.png]

图 3 普通 dfs 大地图

#### 1.2.2 BFS扩展结果 ####

![在这里插入图片描述][19766a0c6c1744bca53e27c0f0d2523a.png]

图 4 普通 bfs 小地图

![在这里插入图片描述][ef73d57847d94dceb76f93d4ca605eb7.png]

图 5 普通 bfs 中地图

![在这里插入图片描述][dd216262b10448fba9d465514cbf5db2.png]

图 6 普通 bfs 大地图

接下来是地图遍历过程的展示

![在这里插入图片描述][094ed48bb30741e6b1466b4543840bcb.png]  
![在这里插入图片描述][083fba7aa47c491fac950cdf0fc9d657.png]  
![在这里插入图片描述][8b872408d380462b9d85f72cc7f19d00.png]  
![在这里插入图片描述][3be44204d3aa461ebb680c5597e7fb72.png]

#### 1.2.3 地图展示： ####

图 7 地图可视化结果

上图展示的地图结果，左边都是 dfs 的搜索方式，右边都是 bfs 的搜索方式，可以看到 dfs 的搜索策略经常是一条路走到黑，直到找到终点。而 bfs 会搜索全部可以到达的地点，直到找到终点。

这里需要说明的是，无论是 dfs 还是 bfs 我都只是单纯的设置“找到终点后就退出”，因此没有遍历完全部的路径，因为从道理上来说，dfs 和 bfs 的搜索方式都属于全部搜索的暴力式搜索，理应搜索出全部能到达终点的路径，并存起来，判断得到最优路径的。

## 二、对算法进行优化 ##

在优化的过程中我询问了 111172 班的汪圣翔关于 DFS 优化的问题，最终达成共识 DFS 似乎没法进行优化…我的理解是这样的： 由于 DFS 的定义是在每次扩展的时候，直接对第一个被扩展到的节点进行向下搜索，因此 DFS 没有选择的余地。而对于 BFS 来说，它会列出所有被扩展到的节点，这样一来，就有了使用评价函数进行优化的余地了，可以在这一步对节点进行排序，将评价更高的节点进行扩展，这样就能比原来更快地找到到达终点的路径。

我一共写了三种优化方式，分别是贪心和 A\*，用到了 util 中提供的优先队列的定义。这里只需要将各自的评价函数进行定义，就可以得到符合该算法的优先队列了，我的函数定义如下：

![在这里插入图片描述][135460e04c6f41b9956458641fed4734.png]

图 8 启发式函数以及优先队列的定义，由于是在 DFS 的函数里面写的这个算法，因此变量名沿用了 dfs\_stack 这个叫法 将启发函数定义翻译成中文，如下：

贪心：从该节点到终点的曼哈顿距离 A\*： 从该节点到终点的曼哈顿距离 + 从该节点到起点的曼哈顿距离接下来是三种优化的结果展示，如下图所示：

### 2.1 贪心优化 ###

![在这里插入图片描述][ec50fa9ec9fe4ed89ba37b7805c4358c.png]  
![在这里插入图片描述][0d6e1529c2694da8bb8fa2ded7c363e1.png]

图 8 贪心优化 中地图

![在这里插入图片描述][0e3da70eca7f4ab09ed645fd73fed65c.png]  
![在这里插入图片描述][bf4ad7736e244fea8118b8f770aeec5a.png]

图 9 贪心优化 大地图

### 2.2 \*优化 ###

![在这里插入图片描述][c1cd5e2a4e784fd485a69822e9a04bb1.png]  
![在这里插入图片描述][210c2c9a20a7495aae82e243be047fc1.png]

图 10 A\*优化 中地图

[b4f0c89b0f604caa962be514c9e0d32a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/22aae96db6324cf3913fbb77c63bb8a5.png
[dd3533e247714b7380454872fa2a43dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/0e1cd3951dfe498cb1f29d2a72646164.png
[db586ffe6a944ed1944eb6d8af0c29de.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/5e979f7bdc85400ba6cba46ac2567b53.png
[2b793627792149838ae46f034b7f49f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/3f2ed7b8f9114021888dfef07fb30dea.png
[19766a0c6c1744bca53e27c0f0d2523a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/4d13ac61f15646a99e858fa088174b97.png
[ef73d57847d94dceb76f93d4ca605eb7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/b23fc369f0a94959935eafa84132e35f.png
[dd216262b10448fba9d465514cbf5db2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/c25dc5bf3f1b41d9b77e546e0881909f.png
[094ed48bb30741e6b1466b4543840bcb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/236edb2112e8411ba7acfbcfcbddd201.png
[083fba7aa47c491fac950cdf0fc9d657.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/e0ebe4cb72d8469890dfd5b61f8b3809.png
[8b872408d380462b9d85f72cc7f19d00.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/8e4edb66949a46ffa6eac26c4942e859.png
[3be44204d3aa461ebb680c5597e7fb72.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/7c4cfe42ad1347ee8096b868df42ab73.png
[135460e04c6f41b9956458641fed4734.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/0e7d4fbc22e94961be7c8a4283683a08.png
[ec50fa9ec9fe4ed89ba37b7805c4358c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/efc7cd27c04a4794b6f02ac83fc1201a.png
[0d6e1529c2694da8bb8fa2ded7c363e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/35ed8647eef04ad8b5229d0219be7d21.png
[0e3da70eca7f4ab09ed645fd73fed65c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/2fa6ed2e3da54b36853a1de09b99393d.png
[bf4ad7736e244fea8118b8f770aeec5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/7a7d42e8f97448f78d6c90746c4bb830.png
[c1cd5e2a4e784fd485a69822e9a04bb1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/a9f3155a885f4e97bbb050dd744f22b1.png
[210c2c9a20a7495aae82e243be047fc1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/92193036651b4d3aa1655725055d89fe.png